Submission #1592973
Source Code Expand
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <string>
#include <cassert>
#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define PI acos(-1.0)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef vector <ll> vll;
int x;
int r[100000];
pii a[100000];
int k, q;
int em[100000], fu[100000];
int diff[100000];
int firstEmpty;
int mm[100000], ma[100000];
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
firstEmpty = INF;
scanf("%lld\n%lld", &x, &k);
for (int i = 0; i < k; i++) scanf("%d", r + i);
scanf("%d", &q);
for (int i = 0; i < q; i++) scanf("%d %d", &a[i].first, &a[i].second);
em[0] = 0;
fu[0] = x;
for (int i = 1; i < k; i++) {
if (i % 2 == 1) {
em[i] = min(x, em[i - 1] + r[i] - r[i - 1]);
fu[i] = min(x, fu[i - 1] + r[i] - r[i - 1]);
} else {
em[i] = max(0, em[i - 1] - r[i] + r[i - 1]);
fu[i] = max(0, fu[i - 1] - r[i] + r[i - 1]);
}
}
diff[0] = -r[0];
for (int i = 1; i < k; i++) {
if (i % 2 == 1) {
diff[i] = min(x, diff[i - 1] + r[i] - r[i - 1]);
} else {
diff[i] = max(-x, diff[i - 1] - r[i] + r[i - 1]);
if (diff[i] == -x)
firstEmpty = min(firstEmpty, r[i]);
}
}
mm[0] = -r[0];
ma[0] = x - r[0];
for (int i = 1; i < k; i++) mm[i] = min(mm[i - 1], diff[i]);
for (int i = 1; i < k; i++) ma[i] = max(ma[i - 1], diff[i]);
for (int i = 0; i < q; i++) {
if (a[i].first < r[0]) {
printf("%d\n", max(0, a[i].second - a[i].first));
continue;
}
int ll = 0, rr = k - 1;
int ans = 0;
while (ll <= rr) {
int mid = (ll + rr) / 2;
if (r[mid] <= a[i].first) {
ans = mid;
ll = mid + 1;
} else rr = mid - 1;
}
if (a[i].second + ma[ans] >= x) {
if (ans % 2 == 0)
printf("%d\n", min(x, fu[ans] + min(a[i].first - r[ans], x - fu[ans])));
else
printf("%d\n", max(0, fu[ans] - (a[i].first - r[ans])));
} else if (a[i].second + mm[ans] >= 0) {
if (ans % 2 == 0) {
int cur = min(x, a[i].second + diff[ans]);
printf("%d\n", min(x, cur + min(a[i].first - r[ans], x - cur)));
} else {
int cur = min(x, a[i].second + diff[ans]);
printf("%d\n", max(0, cur - (a[i].first - r[ans])));
}
} else {
if (ans % 2 == 0)
printf("%d\n", min(x, em[ans] + min(a[i].first - r[ans], x - em[ans])));
else
printf("%d\n", max(0, em[ans] - (a[i].first - r[ans])));
}
}
return 0;
}
Submission Info
Submission Time
2017-09-15 04:06:23+0900
Task
F - Sandglass
User
spiderbatman
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2670 Byte
Status
WA
Exec Time
50 ms
Memory
4352 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:39:28: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int*’ [-Wformat=]
scanf("%lld\n%lld", &x, &k);
^
./Main.cpp:39:28: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int*’ [-Wformat=]
./Main.cpp:39:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld\n%lld", &x, &k);
^
./Main.cpp:40:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < k; i++) scanf("%d", r + i);
^
./Main.cpp:41:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:42:71: warning: ignoring...
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 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
1 ms
256 KB
0_001.txt
AC
1 ms
256 KB
0_002.txt
WA
1 ms
256 KB
1_003.txt
AC
42 ms
3584 KB
1_004.txt
AC
43 ms
3584 KB
1_005.txt
AC
44 ms
3584 KB
1_006.txt
WA
42 ms
3584 KB
1_007.txt
AC
43 ms
3584 KB
1_008.txt
AC
44 ms
3584 KB
1_009.txt
WA
42 ms
3584 KB
1_010.txt
AC
44 ms
3712 KB
1_011.txt
AC
45 ms
3712 KB
1_012.txt
WA
43 ms
3712 KB
1_013.txt
WA
44 ms
3712 KB
1_014.txt
AC
45 ms
3712 KB
1_015.txt
WA
43 ms
3840 KB
1_016.txt
WA
44 ms
3840 KB
1_017.txt
AC
47 ms
3840 KB
1_018.txt
WA
44 ms
3968 KB
1_019.txt
WA
45 ms
3968 KB
1_020.txt
WA
47 ms
3968 KB
1_021.txt
WA
42 ms
4096 KB
1_022.txt
WA
45 ms
4096 KB
1_023.txt
WA
48 ms
3968 KB
1_024.txt
WA
42 ms
4096 KB
1_025.txt
WA
46 ms
4096 KB
1_026.txt
WA
48 ms
4096 KB
1_027.txt
WA
43 ms
4224 KB
1_028.txt
WA
44 ms
4224 KB
1_029.txt
WA
49 ms
4224 KB
1_030.txt
WA
44 ms
4352 KB
1_031.txt
WA
45 ms
4352 KB
1_032.txt
WA
50 ms
4352 KB
1_033.txt
WA
29 ms
1920 KB
1_034.txt
WA
30 ms
1792 KB
1_035.txt
WA
47 ms
4096 KB
1_036.txt
WA
30 ms
1920 KB
1_037.txt
WA
31 ms
1920 KB
1_038.txt
WA
48 ms
4224 KB
1_039.txt
WA
30 ms
1664 KB
1_040.txt
WA
32 ms
2048 KB
1_041.txt
WA
50 ms
4352 KB