Submission #1750433


Source Code Expand

// Sandglass
// * frank_c1
// * 2017 / 11/ 07

#include <bits/stdc++.h>
using namespace std;

const int maxn = (int)(1e5) + 5;
pair<int, pair<int, int> > w[maxn];
int res[maxn], ri[maxn];

int main() {
	int X, K;
	scanf("%d%d", &X, &K);
	for (int i = 1; i <= K; ++i) scanf("%d", &ri[i]);
	int m; scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		int t, a; scanf("%d%d", &t, &a); w[i] = make_pair(t, make_pair(a, i));
	} 
	sort(w + 1, w + m + 1);
	int v = 0, l = 0, r = X, ps = 1;
	for (int i = 0; i <= K; ++i) {
		for (; ps <= m && (i == K || w[ps].first < ri[i + 1]); ++ps) {
			int t = w[ps].first - ri[i], a = w[ps].second.first, id = w[ps].second.second;
			if (i & 1) {
				if (l < 0) res[id] = min(X, v + t); 
				else {
					int nv = v, nl = l, nr = r;
					int c = min(t, X - (nv + nr - nl)); nv += c; t -= c;
					c = min(t, nr - nl); nv += c; nr -= c; t -= c; if (nl == nr) nl = nr = -1;
					if (nl < 0) res[id] = nv; else if (a <= nl) res[id] = nv; else if (a <= nr) res[id] = nv + a - nl; else res[id] = nv + nr - nl;
				}
			} else {
				if (l < 0) res[id] = max(0, v - t);
				else {
					int nv = v, nl = l, nr = r;
					int c = min(t, nv); nv -= c; t -= c;
					c = min(t, nr - nl); nl += c; t -= c; if (nl == nr) nl = nr = -1;
					if (nl < 0) res[id] = nv; else if (a <= nl) res[id] = nv; else if (a <= nr) res[id] = nv + a - nl; else res[id] = nv + nr - nl;
				}
			}
		}
		if (i < K) {
			int t = ri[i + 1] - ri[i];
			if (i & 1) {
				if (l < 0) v = min(X, v + t);
				else {
					int c = min(t, X - (v + r - l)); v += c; t -= c;
					c = min(t, r - l); v += c; r -= c; t -= c; if (l == r) l = r = -1;
				} 
			} else {
				if (l < 0) v = max(0, v - t);
				else {
					int c = min(t, v); v -= c; t -= c;
					c = min(t, r - l); l += c; t -= c; if (l == r) l = r = -1;
				}
			}
		}
	}
	for (int i = 1; i <= m; ++i) printf("%d\n", res[i]);
	return 0;
}

Submission Info

Submission Time
Task F - Sandglass
User frank_c1
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1940 Byte
Status AC
Exec Time 45 ms
Memory 3200 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &X, &K);
                       ^
./Main.cpp:15:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= K; ++i) scanf("%d", &ri[i]);
                                                  ^
./Main.cpp:16:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int m; scanf("%d", &m);
                        ^
./Main.cpp:18:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int t, a; scanf("%d%d", &t, &a); w[i] = make_pair(t, make_pair(a, i));
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 42
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 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 37 ms 2432 KB
1_004.txt AC 38 ms 2432 KB
1_005.txt AC 40 ms 2432 KB
1_006.txt AC 36 ms 2432 KB
1_007.txt AC 38 ms 2432 KB
1_008.txt AC 40 ms 2432 KB
1_009.txt AC 37 ms 2432 KB
1_010.txt AC 39 ms 2432 KB
1_011.txt AC 41 ms 2432 KB
1_012.txt AC 38 ms 2560 KB
1_013.txt AC 39 ms 2560 KB
1_014.txt AC 41 ms 2560 KB
1_015.txt AC 38 ms 2688 KB
1_016.txt AC 40 ms 2688 KB
1_017.txt AC 42 ms 2688 KB
1_018.txt AC 39 ms 2816 KB
1_019.txt AC 41 ms 2816 KB
1_020.txt AC 42 ms 2816 KB
1_021.txt AC 39 ms 2688 KB
1_022.txt AC 41 ms 2816 KB
1_023.txt AC 43 ms 2816 KB
1_024.txt AC 40 ms 2688 KB
1_025.txt AC 42 ms 2944 KB
1_026.txt AC 44 ms 2944 KB
1_027.txt AC 41 ms 2688 KB
1_028.txt AC 42 ms 2816 KB
1_029.txt AC 45 ms 3072 KB
1_030.txt AC 42 ms 2816 KB
1_031.txt AC 43 ms 2816 KB
1_032.txt AC 45 ms 3200 KB
1_033.txt AC 31 ms 2688 KB
1_034.txt AC 31 ms 2560 KB
1_035.txt AC 43 ms 2944 KB
1_036.txt AC 32 ms 2688 KB
1_037.txt AC 32 ms 2688 KB
1_038.txt AC 44 ms 3072 KB
1_039.txt AC 34 ms 2432 KB
1_040.txt AC 33 ms 2816 KB
1_041.txt AC 45 ms 3200 KB