Submission #3624732
Source Code Expand
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <string> #include <set> #include <map> #define REP(i,n) for(ll i = 0; i < (ll)n; i++) #define INF 1000000000000000 using namespace std; typedef long long ll; typedef double db; typedef string str; const ll max_b = 200002; ll bit[max_b]; ll sum(ll i){ ll s = 0; while(i>0){ s += bit[i]; i -= i & -i; } return s; } void add(ll i, ll x){ while(i<=max_b){ bit[i]+=x; i+=i&-i; } } pair<ll,ll> search(ll x, bool lower_bound){ ll lb = 0, ub = max_b, mid; while(ub-lb>1){ mid = (ub+lb)/2; if(sum(mid)<x) lb = mid; else if(sum(mid)>x) ub = mid; else if(lower_bound) ub = mid; else lb = mid; } return pair<ll,ll>(lb,ub); } int main(){ ll n,m,h; cin >> n >> m >> h; REP(i,n){ ll a; cin >> a; add(i+1,a); } ll index = n+1; vector<str> ans; REP(i,m){ //printf("%d %d %d %d %d %d %d %d\n",sum(0),sum(1),sum(2),sum(3),sum(4),sum(5),sum(6),sum(7)); str opr; ll arg; cin >> opr >> arg; if(opr=="add"){ add(i+n+1,arg); index++; }else{ ll left = search(arg-h,false).second; ll right = search(arg+h,true).second; //cout << left << " "<< right << endl; //printf("%ld %ld\n",left,right); if(left==max_b){ //cout << "miss" << endl; ans.push_back("miss"); }else if(sum(left)==sum(right)){ //cout << "go" << endl; ans.push_back("go"); add(left,-sum(left)+sum(left-1)); }else{ //cout << "stop" << endl; ans.push_back("stop"); } } } for(str s:ans){ cout << s << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - だるま落とし |
User | nexusuica |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1796 Byte |
Status | AC |
Exec Time | 282 ms |
Memory | 5880 KB |
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 | 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 | AC | 1 ms | 256 KB |
large/case_007.txt | AC | 1 ms | 256 KB |
large/case_008.txt | AC | 3 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 | 384 KB |
large/case_012.txt | AC | 4 ms | 384 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 | 3 ms | 256 KB |
large/case_017.txt | AC | 4 ms | 384 KB |
large/case_018.txt | AC | 2 ms | 256 KB |
large/case_019.txt | AC | 3 ms | 256 KB |
large/case_020.txt | AC | 3 ms | 256 KB |
large/case_021.txt | AC | 3 ms | 256 KB |
large/case_022.txt | AC | 4 ms | 384 KB |
large/case_023.txt | AC | 4 ms | 384 KB |
large/case_024.txt | AC | 4 ms | 384 KB |
large/case_025.txt | AC | 4 ms | 384 KB |
large/case_026.txt | AC | 4 ms | 384 KB |
large/case_027.txt | AC | 4 ms | 384 KB |
large/case_028.txt | AC | 4 ms | 384 KB |
large/case_029.txt | AC | 4 ms | 384 KB |
large/case_030.txt | AC | 4 ms | 384 KB |
large/case_031.txt | AC | 4 ms | 384 KB |
large/case_032.txt | AC | 4 ms | 384 KB |
large/case_033.txt | AC | 4 ms | 384 KB |
large/case_034.txt | AC | 4 ms | 384 KB |
large/case_035.txt | AC | 4 ms | 384 KB |
large/case_036.txt | AC | 4 ms | 384 KB |
large/case_037.txt | AC | 4 ms | 384 KB |
large/large_case_000.txt | AC | 242 ms | 4728 KB |
large/large_case_001.txt | AC | 244 ms | 4728 KB |
large/large_case_002.txt | AC | 241 ms | 4728 KB |
large/large_case_003.txt | AC | 243 ms | 4728 KB |
large/large_case_004.txt | AC | 240 ms | 4728 KB |
large/large_case_005.txt | AC | 242 ms | 4728 KB |
large/large_case_006.txt | AC | 237 ms | 4728 KB |
large/large_case_007.txt | AC | 239 ms | 4728 KB |
large/large_case_008.txt | AC | 240 ms | 4728 KB |
large/large_case_009.txt | AC | 242 ms | 4728 KB |
large/large_case_010.txt | AC | 112 ms | 1792 KB |
large/large_case_011.txt | AC | 222 ms | 4728 KB |
large/large_case_012.txt | AC | 237 ms | 4728 KB |
large/large_case_013.txt | AC | 243 ms | 4728 KB |
large/large_case_014.txt | AC | 277 ms | 5880 KB |
large/large_case_015.txt | AC | 279 ms | 5880 KB |
large/large_case_016.txt | AC | 276 ms | 5880 KB |
large/large_case_017.txt | AC | 281 ms | 5880 KB |
large/large_case_018.txt | AC | 276 ms | 5880 KB |
large/large_case_019.txt | AC | 278 ms | 5880 KB |
large/large_case_020.txt | AC | 276 ms | 5880 KB |
large/large_case_021.txt | AC | 277 ms | 5880 KB |
large/large_case_022.txt | AC | 279 ms | 5880 KB |
large/large_case_023.txt | AC | 277 ms | 5880 KB |
large/large_case_024.txt | AC | 276 ms | 5880 KB |
large/large_case_025.txt | AC | 282 ms | 5880 KB |
large/large_case_026.txt | AC | 275 ms | 5880 KB |
large/large_case_027.txt | AC | 276 ms | 5880 KB |
large/large_case_028.txt | AC | 278 ms | 5880 KB |
large/large_case_029.txt | AC | 281 ms | 5880 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 | AC | 1 ms | 256 KB |
small/case_007.txt | AC | 1 ms | 256 KB |
small/case_008.txt | AC | 3 ms | 256 KB |
small/case_009.txt | AC | 3 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 | AC | 4 ms | 384 KB |
small/case_013.txt | AC | 4 ms | 256 KB |
small/case_014.txt | AC | 3 ms | 256 KB |
small/case_015.txt | AC | 4 ms | 256 KB |
small/case_016.txt | AC | 3 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 | 3 ms | 256 KB |
small/case_020.txt | AC | 3 ms | 256 KB |
small/case_021.txt | AC | 3 ms | 256 KB |
small/case_022.txt | AC | 4 ms | 384 KB |
small/case_023.txt | AC | 4 ms | 384 KB |
small/case_024.txt | AC | 4 ms | 384 KB |
small/case_025.txt | AC | 4 ms | 384 KB |
small/case_026.txt | AC | 4 ms | 384 KB |
small/case_027.txt | AC | 4 ms | 384 KB |
small/case_028.txt | AC | 4 ms | 384 KB |
small/case_029.txt | AC | 4 ms | 384 KB |
small/case_030.txt | AC | 4 ms | 384 KB |
small/case_031.txt | AC | 4 ms | 384 KB |
small/case_032.txt | AC | 4 ms | 384 KB |
small/case_033.txt | AC | 4 ms | 384 KB |
small/case_034.txt | AC | 4 ms | 384 KB |
small/case_035.txt | AC | 4 ms | 384 KB |
small/case_036.txt | AC | 4 ms | 384 KB |
small/case_037.txt | AC | 4 ms | 384 KB |