Submission #1369967
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__",", __VA_ARGS__) void _dbg(string){cout<<endl;} template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);} template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} #define INF 1120000000 template<typename T> class BIT { private: vector<T> bit; int n; public: BIT(int _n) : n(_n) { bit = vector<T>(n+1, 0); //0初期化 } void add(int v, T a){ //vは0-indexed for(int x=v+1; x<=n; x += x&(-x)) bit[x] += a; } T sum(int v){ //vは0-indexed T ret=0; for(int x=v+1; x>0; x -= x&(-x)) ret += bit[x]; return ret; } int lower_bound(T w){ //w以上となる最小のsumの位置(0-indexed) if(w<=0) return 0; int x=0, d=0; while(n > (1<<d)) d++; for(int k=(1<<(d-1)); k>0; k/=2){ if(x+k<=n && bit[x+k]<w){ w -= bit[x+k]; x += k; } } return x; } }; // END class BIT int main(){ int n,m;long h; cin>>n>>m>>h; BIT<long> bit(n+m+1); BIT<int> idx(n+m+1); vector<long> vals(n+m); long total = 0; rep(i,n){ long d; cin>>d; bit.add(i,d); idx.add(i,1); total += d; vals[i]=d; } rep(i,m){ string s; long arg; cin>>s>>arg; vals[n+i]=arg; if(s[0]=='c'){ if(arg-h>=total){ cout << "miss" << endl; continue; } int l = bit.lower_bound(arg-h+1); int r = bit.lower_bound(arg+h); int il = idx.sum(l); int ir = idx.sum(r); // dbg(l,r,il,ir); if(il==ir){ cout << "go" << endl; bit.add(l, -vals[l]); idx.add(l, -1); total = bit.sum(n+m); } else { cout << "stop" << endl; } } else { bit.add(n+i,arg); idx.add(n+i,1); total += arg; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - だるま落とし |
User | tossy |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2443 Byte |
Status | WA |
Exec Time | 283 ms |
Memory | 4480 KB |
Judge Result
Set Name | small | large | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 20 | 0 / 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 | 1 ms | 256 KB |
large/case_002.txt | AC | 1 ms | 256 KB |
large/case_003.txt | AC | 1 ms | 256 KB |
large/case_005.txt | AC | 1 ms | 256 KB |
large/case_006.txt | WA | 1 ms | 256 KB |
large/case_007.txt | AC | 1 ms | 256 KB |
large/case_008.txt | AC | 4 ms | 256 KB |
large/case_009.txt | AC | 4 ms | 256 KB |
large/case_010.txt | AC | 4 ms | 256 KB |
large/case_011.txt | AC | 4 ms | 256 KB |
large/case_012.txt | WA | 4 ms | 256 KB |
large/case_013.txt | AC | 4 ms | 256 KB |
large/case_014.txt | AC | 3 ms | 256 KB |
large/case_015.txt | AC | 4 ms | 256 KB |
large/case_016.txt | AC | 4 ms | 256 KB |
large/case_017.txt | AC | 4 ms | 256 KB |
large/case_018.txt | AC | 2 ms | 256 KB |
large/case_019.txt | AC | 4 ms | 256 KB |
large/case_020.txt | AC | 4 ms | 256 KB |
large/case_021.txt | AC | 4 ms | 256 KB |
large/case_022.txt | WA | 4 ms | 256 KB |
large/case_023.txt | WA | 4 ms | 256 KB |
large/case_024.txt | WA | 4 ms | 256 KB |
large/case_025.txt | WA | 4 ms | 256 KB |
large/case_026.txt | WA | 4 ms | 256 KB |
large/case_027.txt | WA | 4 ms | 256 KB |
large/case_028.txt | WA | 4 ms | 256 KB |
large/case_029.txt | WA | 4 ms | 256 KB |
large/case_030.txt | WA | 4 ms | 256 KB |
large/case_031.txt | WA | 4 ms | 256 KB |
large/case_032.txt | WA | 4 ms | 256 KB |
large/case_033.txt | WA | 4 ms | 256 KB |
large/case_034.txt | WA | 4 ms | 256 KB |
large/case_035.txt | WA | 4 ms | 256 KB |
large/case_036.txt | WA | 4 ms | 256 KB |
large/case_037.txt | WA | 4 ms | 256 KB |
large/large_case_000.txt | AC | 244 ms | 4352 KB |
large/large_case_001.txt | AC | 248 ms | 4352 KB |
large/large_case_002.txt | AC | 249 ms | 4352 KB |
large/large_case_003.txt | AC | 247 ms | 4352 KB |
large/large_case_004.txt | AC | 247 ms | 4352 KB |
large/large_case_005.txt | AC | 247 ms | 4352 KB |
large/large_case_006.txt | AC | 241 ms | 4352 KB |
large/large_case_007.txt | AC | 246 ms | 4352 KB |
large/large_case_008.txt | AC | 246 ms | 4352 KB |
large/large_case_009.txt | AC | 244 ms | 4352 KB |
large/large_case_010.txt | AC | 112 ms | 4096 KB |
large/large_case_011.txt | AC | 238 ms | 4352 KB |
large/large_case_012.txt | AC | 243 ms | 4352 KB |
large/large_case_013.txt | AC | 251 ms | 4352 KB |
large/large_case_014.txt | AC | 278 ms | 4480 KB |
large/large_case_015.txt | AC | 278 ms | 4480 KB |
large/large_case_016.txt | AC | 275 ms | 4480 KB |
large/large_case_017.txt | AC | 277 ms | 4480 KB |
large/large_case_018.txt | AC | 275 ms | 4480 KB |
large/large_case_019.txt | AC | 276 ms | 4480 KB |
large/large_case_020.txt | AC | 277 ms | 4480 KB |
large/large_case_021.txt | AC | 278 ms | 4480 KB |
large/large_case_022.txt | AC | 276 ms | 4480 KB |
large/large_case_023.txt | AC | 275 ms | 4480 KB |
large/large_case_024.txt | AC | 277 ms | 4480 KB |
large/large_case_025.txt | AC | 277 ms | 4480 KB |
large/large_case_026.txt | AC | 275 ms | 4480 KB |
large/large_case_027.txt | AC | 283 ms | 4480 KB |
large/large_case_028.txt | AC | 280 ms | 4480 KB |
large/large_case_029.txt | AC | 276 ms | 4480 KB |
small/case_000.txt | AC | 1 ms | 256 KB |
small/case_002.txt | AC | 1 ms | 256 KB |
small/case_003.txt | AC | 1 ms | 256 KB |
small/case_005.txt | AC | 1 ms | 256 KB |
small/case_006.txt | WA | 1 ms | 256 KB |
small/case_007.txt | AC | 1 ms | 256 KB |
small/case_008.txt | AC | 4 ms | 256 KB |
small/case_009.txt | AC | 4 ms | 256 KB |
small/case_010.txt | AC | 4 ms | 256 KB |
small/case_011.txt | AC | 4 ms | 256 KB |
small/case_012.txt | WA | 4 ms | 256 KB |
small/case_013.txt | AC | 4 ms | 256 KB |
small/case_014.txt | AC | 4 ms | 256 KB |
small/case_015.txt | AC | 4 ms | 256 KB |
small/case_016.txt | AC | 4 ms | 256 KB |
small/case_017.txt | AC | 4 ms | 256 KB |
small/case_018.txt | AC | 2 ms | 256 KB |
small/case_019.txt | AC | 4 ms | 256 KB |
small/case_020.txt | AC | 3 ms | 256 KB |
small/case_021.txt | AC | 4 ms | 256 KB |
small/case_022.txt | WA | 4 ms | 256 KB |
small/case_023.txt | WA | 4 ms | 256 KB |
small/case_024.txt | WA | 4 ms | 256 KB |
small/case_025.txt | WA | 4 ms | 256 KB |
small/case_026.txt | WA | 4 ms | 256 KB |
small/case_027.txt | WA | 4 ms | 256 KB |
small/case_028.txt | WA | 4 ms | 256 KB |
small/case_029.txt | WA | 4 ms | 256 KB |
small/case_030.txt | WA | 4 ms | 256 KB |
small/case_031.txt | WA | 4 ms | 256 KB |
small/case_032.txt | WA | 4 ms | 256 KB |
small/case_033.txt | WA | 4 ms | 256 KB |
small/case_034.txt | WA | 4 ms | 256 KB |
small/case_035.txt | WA | 4 ms | 256 KB |
small/case_036.txt | WA | 4 ms | 256 KB |
small/case_037.txt | WA | 4 ms | 256 KB |