Submission #54067

#TimeUsernameProblemLanguageResultExecution timeMemory
54067sebinkimPyramid Base (IOI08_pyramid_base)C++14
0 / 100
5008 ms41908 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct obstacle{ int x, y1, y2, c; obstacle() {} obstacle(int x_, int y1_, int y2_, int c_) { x = x_, y1 = y1_, y2 = y2_, c = c_; } bool operator < (obstacle& c) { return x < c.x; } }; ll T[2202020], L[2202020]; obstacle K1[404040], K2[404040]; int n, m, c, k, sz; char in[1<<22]; char const*o; void init_in() { o = in; in[fread(in,1,sizeof(in)-4,stdin)]=0; } int readInt(){ unsigned u = 0, s = 0; while(*o && *o <= 32)++o; if (*o == '-')s = ~s, ++o; else if (*o == '+')++o; while(*o>='0' && *o<='9') u = (u<<3) + (u << 1) + (*o++ - '0'); return static_cast<int>( (u^s) + !!s) ; } void add(int p, int s, int e, int l, int r, int v) { if(r < s || e < l) return; if(l <= s && e <= r){ L[p] += v; return; } L[p<<1] += L[p], L[p<<1|1] += L[p]; L[p] = 0; add(p<<1, s, s+e>>1, l, r, v); add(p<<1|1, (s+e>>1)+1, e, l, r, v); T[p] = min(T[p<<1] + L[p<<1], T[p<<1|1] + L[p<<1|1]); } bool check(int t) { int i, j, p; bool f = false; if(K1[0].x-t+1 > 1) return 1; for(i=j=0;i<k;i++){ for(;j<k && K2[j].x < K1[i].x-t+1;j++){ add(1, 1, m-t+1, K2[j].y1-t+1, K2[j].y2, -K2[j].c); if(0 < K1[i].x-t && K2[j].x < K2[j+1].x && K2[j].x < K1[i].x-t) f |= (T[1] + L[1] <= c); } add(1, 1, m-t+1, K1[i].y1-t+1, K1[i].y2, K1[i].c); if(K1[i].x < K1[i+1].x && K1[i].x-t < K2[j].x && 0 < K1[i+1].x-t) f |= (T[1] + L[1] <= c); } for(;j<k;j++){ add(1, 1, m-t+1, K2[j].y1-t+1, K2[j].y2, -K2[j].c); if(K2[j].x < K2[j+1].x && K2[j].x <= n-t) f |= (T[1] + L[1] <= c); } return f; } int main() { //freopen("input.txt", "r", stdin); init_in(); int i, s, e; int x1, x2, y1, y2, z; n = readInt(); m = readInt(); c = readInt(); k = readInt(); for(sz=1;sz<=m;sz<<=1); for(i=0;i<k;i++){ x1 = readInt(); y1 = readInt(); x2 = readInt(); y2 = readInt(); z = readInt(); K1[i] = obstacle(x1, y1, y2, z); K2[i] = obstacle(x2, y1, y2, -z); } sort(K1, K1+k); sort(K2, K2+k); K1[k] = K2[k] = obstacle(1e9, 0, 0, 0); for(s=1,e=min(n,m); s<=e;){ if(check(s+e>>1)) s = (s+e>>1) + 1; else e = (s+e>>1) - 1; } printf("%d\n", s-1); return 0; }

Compilation message (stderr)

pyramid_base.cpp: In function 'void add(int, int, int, int, int, int)':
pyramid_base.cpp:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1, s, s+e>>1, l, r, v);
               ~^~
pyramid_base.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  add(p<<1|1, (s+e>>1)+1, e, l, r, v);
               ~^~
pyramid_base.cpp: In function 'bool check(int)':
pyramid_base.cpp:54:12: warning: unused variable 'p' [-Wunused-variable]
  int i, j, p;
            ^
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:107:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
            ~^~
pyramid_base.cpp:107:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s+e>>1)) s = (s+e>>1) + 1;
                          ~^~
pyramid_base.cpp:108:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s+e>>1) - 1;
             ~^~
#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...