Submission #1416929
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Globalization; using System.Diagnostics; class Myon { public Myon() { } public static int Main() { new Myon().calc(); return 0; } Scanner cin; long[] ar; void calc() { cin = new Scanner(); int N = cin.nextInt(); int M = cin.nextInt(); int H = cin.nextInt(); ar = new long[N + M + 10]; int cnt = 1; BIT bit = new BIT(N + M + 10); for (int i = 0; i < N; i++) { ar[cnt] = cin.nextLong(); bit.bitUpdate(cnt, ar[cnt]); cnt++; } for (int i = 0; i < M; i++) { string op = cin.next(); long arg = cin.nextLong(); if(op == "add") { ar[cnt] = arg; bit.bitUpdate(cnt, arg); cnt++; } else { long low = arg - H; long high = arg + H; int ok = cnt + 3; int ng = 0; while(ok - ng > 1) { int mid = (ok + ng) / 2; if (bit.bitCal(mid) <= low) ng = mid; else ok = mid; } //Console.WriteLine("sum : " + bit.bitCal(cnt + 13)); if(ok == cnt + 3) { Console.WriteLine("miss"); continue; } long sum = bit.bitCal(ng + 1); long all = bit.bitCal(cnt + 3); if (sum != all && sum < high) Console.WriteLine("stop"); else { Console.WriteLine("go"); bit.bitUpdate(ng + 1, -ar[ng + 1]); } } } } class BIT { int bitA; long[] bit; const int INF = int.MaxValue - 10; public BIT(int maxa) { bitA = maxa; bit = new long[bitA + 1]; for (int i = 0; i < bitA; i++) { bit[i] = 0; } } public void bitUpdate(int a, long val) { for (int i = a; i <= bitA; i += i & -i) { bit[i] += val; } } public long bitCal(int max, int min) { return bitCal(max) - bitCal(min - 1); } public long bitCal(int a) { long ret = 0; for (int i = a; i > 0; i &= i - 1) { ret += bit[i]; } return ret; } } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return s[i++]; } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }
Submission Info
Submission Time | |
---|---|
Task | G - だるま落とし |
User | chokudai |
Language | C# (Mono 4.6.2.0) |
Score | 100 |
Code Size | 3616 Byte |
Status | AC |
Exec Time | 413 ms |
Memory | 30656 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 | 20 ms | 9044 KB |
large/case_002.txt | AC | 21 ms | 11092 KB |
large/case_003.txt | AC | 21 ms | 11092 KB |
large/case_005.txt | AC | 21 ms | 11092 KB |
large/case_006.txt | AC | 20 ms | 9044 KB |
large/case_007.txt | AC | 20 ms | 9044 KB |
large/case_008.txt | AC | 24 ms | 11124 KB |
large/case_009.txt | AC | 23 ms | 9076 KB |
large/case_010.txt | AC | 23 ms | 9076 KB |
large/case_011.txt | AC | 23 ms | 9076 KB |
large/case_012.txt | AC | 23 ms | 9076 KB |
large/case_013.txt | AC | 23 ms | 9076 KB |
large/case_014.txt | AC | 23 ms | 9076 KB |
large/case_015.txt | AC | 24 ms | 11124 KB |
large/case_016.txt | AC | 24 ms | 11124 KB |
large/case_017.txt | AC | 23 ms | 9076 KB |
large/case_018.txt | AC | 21 ms | 9068 KB |
large/case_019.txt | AC | 23 ms | 9076 KB |
large/case_020.txt | AC | 24 ms | 11124 KB |
large/case_021.txt | AC | 24 ms | 13172 KB |
large/case_022.txt | AC | 25 ms | 11124 KB |
large/case_023.txt | AC | 24 ms | 11124 KB |
large/case_024.txt | AC | 24 ms | 11124 KB |
large/case_025.txt | AC | 24 ms | 11124 KB |
large/case_026.txt | AC | 24 ms | 11124 KB |
large/case_027.txt | AC | 24 ms | 11124 KB |
large/case_028.txt | AC | 24 ms | 11124 KB |
large/case_029.txt | AC | 24 ms | 11124 KB |
large/case_030.txt | AC | 24 ms | 9076 KB |
large/case_031.txt | AC | 25 ms | 11124 KB |
large/case_032.txt | AC | 24 ms | 11124 KB |
large/case_033.txt | AC | 24 ms | 11124 KB |
large/case_034.txt | AC | 24 ms | 11124 KB |
large/case_035.txt | AC | 24 ms | 11124 KB |
large/case_036.txt | AC | 24 ms | 11124 KB |
large/case_037.txt | AC | 24 ms | 9076 KB |
large/large_case_000.txt | AC | 335 ms | 24644 KB |
large/large_case_001.txt | AC | 333 ms | 22472 KB |
large/large_case_002.txt | AC | 335 ms | 22596 KB |
large/large_case_003.txt | AC | 329 ms | 22472 KB |
large/large_case_004.txt | AC | 330 ms | 24520 KB |
large/large_case_005.txt | AC | 343 ms | 22472 KB |
large/large_case_006.txt | AC | 328 ms | 26568 KB |
large/large_case_007.txt | AC | 336 ms | 22472 KB |
large/large_case_008.txt | AC | 328 ms | 24520 KB |
large/large_case_009.txt | AC | 331 ms | 22596 KB |
large/large_case_010.txt | AC | 145 ms | 23880 KB |
large/large_case_011.txt | AC | 324 ms | 24644 KB |
large/large_case_012.txt | AC | 337 ms | 22596 KB |
large/large_case_013.txt | AC | 335 ms | 22596 KB |
large/large_case_014.txt | AC | 389 ms | 26568 KB |
large/large_case_015.txt | AC | 396 ms | 30656 KB |
large/large_case_016.txt | AC | 384 ms | 26564 KB |
large/large_case_017.txt | AC | 393 ms | 24520 KB |
large/large_case_018.txt | AC | 394 ms | 22472 KB |
large/large_case_019.txt | AC | 392 ms | 22592 KB |
large/large_case_020.txt | AC | 413 ms | 26568 KB |
large/large_case_021.txt | AC | 389 ms | 24520 KB |
large/large_case_022.txt | AC | 385 ms | 24520 KB |
large/large_case_023.txt | AC | 383 ms | 22472 KB |
large/large_case_024.txt | AC | 394 ms | 24520 KB |
large/large_case_025.txt | AC | 402 ms | 24520 KB |
large/large_case_026.txt | AC | 397 ms | 28616 KB |
large/large_case_027.txt | AC | 391 ms | 24520 KB |
large/large_case_028.txt | AC | 390 ms | 28616 KB |
large/large_case_029.txt | AC | 391 ms | 28616 KB |
small/case_000.txt | AC | 21 ms | 11092 KB |
small/case_002.txt | AC | 20 ms | 11092 KB |
small/case_003.txt | AC | 21 ms | 11092 KB |
small/case_005.txt | AC | 21 ms | 11092 KB |
small/case_006.txt | AC | 20 ms | 9044 KB |
small/case_007.txt | AC | 20 ms | 9044 KB |
small/case_008.txt | AC | 23 ms | 9076 KB |
small/case_009.txt | AC | 23 ms | 9076 KB |
small/case_010.txt | AC | 24 ms | 13172 KB |
small/case_011.txt | AC | 23 ms | 11124 KB |
small/case_012.txt | AC | 24 ms | 11124 KB |
small/case_013.txt | AC | 23 ms | 9076 KB |
small/case_014.txt | AC | 23 ms | 9076 KB |
small/case_015.txt | AC | 24 ms | 11124 KB |
small/case_016.txt | AC | 24 ms | 11124 KB |
small/case_017.txt | AC | 24 ms | 11124 KB |
small/case_018.txt | AC | 22 ms | 13164 KB |
small/case_019.txt | AC | 24 ms | 11124 KB |
small/case_020.txt | AC | 24 ms | 11124 KB |
small/case_021.txt | AC | 23 ms | 9076 KB |
small/case_022.txt | AC | 24 ms | 9076 KB |
small/case_023.txt | AC | 24 ms | 11124 KB |
small/case_024.txt | AC | 24 ms | 11124 KB |
small/case_025.txt | AC | 24 ms | 11124 KB |
small/case_026.txt | AC | 24 ms | 9076 KB |
small/case_027.txt | AC | 25 ms | 13172 KB |
small/case_028.txt | AC | 24 ms | 11124 KB |
small/case_029.txt | AC | 24 ms | 11124 KB |
small/case_030.txt | AC | 24 ms | 11124 KB |
small/case_031.txt | AC | 24 ms | 11124 KB |
small/case_032.txt | AC | 24 ms | 9076 KB |
small/case_033.txt | AC | 24 ms | 11124 KB |
small/case_034.txt | AC | 24 ms | 11124 KB |
small/case_035.txt | AC | 24 ms | 11124 KB |
small/case_036.txt | AC | 24 ms | 11124 KB |
small/case_037.txt | AC | 25 ms | 13172 KB |