Submission #1062732

#TimeUsernameProblemLanguageResultExecution timeMemory
1062732NemanjaSo2005Wall (IOI14_wall)C++17
100 / 100
390 ms166024 KiB
#include<bits/stdc++.h> #include "wall.h" #define ll long long #define f first #define s second using namespace std; const int maxn=2e6+5; int N,Q,K,tip[maxn],vis[maxn]; vector<int> poc[maxn],kraj[maxn]; struct slog{ int res=0,minr=1e9; } st[maxn]; slog spoj(slog a,slog b){ slog ret; ret.minr=min(a.minr,b.minr); ret.res=max(b.res,min(a.res,b.minr)); return ret; } void update(int gde,slog sta){ gde+=K; st[gde]=sta; gde/=2; while(gde){ st[gde]=spoj(st[gde*2],st[gde*2+1]); gde/=2; } return; } void akt(int x){ slog sta; if(tip[x]==1) sta.res=vis[x]; else sta.minr=vis[x]; update(x,sta); } void deakt(int x){ slog a; update(x,a); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ N=n; Q=k; K=1; while(K<Q) K<<=1; for(int i=0;i<Q;i++){ poc[left[i]].push_back(i); kraj[right[i]+1].push_back(i); tip[i]=op[i]; vis[i]=height[i]; } for(int i=0;i<N;i++){ for(int x:poc[i]) akt(x); for(int x:kraj[i]) deakt(x); finalHeight[i]=st[1].res; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...