Submission #1750518


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 200005 ;
using namespace std ;

int X, n, a[N] ;
struct poi {
	int l, r, L, R, b ;
} f[N], g ;

void add(poi a, poi &b, int x) {
	if (a.L + x >= X) {
		b.l = 0, b.r = 0, b.b = b.L = b.R = X ;
		return ;
	}
	b.l = a.l, b.L = a.L + x ;
	b.b = a.b + x ;
	if (a.R + x <= X) {
		b.r = a.r, b.R = a.R + x ;
		return ;
	}
	b.r = X - (a.b + x) ;
	b.R = X ;
}

void del(poi a, poi &b, int x) {
	if (a.R - x <= 0) {
		b.l = b.r = X, b.b = - X, b.L = b.R = 0 ;
		return ;
	}
	b.r = a.r, b.R = a.R - x ;
	b.b = a.b - x ;
	if (a.L - x >= 0) {
		b.l = a.l, b.L = a.L - x ;
		return ;
	}
	b.l = - (a.b - x) ;
	b.L = 0 ;
}

int main() {
	//freopen("a.in", "r", stdin) ;
	scanf("%d%d", &X, &n) ;
	f[0].l = 0, f[0].r = X, f[0].b = 0, f[0].L = 0, f[0].R = X ;
	a[0] = 0 ; 
	rep(i, 1, n) {
		scanf("%d", &a[i]) ;
		if (i & 1) del(f[i - 1], f[i], a[i] - a[i - 1]) ; else
		  add(f[i - 1], f[i], a[i] - a[i - 1]) ;
	//	printf("%d: %d -> l=%d r=%d L=%d R=%d b=%d\n", i, a[i], f[i].l, f[i].r, f[i].L, f[i].R, f[i].b) ;
	}
	int m, x, y ;
	scanf("%d", &m) ;
	rep(i, 1, m) {
		scanf("%d%d", &x, &y) ;
		int l = 0, r = n, res = l ;
		for ( ; l <= r ; ) {
			int mid = (l + r) / 2 ;
			if (a[mid] <= x) res = mid, l = mid + 1 ;
				else r = mid - 1 ;
		}
		if (res & 1) add(f[res], g, x - a[res]) ;
			else del(f[res], g, x - a[res]) ;
		if (y < g.l) printf("%d\n", g.L) ; else
		  if (y > g.r) printf("%d\n", g.R) ; else 
			printf("%d\n", y + g.b) ;
	}
	return 0 ; 
}

Submission Info

Submission Time
Task F - Sandglass
User mjy0724
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1699 Byte
Status AC
Exec Time 53 ms
Memory 5504 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &X, &n) ;
                        ^
./Main.cpp:52:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]) ;
                      ^
./Main.cpp:58:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m) ;
                  ^
./Main.cpp:60:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y) ;
                         ^

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 2 ms 2304 KB
0_001.txt AC 2 ms 2304 KB
0_002.txt AC 2 ms 2304 KB
1_003.txt AC 45 ms 4608 KB
1_004.txt AC 46 ms 4608 KB
1_005.txt AC 48 ms 4608 KB
1_006.txt AC 43 ms 4608 KB
1_007.txt AC 45 ms 4736 KB
1_008.txt AC 47 ms 4736 KB
1_009.txt AC 43 ms 4736 KB
1_010.txt AC 45 ms 4736 KB
1_011.txt AC 47 ms 4736 KB
1_012.txt AC 45 ms 4864 KB
1_013.txt AC 45 ms 4864 KB
1_014.txt AC 47 ms 4864 KB
1_015.txt AC 45 ms 4992 KB
1_016.txt AC 46 ms 4992 KB
1_017.txt AC 49 ms 4864 KB
1_018.txt AC 46 ms 4992 KB
1_019.txt AC 48 ms 4992 KB
1_020.txt AC 49 ms 4992 KB
1_021.txt AC 45 ms 4992 KB
1_022.txt AC 48 ms 5120 KB
1_023.txt AC 50 ms 5120 KB
1_024.txt AC 45 ms 4992 KB
1_025.txt AC 49 ms 5248 KB
1_026.txt AC 51 ms 5248 KB
1_027.txt AC 46 ms 4992 KB
1_028.txt AC 48 ms 4992 KB
1_029.txt AC 52 ms 5376 KB
1_030.txt AC 48 ms 4992 KB
1_031.txt AC 49 ms 4992 KB
1_032.txt AC 53 ms 5376 KB
1_033.txt AC 32 ms 3072 KB
1_034.txt AC 33 ms 3072 KB
1_035.txt AC 50 ms 5248 KB
1_036.txt AC 33 ms 3200 KB
1_037.txt AC 34 ms 3200 KB
1_038.txt AC 51 ms 5376 KB
1_039.txt AC 34 ms 2944 KB
1_040.txt AC 36 ms 3328 KB
1_041.txt AC 53 ms 5504 KB