Submission #1834161
Source Code Expand
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> #define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i) #define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i) #define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i) #define ri rd<int> using namespace std; const int maxN = 2e5 + 7; const int maxV = 20; const int maxS = (1 << maxV); template<class T> inline T rd() { bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0; T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x; } inline void Min(int &x, int y) {if (y < x) x = y;} inline void Max(int &x, int y) {if (y > x) x = y;} int n, m, V; int a[maxN], b[maxN]; int nx[maxV][maxN], pr[maxV][maxN]; int f[maxS], g[maxS]; struct dsu { int mn, mx, fa; }fa[maxN]; inline int find(int x) {return (fa[x].fa != x) ? fa[x].fa = find(fa[x].fa) : x;} void merge(int x, int y) { if (find(x) != find(y)) { Min(fa[find(y)].mn, fa[find(x)].mn); Max(fa[find(y)].mx, fa[find(x)].mx); fa[find(x)].fa = find(y); } } struct rec { int l, r; inline bool operator < (const rec &v) const { return r < v.r; } }q[maxS]; int tt; int main() { n = ri(), m = ri(); rep (i, 1, n) a[i] = ri(); for (int i = m; i > 0; i >>= 1) b[++V] = i; b[++V] = 0; reverse(b+1, b+V+1); rep (i, 1, n) fa[i] = (dsu){i, i, i}; rep (j, 1, V) { rep (i, 2, n) if (a[i] - a[i - 1] <= b[j]) merge(i, i-1); rep (i, 1, n) nx[j][i] = fa[find(i)].mx, pr[j][i] = fa[find(i)].mn; nx[j][n+1] = n; pr[j][0] = 1; } int mask = (1 << V) - 1; f[0] = 0; rep (s, 1, mask) { f[s] = 0; rep (j, 1, V) if (s >> (j-1) & 1) Max(f[s], nx[j][f[s ^ (1 << (j-1))] + 1]); } g[0] = n+1; rep (s, 1, mask) { g[s] = n+1; rep (j, 1, V) if (s >> (j-1) & 1) Min(g[s], pr[j][g[s ^ (1 << (j-1))] - 1]); } rep (s, 0, mask = (1 << (V-1)) - 1) q[++tt] = (rec){f[s], g[mask ^ s]}; sort(q+1, q+tt+1); for (int i = 1, j = 1, cl = -1; i <= n; ++ i) { int l = fa[find(i)].mn, r = fa[find(i)].mx; for (; j <= tt && q[j].r <= r+1; ++ j) cl = max(cl, q[j].l); puts(cl >= l - 1 ? "Possible" : "Impossible"); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Camel and Oases |
User | acha |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2288 Byte |
Status | AC |
Exec Time | 138 ms |
Memory | 49792 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 3 ms | 14464 KB |
00_example_02.txt | AC | 3 ms | 14464 KB |
00_example_03.txt | AC | 4 ms | 20608 KB |
01.txt | AC | 87 ms | 47232 KB |
02.txt | AC | 26 ms | 37504 KB |
03.txt | AC | 88 ms | 47232 KB |
04.txt | AC | 26 ms | 37504 KB |
05.txt | AC | 86 ms | 47232 KB |
06.txt | AC | 94 ms | 47616 KB |
07.txt | AC | 29 ms | 37760 KB |
08.txt | AC | 94 ms | 47488 KB |
09.txt | AC | 31 ms | 37760 KB |
10.txt | AC | 88 ms | 47360 KB |
11.txt | AC | 50 ms | 40320 KB |
12.txt | AC | 90 ms | 47360 KB |
13.txt | AC | 138 ms | 49792 KB |
14.txt | AC | 87 ms | 47232 KB |
15.txt | AC | 26 ms | 37504 KB |
16.txt | AC | 88 ms | 47232 KB |
17.txt | AC | 26 ms | 37504 KB |
18.txt | AC | 86 ms | 47232 KB |
19.txt | AC | 45 ms | 40064 KB |
20.txt | AC | 93 ms | 47488 KB |
21.txt | AC | 29 ms | 37760 KB |
22.txt | AC | 92 ms | 47488 KB |
23.txt | AC | 31 ms | 37760 KB |
24.txt | AC | 89 ms | 47360 KB |
25.txt | AC | 49 ms | 40320 KB |
26.txt | AC | 91 ms | 47488 KB |
27.txt | AC | 136 ms | 49792 KB |
28.txt | AC | 92 ms | 47488 KB |
29.txt | AC | 29 ms | 37760 KB |
30.txt | AC | 92 ms | 47488 KB |
31.txt | AC | 49 ms | 40192 KB |
32.txt | AC | 89 ms | 47360 KB |
33.txt | AC | 48 ms | 40320 KB |
34.txt | AC | 90 ms | 47488 KB |
35.txt | AC | 137 ms | 49792 KB |
36.txt | AC | 87 ms | 47232 KB |
37.txt | AC | 26 ms | 37504 KB |
38.txt | AC | 87 ms | 47232 KB |
39.txt | AC | 26 ms | 37504 KB |
40.txt | AC | 91 ms | 47232 KB |
41.txt | AC | 45 ms | 40064 KB |
42.txt | AC | 87 ms | 47232 KB |
43.txt | AC | 45 ms | 40064 KB |
44.txt | AC | 87 ms | 47232 KB |
45.txt | AC | 47 ms | 40064 KB |
46.txt | AC | 29 ms | 37632 KB |
47.txt | AC | 91 ms | 47488 KB |
48.txt | AC | 48 ms | 40320 KB |
49.txt | AC | 90 ms | 47360 KB |
50.txt | AC | 48 ms | 40192 KB |
51.txt | AC | 90 ms | 47360 KB |
52.txt | AC | 48 ms | 40320 KB |
53.txt | AC | 90 ms | 47360 KB |
54.txt | AC | 47 ms | 40192 KB |
55.txt | AC | 90 ms | 47488 KB |
56.txt | AC | 29 ms | 37632 KB |
57.txt | AC | 91 ms | 47360 KB |
58.txt | AC | 50 ms | 40320 KB |
59.txt | AC | 89 ms | 47360 KB |
60.txt | AC | 49 ms | 40320 KB |
61.txt | AC | 91 ms | 47488 KB |
62.txt | AC | 49 ms | 40320 KB |
63.txt | AC | 91 ms | 47488 KB |
64.txt | AC | 48 ms | 40320 KB |
65.txt | AC | 91 ms | 47488 KB |
66.txt | AC | 3 ms | 14464 KB |
67.txt | AC | 3 ms | 14464 KB |