Cod sursa(job #811218)

Utilizator irene_mFMI Irina Iancu irene_m Data 11 noiembrie 2012 18:26:44
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <stdio.h>
#include <string.h>
#define fs (node) << 1
#define fd ((node) << 1) + 1
#define mid ((left + right) >> 1)

using namespace std;

const char infile[] = "schi.in";
const char outfile[] = "schi.out";
const int MAXN = 1 << 16;

struct Node {
    int val;
    short int pos;
    Node() {
        val = pos = 0;
    }
} arb[MAXN];

int *v;
int N, a, b, val;

void read() {
    FILE *f = fopen(infile, "rt");
    fscanf(f, "%d", &N);
    v = new int[(N << 1) + 5];
    for(int i = 1; i <= N; ++i)
        fscanf(f, "%d", v + i);
    fclose(f);
}

void buildTree(int node, int left, int right) {
    if(left > right) return;
    if(left == right) {
        arb[node].val = v[left]; arb[node].pos = left;
        return;
    }
    buildTree(fs, left, mid);
    buildTree(fd, mid + 1, right);
    if(arb[fd].val <= arb[fs].val) {
        arb[node].val = arb[fd].val; arb[node].pos = arb[fd].pos;
    }
    else {
        arb[node].val = arb[fs].val; arb[node].pos = arb[fs].pos;
    }
}

void updateTree(int node, int left, int right) {
    if(a > b) return;
    if(a <= left && right <= b) {
        arb[node].val += val; v[node] += val;
        return;
    }
    if(a <= mid)
        updateTree(fs, left, mid);
    if( mid < b)
        updateTree(fd, mid + 1, right);
    if(arb[fd].val <= arb[fs].val) {
        arb[node].val = arb[fd].val + v[node]; arb[node].pos = arb[fd].pos;
    }
    else {
        arb[node].val = arb[fs].val + v[node]; arb[node].pos = arb[fs].pos;
    }

}

void solve() {
    FILE *f = fopen(outfile, "wt");
    buildTree(1, 1, N);
    memset(v, 0, (N << 1) * sizeof(v));
    for(int i = 1; i <= N; ++i) {
        fprintf(f, "%d\n", arb[1].pos);
        a = 1; b = arb[1].pos - 1; val = 1; updateTree(1, 1, N);
        a = b = arb[1].pos; val = MAXN >> 1; updateTree(1, 1, N);
    }
}

int main() {
    read();
    solve();
    return 0;
}