Submission #854549

#TimeUsernameProblemLanguageResultExecution timeMemory
854549KN200711Wall (IOI14_wall)C++14
100 / 100
649 ms79984 KiB
#include "wall.h" # include <bits/stdc++.h> using namespace std; const int MXN = 2e6; int bl[4 * MXN + 1], br[4 * MXN + 1]; void build(int lf, int rg, int nd) { bl[nd] = br[nd] = 0; if(lf != rg) { int mid = (lf + rg) / 2; build(lf, mid, 2*nd+1); build(mid+1, rg, 2*nd+2); } } void upd_lazy(int lf, int rg, int nd) { if(lf != rg) { int mid = (lf + rg) / 2; if(bl[2*nd+1] > bl[nd]) bl[2*nd+1] = bl[nd]; else if(bl[2*nd+1] < br[nd]) bl[2*nd+1] = br[nd]; if(bl[2*nd+2] > bl[nd]) bl[2*nd+2] = bl[nd]; else if(bl[2*nd+2] < br[nd]) bl[2*nd+2] = br[nd]; if(br[2*nd+1] > bl[nd]) br[2*nd+1] = bl[nd]; else if(br[2*nd+1] < br[nd]) br[2*nd+1] = br[nd]; if(br[2*nd+2] > bl[nd]) br[2*nd+2] = bl[nd]; else if(br[2*nd+2] < br[nd]) br[2*nd+2] = br[nd]; } } void upd(int lf, int rg, int nd, int clf, int crg, int op, int pos) { upd_lazy(lf, rg, nd); if(clf > rg || lf > crg) return; else if(clf <= lf && rg <= crg) { if(op == 1) { // cout<<"upd : "<<lf<<" "<<rg<<" "<<nd<<" "<<bl[nd]<<" "<<pos<<endl; if(bl[nd] <= pos) bl[nd] = br[nd] = pos; else if(br[nd] <= pos) br[nd] = pos; } else { if(br[nd] >= pos) bl[nd] = br[nd] = pos; else if(bl[nd] >= pos) bl[nd] = pos; } upd_lazy(lf, rg, nd); } else { int mid = (lf + rg) / 2; upd(lf, mid, 2*nd+1, clf, crg, op, pos); upd(mid+1, rg, 2*nd+2, clf, crg, op, pos); bl[nd] = max(bl[2*nd+1], bl[2*nd+2]); br[nd] = min(br[2*nd+1], br[2*nd+2]); } } int val[MXN + 1]; void fn(int lf, int rg, int nd) { upd_lazy(lf, rg, nd); if(lf == rg) { val[lf] = bl[nd]; } else { int mid = (lf + rg) / 2; fn(lf, mid, 2*nd+1); fn(mid+1, rg, 2*nd+2); } } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ build(0, n-1, 0); for(int i=0;i<k;i++) { upd(0, n-1, 0, left[i], right[i], op[i], height[i]); } fn(0, n-1, 0); for(int i=0;i<n;i++) finalHeight[i] = val[i]; }

Compilation message (stderr)

wall.cpp: In function 'void upd_lazy(int, int, int)':
wall.cpp:19:7: warning: unused variable 'mid' [-Wunused-variable]
   19 |   int mid = (lf + rg) / 2;
      |       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...