Submission #442484

#	Time	Username	Problem	Language	Result	Execution time	Memory
442484		SirCovidThe19th	Wall (IOI14_wall)	C++14	100 / 100	781 ms	102388 KiB

wall

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int mx = (1<<22);

int N; pair<int, int> seg[mx*2]; // f - lowest, s - highest

void comb(int i, int l, int h){
    seg[i].f = min(seg[i].f, l); seg[i].s = max(min(seg[i].s, l), h);
}
void push(int i){ 
    comb(i*2, seg[i].f, seg[i].s), comb(i*2+1, seg[i].f, seg[i].s);
    seg[i] = {1e6, 0};
}
void upd(int x, int y, int op, int v, int l, int r, int i = 1){ 
    if (l > y or r < x) return;
    if (l >= x and r <= y){ comb(i, ((op == 2) ? v : 1e6), ((op == 1) ? v : 0)); return; }
    push(i); int m = (l+r)/2; 
    upd(x, y, op, v, l, m, i*2); upd(x, y, op, v, m+1, r, i*2+1); 
}
void solve(int* res, int l, int r, int i = 1){
    if (l == r){ res[l] = seg[i].s; return;  }
    push(i);
    int m = (l+r)/2; solve(res, l, m, i*2); solve(res, m+1, r, i*2+1); 
}   
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int res[]){
    fill(seg, seg+mx*2, make_pair(1e6, 0));
    for (int i = 0; i < k; i++) upd(l[i], r[i], op[i], h[i], 0, n-1);
    solve(res, 0, n-1);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39