Submission #62294
Source Code Expand
#include <iostream> #include <cassert> using namespace std; const int kMaxI = 1 << 18; // max (N+M) rounded up to the nearest (2^k) void add(long* bit, int k, long x) { for (; k <= kMaxI; k += k & ~(k - 1)) { bit[k] += x; } } long sum(const long* bit, int k) { long ans = 0; for(; k > 0; k -= k & ~(k - 1)) { ans += bit[k]; } return ans; } int upper(const long* bit, long x) { int k = 0; for (int j = kMaxI / 2; j >= 1; j >>= 1) { if (x >= bit[k + j]) { k += j; x -= bit[k]; } } return k; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, h; cin >> n >> m >> h; static long bit[kMaxI + 1]; for (int i = 1; i <= n; i++) { long ai; cin >> ai; add(bit, i, ai); } for (int i = 1; i <= m; i++) { string op; long arg; cin >> op >> arg; if (op == "add") { add(bit, ++n, arg); } else { int k = upper(bit, arg - h); if (k >= n) { cout << "miss\n"; continue; } long s0 = sum(bit, k), s1 = sum(bit, k + 1); if (s1 >= min(sum(bit, n), arg + h)) { add(bit, k + 1, s0 - s1); cout << "go\n"; continue; } else { cout << "stop\n"; continue; } } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - だるま落とし |
User | yuizumi |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 1487 Byte |
Status | AC |
Exec Time | 500 ms |
Memory | 2448 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 | 500 ms | 968 KB |
large/case_002.txt | AC | 151 ms | 864 KB |
large/case_003.txt | AC | 25 ms | 864 KB |
large/case_005.txt | AC | 25 ms | 1040 KB |
large/case_006.txt | AC | 25 ms | 924 KB |
large/case_007.txt | AC | 25 ms | 916 KB |
large/case_008.txt | AC | 25 ms | 1020 KB |
large/case_009.txt | AC | 25 ms | 920 KB |
large/case_010.txt | AC | 26 ms | 1040 KB |
large/case_011.txt | AC | 25 ms | 916 KB |
large/case_012.txt | AC | 26 ms | 1040 KB |
large/case_013.txt | AC | 24 ms | 1040 KB |
large/case_014.txt | AC | 24 ms | 1032 KB |
large/case_015.txt | AC | 24 ms | 920 KB |
large/case_016.txt | AC | 25 ms | 1016 KB |
large/case_017.txt | AC | 25 ms | 916 KB |
large/case_018.txt | AC | 25 ms | 992 KB |
large/case_019.txt | AC | 25 ms | 864 KB |
large/case_020.txt | AC | 25 ms | 1036 KB |
large/case_021.txt | AC | 24 ms | 1016 KB |
large/case_022.txt | AC | 26 ms | 996 KB |
large/case_023.txt | AC | 27 ms | 1060 KB |
large/case_024.txt | AC | 26 ms | 1032 KB |
large/case_025.txt | AC | 25 ms | 996 KB |
large/case_026.txt | AC | 24 ms | 992 KB |
large/case_027.txt | AC | 26 ms | 920 KB |
large/case_028.txt | AC | 26 ms | 996 KB |
large/case_029.txt | AC | 24 ms | 1036 KB |
large/case_030.txt | AC | 25 ms | 996 KB |
large/case_031.txt | AC | 25 ms | 996 KB |
large/case_032.txt | AC | 25 ms | 1048 KB |
large/case_033.txt | AC | 25 ms | 1040 KB |
large/case_034.txt | AC | 25 ms | 984 KB |
large/case_035.txt | AC | 25 ms | 916 KB |
large/case_036.txt | AC | 26 ms | 1004 KB |
large/case_037.txt | AC | 26 ms | 1032 KB |
large/large_case_000.txt | AC | 121 ms | 2320 KB |
large/large_case_001.txt | AC | 117 ms | 2300 KB |
large/large_case_002.txt | AC | 117 ms | 2276 KB |
large/large_case_003.txt | AC | 120 ms | 2320 KB |
large/large_case_004.txt | AC | 123 ms | 2204 KB |
large/large_case_005.txt | AC | 119 ms | 2196 KB |
large/large_case_006.txt | AC | 112 ms | 2280 KB |
large/large_case_007.txt | AC | 116 ms | 2280 KB |
large/large_case_008.txt | AC | 113 ms | 2204 KB |
large/large_case_009.txt | AC | 121 ms | 2324 KB |
large/large_case_010.txt | AC | 91 ms | 2448 KB |
large/large_case_011.txt | AC | 111 ms | 2272 KB |
large/large_case_012.txt | AC | 114 ms | 2324 KB |
large/large_case_013.txt | AC | 133 ms | 2276 KB |
large/large_case_014.txt | AC | 130 ms | 2160 KB |
large/large_case_015.txt | AC | 117 ms | 2144 KB |
large/large_case_016.txt | AC | 109 ms | 2204 KB |
large/large_case_017.txt | AC | 109 ms | 2140 KB |
large/large_case_018.txt | AC | 115 ms | 2148 KB |
large/large_case_019.txt | AC | 119 ms | 2144 KB |
large/large_case_020.txt | AC | 113 ms | 2152 KB |
large/large_case_021.txt | AC | 111 ms | 2156 KB |
large/large_case_022.txt | AC | 108 ms | 2156 KB |
large/large_case_023.txt | AC | 114 ms | 2144 KB |
large/large_case_024.txt | AC | 122 ms | 2148 KB |
large/large_case_025.txt | AC | 121 ms | 2140 KB |
large/large_case_026.txt | AC | 109 ms | 2196 KB |
large/large_case_027.txt | AC | 112 ms | 2180 KB |
large/large_case_028.txt | AC | 119 ms | 2148 KB |
large/large_case_029.txt | AC | 119 ms | 2148 KB |
small/case_000.txt | AC | 25 ms | 880 KB |
small/case_002.txt | AC | 27 ms | 888 KB |
small/case_003.txt | AC | 26 ms | 988 KB |
small/case_005.txt | AC | 25 ms | 876 KB |
small/case_006.txt | AC | 25 ms | 868 KB |
small/case_007.txt | AC | 25 ms | 992 KB |
small/case_008.txt | AC | 28 ms | 1028 KB |
small/case_009.txt | AC | 26 ms | 1036 KB |
small/case_010.txt | AC | 25 ms | 1024 KB |
small/case_011.txt | AC | 25 ms | 1000 KB |
small/case_012.txt | AC | 24 ms | 1032 KB |
small/case_013.txt | AC | 26 ms | 988 KB |
small/case_014.txt | AC | 25 ms | 996 KB |
small/case_015.txt | AC | 24 ms | 1036 KB |
small/case_016.txt | AC | 26 ms | 996 KB |
small/case_017.txt | AC | 24 ms | 1036 KB |
small/case_018.txt | AC | 25 ms | 872 KB |
small/case_019.txt | AC | 25 ms | 920 KB |
small/case_020.txt | AC | 26 ms | 992 KB |
small/case_021.txt | AC | 25 ms | 912 KB |
small/case_022.txt | AC | 25 ms | 1036 KB |
small/case_023.txt | AC | 25 ms | 1000 KB |
small/case_024.txt | AC | 26 ms | 988 KB |
small/case_025.txt | AC | 26 ms | 988 KB |
small/case_026.txt | AC | 26 ms | 1036 KB |
small/case_027.txt | AC | 26 ms | 1036 KB |
small/case_028.txt | AC | 26 ms | 1008 KB |
small/case_029.txt | AC | 26 ms | 984 KB |
small/case_030.txt | AC | 26 ms | 1036 KB |
small/case_031.txt | AC | 27 ms | 972 KB |
small/case_032.txt | AC | 27 ms | 936 KB |
small/case_033.txt | AC | 26 ms | 924 KB |
small/case_034.txt | AC | 26 ms | 1024 KB |
small/case_035.txt | AC | 26 ms | 928 KB |
small/case_036.txt | AC | 26 ms | 944 KB |
small/case_037.txt | AC | 29 ms | 1000 KB |