Submission #68065

#TimeUsernameProblemLanguageResultExecution timeMemory
68065spencercomptonPyramid Base (IOI08_pyramid_base)C++17
70 / 100
5044 ms138124 KiB
#include <bits/stdc++.h> using namespace std; int inf = 2000000069; class Node{ public: Node *l, *r; int mini, lazy, s, e; bool res; Node (int a, int b){ s = a; e = b; lazy = 0; mini = 0; res = false; if(s==e){ l = NULL; r = NULL; } else{ l = new Node(s,(s+e)/2); r = new Node((s+e)/2+1,e); } } void push(){ if(s!=e && res){ res = false; l->mini = 0; l->lazy = 0; l->res = true; r->mini = 0; r->lazy = 0; r->res = true; res = false; } if(s!=e && lazy!=0){ l->mini += lazy; l->lazy += lazy; r->mini += lazy; r->lazy += lazy; lazy = 0; } } void pull(){ if(s!=e){ mini = min(l->mini,r->mini); } } void add(int st, int en, int val){ if(st<=s && e <= en){ lazy += val; mini += val; return; } push(); if(st<=(s+e)/2){ l->add(st,en,val); } if(en>(s+e)/2){ r->add(st,en,val); } pull(); } // int gmin(int st, int en){ // if(st<=s && e <= en){ // return mini; // } // push(); // int ret = inf; // if(st<=(s+e)/2){ // ret = min(ret,l->gmin(st,en)); // } // if(en>(s+e)/2){ // ret = min(ret,r->gmin(st,en)); // } // return ret; // } }; class Obj{ public: int x, y1, y2, c; bool add; Obj(int a , int b, int d, int e, bool f){ x = a; y1 = b; y2 = d; c = e; add = f; } bool operator<(const Obj &o) const{ if(x!=o.x){ return x<o.x; } if(add && !o.add){ return true; } return false; } }; class Rect{ public: //get Rekt int x1, y1, x2, y2, c; Rect(int a, int b, int d, int e, int f){ x1 = a; y1 = b; x2 = d; y2 = e; c = f; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int col, row, bud, p; cin >> col >> row >> bud >> p; vector<Rect> li; for(int i = 0; i<p; i++){ int a, b,c,d,e; cin >> a >> b >> c >> d >> e; a--; b--; c--; d--; if(bud==0){ e = 1; } li.push_back(Rect(a,b,c,d,e)); } Node *t = new Node(0,row-1); int lo = 0; int hi = min(col,row); while(lo<hi){ int mid = (lo+hi+1)/2; bool ok = false; vector<Obj> li2; int f = 0; int s = row-mid; int last = col-mid; for(int i = 0; i<p; i++){ li2.push_back(Obj(max(0,li[i].x1-mid+1),max(0,li[i].y1-mid+1),li[i].y2,li[i].c,true)); if(li2.back().x>last){ li2.pop_back(); } li2.push_back(Obj(li[i].x2+1,max(0,li[i].y1-mid+1),li[i].y2,li[i].c,false)); if(li2.back().x>last){ li2.pop_back(); } } sort(li2.begin(),li2.end()); if(s<row-1){ t->add(s+1,row-1,bud+1); } bool zero = true; for(int i =0; i<li2.size() && !ok; i++){ if(zero && li2[i].x>0){ zero = false; ok |= t->mini<=bud; if(ok){ break; } } if(li2[i].x>last){ break; } if(li2[i].add){ t->add(li2[i].y1,li2[i].y2,li2[i].c); } else{ t->add(li2[i].y1,li2[i].y2,-li2[i].c); ok |= t->mini<=bud; } } if(!ok){ ok |= t->mini<=bud; } if(ok){ lo = mid; } else{ hi = mid-1; } t->res = true; t->mini = 0; t->lazy = 0; } cout << lo << endl; }

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:157:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i =0; i<li2.size() && !ok; i++){
                 ~^~~~~~~~~~~
pyramid_base.cpp:139:7: warning: unused variable 'f' [-Wunused-variable]
   int f = 0;
       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...