Cod sursa(job #811192)

Utilizator irene_mFMI Irina Iancu irene_m Data 11 noiembrie 2012 17:41:00
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.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 {
    short int val, pos, add;
    Node() {
        val = pos = add = 0;
    }
} arb[MAXN];

short int v[MAXN];
int N, a, b, val;

void read() {
    FILE *f = fopen(infile, "rt");
    fscanf(f, "%d", &N);
    for(int i = 1; i <= N; ++i)
        fscanf(f, "%hd", 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; arb[node].add += 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 + arb[node].add; arb[node].pos = arb[fd].pos;
    }
    else {
        arb[node].val = arb[fs].val + arb[node].add; arb[node].pos = arb[fs].pos;
    }

}

void solve() {
    FILE *f = fopen(outfile, "wt");
    buildTree(1, 1, N);
    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; updateTree(1, 1, N);
    }
    fclose(f);
}

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