Submission #986878

#TimeUsernameProblemLanguageResultExecution timeMemory
986878MuntherCarrotWall (IOI14_wall)C++14
61 / 100
449 ms41044 KiB
#include <bits/stdc++.h> #include "wall.h" using namespace std; const int INF = 0x3f3f3f3f; const int N = 1 << 17; int t[N << 2]; int add[N << 2], del[N << 2]; void push(int i, int l, int r){ if(l != r){ add[i << 1] = min(add[i << 1], del[i]); add[i << 1] = max(add[i << 1], add[i]); del[i << 1] = min(del[i << 1], del[i]); del[i << 1] = max(del[i << 1], add[i]); add[i << 1 | 1] = min(add[i << 1 | 1], del[i]); add[i << 1 | 1] = max(add[i << 1 | 1], add[i]); del[i << 1 | 1] = min(del[i << 1 | 1], del[i]); del[i << 1 | 1] = max(del[i << 1 | 1], add[i]); } } void upd(int l, int r, int i, int from, int to, int val, int type){ push(i, from, to); if(from > r || to < l) return; if(from >= l && to <= r){ if(type == 1){ add[i] = max(add[i], val); del[i] = max(del[i], val); } else{ add[i] = min(add[i], val); del[i] = min(del[i], val); } push(i, from, to); return; } add[i] = 0, del[i] = INF; int mid = (from + to) >> 1; upd(l, r, i << 1, from, mid, val, type); upd(l, r, i << 1 | 1, mid + 1, to , val, type); } void pushall(int i, int l, int r){ if(l == r) return; push(i, l, r); int mid = (l + r) >> 1; pushall(i << 1, l, mid); pushall(i << 1 | 1, mid + 1, r); } void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){ memset(del, INF, sizeof del); for(int i = 0; i < k; i++){ upd(l[i], r[i], 1, 0, N - 1, h[i], op[i]); } pushall(1, 0, N - 1); for(int i = 0; i < n; i++){ ans[i] = add[i + N]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...