Submission #1563352
Source Code Expand
using System; using System.IO; using System.Linq; using System.Text; using System.Collections.Generic; using System.Diagnostics; using Enu = System.Linq.Enumerable; public class Program { public void Solve() { int S = Reader.Int(), N = Reader.Int(); var R = Reader.IntArray(N); int NQ = Reader.Int(); var Q = Reader.IntTable(NQ); var diff = new long[N + 1]; long[] min = new long[N + 1], max = new long[N + 1]; long[] lower = new long[N + 1], upper = new long[N + 1]; min[0] = 0; max[0] = S; upper[0] = S; for (int i = 0; i < N; i++) { int r = R[i] - (i == 0 ? 0 : R[i - 1]); diff[i + 1] = diff[i] + (i % 2 == 0 ? -r : r); if (i % 2 == 0) { min[i + 1] = Math.Max(min[i], r - diff[i]); max[i + 1] = max[i]; lower[i + 1] = Math.Max(0, lower[i] - r); upper[i + 1] = Math.Max(0, upper[i] - r); } else { min[i + 1] = min[i]; max[i + 1] = Math.Min(max[i], S - r - diff[i]); lower[i + 1] = Math.Min(S, lower[i] + r); upper[i + 1] = Math.Min(S, upper[i] + r); } } var ans = new List<long>(); foreach (var q in Q) { int time = q[0]; long x = q[1]; int i = UpperBound(R, time) - 1; if (i == -1) { ans.Add(Math.Max(0, x - time)); continue; } if (x >= min[i + 1] && x <= max[i + 1]) x += diff[i + 1]; else if (x < min[i + 1]) x = lower[i + 1]; else x = upper[i + 1]; if (i % 2 == 0) x = Math.Min(S, x + (time - R[i])); else x = Math.Max(0, x - (time - R[i])); ans.Add(x); } Console.WriteLine(string.Join("\n", ans)); } bool CheckMin(ref int a, int b) { if (b < a) { a = b; return true; } return false; } bool CheckMax(ref int a, int b) { if (b > a) { a = b; return true; } return false; } static int UpperBound(int[] A, int val, int L = 0, int R = -1) { if (R == -1) R = A.Length; while (R - L >= 1) { int mid = (L + R) / 2; if (A[mid] > val) R = mid; else L = mid + 1; } return R; } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { Dispose(); A = new string[0]; } public static void Set(TextReader r) { Init(); reader = r; } public static void Set(string file) { Init(); reader = new StreamReader(file); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; } public static void Dispose() { reader.Dispose(); } static string[] Split(string s) { return s.Split(separator, op); } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | eitaho |
Language | C# (Mono 4.6.2.0) |
Score | 700 |
Code Size | 4329 Byte |
Status | AC |
Exec Time | 225 ms |
Memory | 39536 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 24 ms | 13396 KB |
0_001.txt | AC | 24 ms | 11348 KB |
0_002.txt | AC | 24 ms | 11348 KB |
1_003.txt | AC | 176 ms | 29320 KB |
1_004.txt | AC | 180 ms | 29772 KB |
1_005.txt | AC | 187 ms | 28720 KB |
1_006.txt | AC | 181 ms | 33544 KB |
1_007.txt | AC | 185 ms | 32072 KB |
1_008.txt | AC | 193 ms | 31152 KB |
1_009.txt | AC | 186 ms | 32008 KB |
1_010.txt | AC | 190 ms | 34504 KB |
1_011.txt | AC | 197 ms | 31280 KB |
1_012.txt | AC | 189 ms | 32520 KB |
1_013.txt | AC | 194 ms | 32968 KB |
1_014.txt | AC | 196 ms | 35760 KB |
1_015.txt | AC | 202 ms | 33028 KB |
1_016.txt | AC | 199 ms | 31436 KB |
1_017.txt | AC | 205 ms | 36144 KB |
1_018.txt | AC | 199 ms | 37768 KB |
1_019.txt | AC | 207 ms | 34116 KB |
1_020.txt | AC | 212 ms | 35372 KB |
1_021.txt | AC | 195 ms | 35332 KB |
1_022.txt | AC | 208 ms | 34756 KB |
1_023.txt | AC | 213 ms | 31788 KB |
1_024.txt | AC | 194 ms | 35200 KB |
1_025.txt | AC | 209 ms | 33476 KB |
1_026.txt | AC | 222 ms | 36524 KB |
1_027.txt | AC | 200 ms | 35456 KB |
1_028.txt | AC | 210 ms | 38344 KB |
1_029.txt | AC | 219 ms | 37156 KB |
1_030.txt | AC | 204 ms | 35712 KB |
1_031.txt | AC | 206 ms | 36160 KB |
1_032.txt | AC | 225 ms | 37800 KB |
1_033.txt | AC | 163 ms | 25536 KB |
1_034.txt | AC | 165 ms | 29504 KB |
1_035.txt | AC | 212 ms | 39536 KB |
1_036.txt | AC | 162 ms | 27836 KB |
1_037.txt | AC | 168 ms | 28220 KB |
1_038.txt | AC | 217 ms | 35680 KB |
1_039.txt | AC | 158 ms | 25920 KB |
1_040.txt | AC | 173 ms | 28732 KB |
1_041.txt | AC | 225 ms | 35752 KB |