Submission #843391
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct SumSegTree{ long n; vector<ll> dat; //初期化 SumSegTree(long _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,0); } //k番目(0-indexed)の値をaに変更 void update(long k, ll a){ k+=n-1; dat[k]=a; //更新 while(k>0){ k=(k-1)/2; dat[k]=dat[2*k+1]+dat[2*k+2]; } } //内部的に投げられるクエリ ll _query(long a, long b, long k, long l, long r){ if(r<=a || b<=l) return 0; if(a<=l && r<=b) return dat[k]; else{ ll vl=_query(a,b,2*k+1,l,(l+r)/2); ll vr=_query(a,b,2*k+2,(l+r)/2,r); return vl+vr; } } //[a,b)の和を求める ll query(long a, long b){ return _query(a,b,0,0,n); } ll get(long a){ return query(0,a+1)-query(0,a); } }; int main() { int n,m,h; cin >>n >>m >>h; SumSegTree s(200001); rep(i,n) { ll a; scanf(" %lld", &a); s.update(i,a); } rep(Q,m) { char op[16]; ll arg; scanf("%s %lld", op, &arg); if(op[0]=='a') { s.update(n,arg); ++n; } else { int l=0, r=n+1; while(r-l>1) { int mid=(l+r)/2; if(s.query(0,mid)>arg-h) r=mid; else l=mid; } if(l==n) { printf("miss\n"); continue; } if(l+1<n && s.query(0,l+1)<arg+h) { printf("stop\n"); continue; } printf("go\n"); s.update(l,0); while(n>0 && s.query(0,n)-s.query(0,n-1)==0) --n; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - だるま落とし |
User | imulan |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 2242 Byte |
Status | AC |
Exec Time | 306 ms |
Memory | 5272 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:59:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf(" %lld", &a); ^ ./Main.cpp:67:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s %lld", op, &arg); ^
Judge Result
Set Name | small | large | ||||
---|---|---|---|---|---|---|
Score / Max Score | 20 / 20 | 80 / 80 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | small/case_000.txt, small/case_002.txt, small/case_003.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_016.txt, small/case_017.txt, small/case_018.txt, small/case_019.txt, small/case_020.txt, small/case_021.txt, small/case_022.txt, small/case_023.txt, small/case_024.txt, small/case_025.txt, small/case_026.txt, small/case_027.txt, small/case_028.txt, small/case_029.txt, small/case_030.txt, small/case_031.txt, small/case_032.txt, small/case_033.txt, small/case_034.txt, small/case_035.txt, small/case_036.txt, small/case_037.txt |
large | large/case_000.txt, large/case_002.txt, large/case_003.txt, large/case_005.txt, large/case_006.txt, large/case_007.txt, large/case_008.txt, large/case_009.txt, large/case_010.txt, large/case_011.txt, large/case_012.txt, large/case_013.txt, large/case_014.txt, large/case_015.txt, large/case_016.txt, large/case_017.txt, large/case_018.txt, large/case_019.txt, large/case_020.txt, large/case_021.txt, large/case_022.txt, large/case_023.txt, large/case_024.txt, large/case_025.txt, large/case_026.txt, large/case_027.txt, large/case_028.txt, large/case_029.txt, large/case_030.txt, large/case_031.txt, large/case_032.txt, large/case_033.txt, large/case_034.txt, large/case_035.txt, large/case_036.txt, large/case_037.txt, large/large_case_000.txt, large/large_case_001.txt, large/large_case_002.txt, large/large_case_003.txt, large/large_case_004.txt, large/large_case_005.txt, large/large_case_006.txt, large/large_case_007.txt, large/large_case_008.txt, large/large_case_009.txt, large/large_case_010.txt, large/large_case_011.txt, large/large_case_012.txt, large/large_case_013.txt, large/large_case_014.txt, large/large_case_015.txt, large/large_case_016.txt, large/large_case_017.txt, large/large_case_018.txt, large/large_case_019.txt, large/large_case_020.txt, large/large_case_021.txt, large/large_case_022.txt, large/large_case_023.txt, large/large_case_024.txt, large/large_case_025.txt, large/large_case_026.txt, large/large_case_027.txt, large/large_case_028.txt, large/large_case_029.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/case_000.txt | AC | 92 ms | 5088 KB |
large/case_002.txt | AC | 88 ms | 5220 KB |
large/case_003.txt | AC | 36 ms | 5016 KB |
large/case_005.txt | AC | 35 ms | 5020 KB |
large/case_006.txt | AC | 33 ms | 5144 KB |
large/case_007.txt | AC | 34 ms | 5140 KB |
large/case_008.txt | AC | 37 ms | 5144 KB |
large/case_009.txt | AC | 37 ms | 5020 KB |
large/case_010.txt | AC | 38 ms | 5140 KB |
large/case_011.txt | AC | 37 ms | 5020 KB |
large/case_012.txt | AC | 37 ms | 5144 KB |
large/case_013.txt | AC | 37 ms | 5020 KB |
large/case_014.txt | AC | 35 ms | 5144 KB |
large/case_015.txt | AC | 38 ms | 5052 KB |
large/case_016.txt | AC | 35 ms | 5152 KB |
large/case_017.txt | AC | 37 ms | 5148 KB |
large/case_018.txt | AC | 35 ms | 5144 KB |
large/case_019.txt | AC | 37 ms | 5136 KB |
large/case_020.txt | AC | 37 ms | 5148 KB |
large/case_021.txt | AC | 37 ms | 5016 KB |
large/case_022.txt | AC | 38 ms | 5016 KB |
large/case_023.txt | AC | 36 ms | 5272 KB |
large/case_024.txt | AC | 35 ms | 5016 KB |
large/case_025.txt | AC | 37 ms | 5144 KB |
large/case_026.txt | AC | 37 ms | 5148 KB |
large/case_027.txt | AC | 37 ms | 5084 KB |
large/case_028.txt | AC | 38 ms | 5148 KB |
large/case_029.txt | AC | 38 ms | 5144 KB |
large/case_030.txt | AC | 37 ms | 5084 KB |
large/case_031.txt | AC | 39 ms | 5084 KB |
large/case_032.txt | AC | 39 ms | 5140 KB |
large/case_033.txt | AC | 40 ms | 5076 KB |
large/case_034.txt | AC | 39 ms | 5080 KB |
large/case_035.txt | AC | 36 ms | 5048 KB |
large/case_036.txt | AC | 39 ms | 5084 KB |
large/case_037.txt | AC | 38 ms | 5148 KB |
large/large_case_000.txt | AC | 294 ms | 5148 KB |
large/large_case_001.txt | AC | 302 ms | 5016 KB |
large/large_case_002.txt | AC | 298 ms | 5144 KB |
large/large_case_003.txt | AC | 300 ms | 5084 KB |
large/large_case_004.txt | AC | 302 ms | 5140 KB |
large/large_case_005.txt | AC | 304 ms | 5084 KB |
large/large_case_006.txt | AC | 304 ms | 5084 KB |
large/large_case_007.txt | AC | 306 ms | 5080 KB |
large/large_case_008.txt | AC | 304 ms | 5076 KB |
large/large_case_009.txt | AC | 304 ms | 5084 KB |
large/large_case_010.txt | AC | 96 ms | 5140 KB |
large/large_case_011.txt | AC | 252 ms | 5152 KB |
large/large_case_012.txt | AC | 286 ms | 5080 KB |
large/large_case_013.txt | AC | 299 ms | 5048 KB |
large/large_case_014.txt | AC | 280 ms | 5088 KB |
large/large_case_015.txt | AC | 281 ms | 5052 KB |
large/large_case_016.txt | AC | 280 ms | 5144 KB |
large/large_case_017.txt | AC | 283 ms | 5140 KB |
large/large_case_018.txt | AC | 278 ms | 5016 KB |
large/large_case_019.txt | AC | 280 ms | 5084 KB |
large/large_case_020.txt | AC | 279 ms | 5084 KB |
large/large_case_021.txt | AC | 279 ms | 5080 KB |
large/large_case_022.txt | AC | 281 ms | 5148 KB |
large/large_case_023.txt | AC | 281 ms | 5080 KB |
large/large_case_024.txt | AC | 280 ms | 5144 KB |
large/large_case_025.txt | AC | 282 ms | 5144 KB |
large/large_case_026.txt | AC | 301 ms | 5020 KB |
large/large_case_027.txt | AC | 282 ms | 5136 KB |
large/large_case_028.txt | AC | 282 ms | 5144 KB |
large/large_case_029.txt | AC | 281 ms | 5080 KB |
small/case_000.txt | AC | 37 ms | 5148 KB |
small/case_002.txt | AC | 36 ms | 5144 KB |
small/case_003.txt | AC | 34 ms | 5260 KB |
small/case_005.txt | AC | 36 ms | 5020 KB |
small/case_006.txt | AC | 35 ms | 5148 KB |
small/case_007.txt | AC | 36 ms | 5168 KB |
small/case_008.txt | AC | 38 ms | 5148 KB |
small/case_009.txt | AC | 38 ms | 5016 KB |
small/case_010.txt | AC | 37 ms | 5144 KB |
small/case_011.txt | AC | 37 ms | 5148 KB |
small/case_012.txt | AC | 40 ms | 5076 KB |
small/case_013.txt | AC | 38 ms | 5144 KB |
small/case_014.txt | AC | 37 ms | 5020 KB |
small/case_015.txt | AC | 38 ms | 5148 KB |
small/case_016.txt | AC | 38 ms | 5148 KB |
small/case_017.txt | AC | 38 ms | 5016 KB |
small/case_018.txt | AC | 36 ms | 5016 KB |
small/case_019.txt | AC | 37 ms | 5020 KB |
small/case_020.txt | AC | 37 ms | 5148 KB |
small/case_021.txt | AC | 37 ms | 5016 KB |
small/case_022.txt | AC | 38 ms | 5084 KB |
small/case_023.txt | AC | 35 ms | 5260 KB |
small/case_024.txt | AC | 35 ms | 5148 KB |
small/case_025.txt | AC | 36 ms | 5020 KB |
small/case_026.txt | AC | 38 ms | 5016 KB |
small/case_027.txt | AC | 38 ms | 5044 KB |
small/case_028.txt | AC | 51 ms | 5148 KB |
small/case_029.txt | AC | 39 ms | 5048 KB |
small/case_030.txt | AC | 37 ms | 5080 KB |
small/case_031.txt | AC | 38 ms | 5048 KB |
small/case_032.txt | AC | 38 ms | 5084 KB |
small/case_033.txt | AC | 38 ms | 5012 KB |
small/case_034.txt | AC | 39 ms | 5080 KB |
small/case_035.txt | AC | 41 ms | 5084 KB |
small/case_036.txt | AC | 38 ms | 5076 KB |
small/case_037.txt | AC | 40 ms | 5016 KB |