Submission #986906

#TimeUsernameProblemLanguageResultExecution timeMemory
986906vjudge1Wall (IOI14_wall)C++17
100 / 100
500 ms106704 KiB
#include <bits/stdc++.h> #define INF 1e9 using namespace std; const int N = 5e5 + 5; const int M = 2e6 + 5; pair<int,int> seg[N*4]; struct wall { int h, ty, ord; }; pair<int,int> mer(pair<int,int> a, pair<int,int> b) { if(a.second < b.first) { return {b.first,b.first}; } else if(a.first > b.second) { return {b.second,b.second}; } else { return {max(a.first,b.first),min(a.second,b.second)}; } return {0,INF}; } void Build(int x, int l, int r) { if(l == r) { seg[x].first = 0; seg[x].second = INF; } else { int mid = (l+r)/2; Build(x*2,l,mid); Build(x*2+1,mid+1,r); seg[x].first = 0; seg[x].second = INF; } } void Update(int x, int l, int r, int pos, int ty, int val) { if(l == r) { if(val < 0) { // cout << "aa" << endl; if(ty == 1) seg[x].first = 0; else seg[x].second = INF; } else { // cout << "bb" << endl; if(ty == 1) seg[x].first = val; else seg[x].second = val; } // cout << seg[x].first << ' ' << seg[x].second << endl; } else { int mid = (l+r)/2; if(pos <= mid) Update(x*2,l,mid,pos,ty,val); else Update(x*2+1,mid+1,r,pos,ty,val); pair<int,int> pp = mer(seg[x*2],seg[x*2+1]); // cout << l << ' ' << r << 'k' << endl; // cout << pp.first << ' ' << pp.second << 'a' << endl; seg[x] = pp; } } vector<wall> v[M]; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { for(int i = 0; i < k; i++) { if(op[i] == 1) { wall cur; cur.h = height[i]+1; cur.ty = 1; cur.ord = i+1; v[left[i]].push_back(cur); cur.h *= -1; v[right[i]+1].push_back(cur); } else { wall cur; cur.h = height[i]+1; cur.ty = 2; cur.ord = i+1; v[left[i]].push_back(cur); cur.h *= -1; v[right[i]+1].push_back(cur); } } for(int i = 0; i < n; i++) finalHeight[i] = 1; Build(1,1,k+1); for(int i = 0; i < n; i++) { for(auto j : v[i]) { // cout << "JJJJJJJJJJJJJ" << endl; // cout << j.ord << ' ' << j.h << 'p' << endl; Update(1,1,k+1,j.ord,j.ty,j.h); } if(finalHeight[i] < seg[1].first) finalHeight[i] = seg[1].first; if(finalHeight[i] > seg[1].second) finalHeight[i] = seg[1].second; } for(int i = 0; i < n; i++) finalHeight[i]--; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...