Submission #978150

#TimeUsernameProblemLanguageResultExecution timeMemory
978150shezittWall (IOI14_wall)C++14
24 / 100
266 ms25864 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; #define fore(a, b, c) for(int a=b; a<c; ++a) #define sz(x) (int) x.size() #define all(x) x.begin(), x.end() #define ii pair<int,int> #define vi vector<int> struct mxtree { vi t; vi lazy; int n; mxtree(int n) : n(n) { t.assign(4*n, 0); lazy.assign(4*n, -1); } void update(int i, int tl, int tr, int l, int r, int val){ if(l <= tl && tr <= r){ if(lazy[i] > -1){ lazy[i] = max(lazy[i], val); } else { lazy[i] = val; } return; } if(r < tl or tr < l){ return; } int tm = (tl + tr) / 2; update(2*i+1, tl, tm, l, r, val); update(2*i+2, tm+1, tr, l, r, val); } void update(int l, int r, int val){ update(0, 0, n-1, l, r, val); } void push(int i, int tl, int tr){ lazy[2*i+1] = (lazy[2*i+1] == -1 ? lazy[i] : max(lazy[2*i+1], lazy[i])); lazy[2*i+2] = (lazy[2*i+2] == -1 ? lazy[i] : max(lazy[2*i+2], lazy[i])); lazy[i] = -1; } int query(int i, int tl, int tr, int idx){ if(tl == tr){ t[i] = max(t[i], lazy[i]); return t[i]; } push(i, tl, tr); int tm = (tl + tr) / 2; if(idx <= tm){ return query(2*i+1, tl, tm, idx); } else { return query(2*i+2, tm+1, tr, idx); } } int query(int idx){ return query(0, 0, n-1, idx); } }; struct mntree { vi t; vi lazy; int n; vi arr; mntree(int a[], int n) : n(n) { arr.assign(n, 0); fore(i, 0, n){ arr[i] = a[i]; } t.assign(4*n, 0); lazy.assign(4*n, -1); init(0, 0, n-1); } void init(int i, int tl, int tr){ if(tl == tr){ t[i] = arr[tl]; return; } int tm = (tl + tr) / 2; init(2*i+1, tl, tm); init(2*i+2, tm+1, tr); } void update(int i, int tl, int tr, int l, int r, int val){ if(l <= tl && tr <= r){ if(lazy[i] > -1){ lazy[i] = min(lazy[i], val); } else { lazy[i] = val; } return; } if(r < tl or tr < l){ return; } int tm = (tl + tr) / 2; update(2*i+1, tl, tm, l, r, val); update(2*i+2, tm+1, tr, l, r, val); } void update(int l, int r, int val){ update(0, 0, n-1, l, r, val); } void push(int i, int tl, int tr){ if(lazy[i] == -1) return; lazy[2*i+1] = (lazy[2*i+1] == -1 ? lazy[i] : min(lazy[2*i+1], lazy[i])); lazy[2*i+2] = (lazy[2*i+2] == -1 ? lazy[i] : min(lazy[2*i+2], lazy[i])); lazy[i] = -1; } int query(int i, int tl, int tr, int idx){ if(tl == tr){ // leaf t[i] = min(t[i], lazy[i]); return t[i]; } push(i, tl, tr); int tm = (tl + tr) / 2; if(idx <= tm){ return query(2*i+1, tl, tm, idx); } else { return query(2*i+2, tm+1, tr, idx); } } int query(int idx){ return query(0, 0, n-1, idx); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ mxtree Tmax(n); fore(i, 0, k){ if(op[i] == 2) break; Tmax.update(left[i], right[i], height[i]); } fore(i, 0, n){ finalHeight[i] = Tmax.query(i); } mntree Tmin(finalHeight, n); vi tmp(n+1); fore(i, 0, k){ if(op[i] == 1) continue; Tmin.update(left[i], right[i], height[i]); tmp[right[i]+1]--; tmp[left[i]]++; } fore(i, 1, n+1){ tmp[i] += tmp[i-1]; } fore(i, 0, n){ if(tmp[i] > 0){ finalHeight[i] = Tmin.query(i); } } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...