Submission #8581

#TimeUsernameProblemLanguageResultExecution timeMemory
8581cki86201Wall (IOI14_wall)C++98
100 / 100
1120 ms65880 KiB
#include "wall.h" #include<algorithm> using namespace std; int T[1<<22], P[1<<22], M[1<<22]; inline void update_node(int rt, int mode, int h){ if(mode == 1){ T[rt] = max(T[rt], h); P[rt] = max(P[rt], h); M[rt] = max(M[rt], P[rt]); } else{ T[rt] = min(T[rt], h); M[rt] = min(M[rt], h); P[rt] = min(P[rt], M[rt]); } } void pushdown(int rt){ update_node(rt<<1, 2, M[rt]); update_node(rt<<1, 1, P[rt]); update_node(rt<<1|1, 2, M[rt]); update_node(rt<<1|1, 1, P[rt]); P[rt] = 0, M[rt] = 1e5 + 5; } void update(int rt, int s, int d, int mode, int l, int r, int h){ if(l <= s && d <= r){ update_node(rt, mode, h); return; } pushdown(rt); int m = (s+d)>>1; if(l<=m)update(rt<<1, s, m, mode, l, r, h); if(m<r)update(rt<<1|1, m+1, d, mode, l, r, h); } void get_ans(int rt, int s, int d, int &cnt, int arr[]){ if(s == d){ arr[cnt++] = T[rt]; return; } int m = (s+d)>>1; pushdown(rt); get_ans(rt<<1, s, m, cnt, arr); get_ans(rt<<1|1, m+1, d, cnt, arr); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ int i; for(i=0;i<1<<22;i++)M[i] = 1e5 + 5; for(i=0;i<k;i++)update(1, 0, n-1, op[i], left[i], right[i], height[i]); int cnt = 0; get_ans(1, 0, n-1, cnt, finalHeight); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...