Cod sursa(job #2102662)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 9 ianuarie 2018 11:43:57
Problema Secv8 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>
#define MAXN 1000000
#define INF 2000000000

#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a * 10 + c - '0';
        c = nextch();
    }
    return a;
}
char bufw[1 + BUF_SIZE];
int pbufw = 0;
inline void printch(char c){
    bufw[pbufw++] = c;
    if(pbufw == BUF_SIZE){
        fwrite(bufw, 1, BUF_SIZE, fo);
        pbufw = 0;
    }
}
void printnum(int a){
    if(a > 0){
        printnum(a / 10);
        printch(a % 10 + '0');
    }
}

int aint[4 * MAXN];
int v[1 + MAXN];
int dif[1 + MAXN];
int f[1 + MAXN];
int pos, val;
void update(int p, int st, int dr){
    if(st == dr){
        v[pos] = val;
        aint[p] = pos;
    }
    else{
        int m = (st + dr) / 2;
        if(pos <= m) update(2 * p, st, m);
        else update(2 * p + 1, m + 1, dr);
        if(v[aint[2 * p]] < v[aint[2 * p + 1]]) aint[p] = aint[2 * p];
        else aint[p] = aint[2 * p + 1];
    }
}

int main(){
    fi = fopen("viteze.in","r");
    fo = fopen("viteze.out","w");

    int n = nextnum();
    v[0] = INF;
    for(int i = 1; i <= n; i++){
        int x = nextnum();

        pos = i;
        val = x;
        update(1, 1, n);
    }
    for(int i = 1; i <= n; i++)
        dif[i] = nextnum();
    if(dif[1] < v[1]){
        pos = 1;
        val = dif[1];
        update(1, 1, n);
    }
    int marked = 0;
    while(marked < n){
        int p = aint[1];
        f[p] = v[p];
        if(p != n && v[p + 1] != INF && v[p] + dif[p + 1] < v[p + 1]){
            pos = p + 1;
            val = v[p] + dif[p + 1];
            update(1, 1, n);
        }
        if(p != 1 && v[p - 1] != INF && v[p] + dif[p] < v[p - 1]){
            pos = p - 1;
            val = v[p] + dif[p];
            update(1, 1, n);
        }
        pos = p;
        val = INF;
        update(1, 1, n);
        marked++;
    }
    for(int i = 1; i <= n; i++){
        printnum(f[i]);
        printch(' ');
    }
    if(pbufw)
        fwrite(bufw, 1, pbufw, fo);

    fclose(fi);
    fclose(fo);
    return 0;
}