# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
96827 |
2019-02-12T10:48:05 Z |
youngyojun |
Seats (IOI18_seats) |
C++11 |
|
2824 ms |
124608 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1000005;
int _int[MAXN*4], *_intp = _int;
int* newint(int n) { _intp += n; return _intp - n; }
struct SEG {
int dp[MAXN*3][5], duc[MAXN*3], dbc[MAXN*3];
bitset<MAXN*3> chk;
int n;
void init(int i, int s, int e) {
dp[i][0] = e-s+1;
if(s == e) return;
int m = (s+e) >> 1;
init(i<<1, s, m);
init(i<<1|1, m+1, e);
}
void init(int _n) {
n = _n;
init(1, 0, n-1);
}
void mv(int d[], int w) {
if(!w) return;
for(int i = 5; w < i--;) d[i] = d[i-w];
memset(d, 0, min(5, w)<<2);
}
void cal(int i, int s, int e) {
memset(dp[i], 0, 20);
if(dbc[i] || 4 < duc[i]) return;
if(s == e) dp[i][0] = 1;
else {
for(int j = 5, t; j--;) {
t = 0;
if(!chk[i<<1]) t += dp[i<<1][j];
if(!chk[i<<1|1]) t += dp[i<<1|1][j];
dp[i][j] = t;
}
}
mv(dp[i], duc[i]);
}
void precal(int i, int s, int e) {
chk[i] = false;
if(s == e) {
cal(i, s, e);
return;
}
int m = (s+e) >> 1, l = i<<1, r = l|1;
if(chk[l] && !dbc[l] && duc[l] < 5) precal(l, s, m);
if(chk[r] && !dbc[r] && duc[r] < 5) precal(r, m+1, e);
cal(i, s, e);
}
void updb(int i, int s, int e, int p, int q, int x) {
if(q < p || e < p || q < s) return;
chk[i] = true;
if(p <= s && e <= q) {
dbc[i] += x;
return;
}
int m = (s+e) >> 1;
updb(i<<1, s, m, p, q, x);
updb(i<<1|1, m+1, e, p, q, x);
}
void updu(int i, int s, int e, int p, int q, int x) {
if(q < p || e < p || q < s) return;
chk[i] = true;
if(p <= s && e <= q) {
duc[i] += x;
return;
}
int m = (s+e) >> 1;
updu(i<<1, s, m, p, q, x);
updu(i<<1|1, m+1, e, p, q, x);
}
void updb(int s, int e, int x) { updb(1, 0, n-1, s, e, x); }
void updu(int s, int e, int x) { updu(1, 0, n-1, s, e, x); }
int get() {
if(chk[1]) precal(1, 0, n-1);
return dp[1][4];
}
} seg;
int A[MAXN], B[MAXN], *C[MAXN];
int H, W, N;
vector<pii> PFV[2], NFV[2];
void f(int y, int x, bool flag = false) {
int a[4] = { C[y][x], C[y][x+1], C[y+1][x], C[y+1][x+1] };
sort(a, a+4);
(flag ? NFV : PFV)[0].eb(a[0], a[1]-1);
(flag ? NFV : PFV)[1].eb(a[2], a[3]-1);
}
void g(int i, bool flag = false) {
int y = A[i], x = B[i];
for(int dy = 2; dy--;) for(int dx = 2; dx--;)
f(y-dy, x-dx, flag);
}
void run() {
for(auto &v : PFV[0]) seg.updu(v.first, v.second, 1);
for(auto &v : PFV[1]) seg.updb(v.first, v.second, 1);
for(auto &v : NFV[0]) seg.updu(v.first, v.second, -1);
for(auto &v : NFV[1]) seg.updb(v.first, v.second, -1);
PFV[0].clear(); PFV[1].clear();
NFV[0].clear(); NFV[1].clear();
}
void give_initial_chart(int H, int W, std::vector<int> RV, std::vector<int> CV) {
::H = H; ::W = W; N = H*W;
for(int i = H+2; i--;) {
C[i] = newint(W+2);
C[i][0] = C[i][W+1] = INF;
}
fill(C[0], C[0]+W+2, INF);
fill(C[H+1], C[H+1]+W+2, INF);
for(int i = N; i--;) {
A[i] = RV[i] + 1;
B[i] = CV[i] + 1;
C[A[i]][B[i]] = i;
}
seg.init(N);
for(int y = 0; y <= H; y++) for(int x = 0; x <= W; x++) f(y, x);
run();
}
int swap_seats(int a, int b) {
g(a, true); g(b, true);
swap(C[A[a]][B[a]], C[A[b]][B[b]]);
swap(A[a], A[b]); swap(B[a], B[b]);
g(a); g(b);
run();
return seg.get();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
896 KB |
Output is correct |
2 |
Correct |
19 ms |
896 KB |
Output is correct |
3 |
Correct |
27 ms |
896 KB |
Output is correct |
4 |
Correct |
17 ms |
888 KB |
Output is correct |
5 |
Correct |
16 ms |
896 KB |
Output is correct |
6 |
Correct |
24 ms |
920 KB |
Output is correct |
7 |
Correct |
24 ms |
888 KB |
Output is correct |
8 |
Correct |
24 ms |
872 KB |
Output is correct |
9 |
Correct |
28 ms |
868 KB |
Output is correct |
10 |
Correct |
25 ms |
884 KB |
Output is correct |
11 |
Correct |
23 ms |
896 KB |
Output is correct |
12 |
Correct |
18 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
896 KB |
Output is correct |
2 |
Correct |
19 ms |
896 KB |
Output is correct |
3 |
Correct |
27 ms |
896 KB |
Output is correct |
4 |
Correct |
17 ms |
888 KB |
Output is correct |
5 |
Correct |
16 ms |
896 KB |
Output is correct |
6 |
Correct |
24 ms |
920 KB |
Output is correct |
7 |
Correct |
24 ms |
888 KB |
Output is correct |
8 |
Correct |
24 ms |
872 KB |
Output is correct |
9 |
Correct |
28 ms |
868 KB |
Output is correct |
10 |
Correct |
25 ms |
884 KB |
Output is correct |
11 |
Correct |
23 ms |
896 KB |
Output is correct |
12 |
Correct |
18 ms |
896 KB |
Output is correct |
13 |
Correct |
50 ms |
2296 KB |
Output is correct |
14 |
Correct |
73 ms |
2292 KB |
Output is correct |
15 |
Correct |
44 ms |
2348 KB |
Output is correct |
16 |
Correct |
32 ms |
2396 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
46 ms |
2424 KB |
Output is correct |
19 |
Correct |
45 ms |
2276 KB |
Output is correct |
20 |
Correct |
38 ms |
2424 KB |
Output is correct |
21 |
Correct |
31 ms |
2348 KB |
Output is correct |
22 |
Correct |
36 ms |
2476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1738 ms |
101584 KB |
Output is correct |
2 |
Correct |
811 ms |
101608 KB |
Output is correct |
3 |
Correct |
827 ms |
101492 KB |
Output is correct |
4 |
Correct |
677 ms |
99552 KB |
Output is correct |
5 |
Correct |
802 ms |
101608 KB |
Output is correct |
6 |
Correct |
751 ms |
99432 KB |
Output is correct |
7 |
Correct |
805 ms |
101652 KB |
Output is correct |
8 |
Correct |
890 ms |
99604 KB |
Output is correct |
9 |
Correct |
904 ms |
99680 KB |
Output is correct |
10 |
Correct |
847 ms |
100628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
2304 KB |
Output is correct |
2 |
Correct |
139 ms |
11976 KB |
Output is correct |
3 |
Correct |
781 ms |
101096 KB |
Output is correct |
4 |
Correct |
1607 ms |
101608 KB |
Output is correct |
5 |
Correct |
768 ms |
114744 KB |
Output is correct |
6 |
Correct |
1646 ms |
124608 KB |
Output is correct |
7 |
Correct |
819 ms |
106836 KB |
Output is correct |
8 |
Correct |
815 ms |
101736 KB |
Output is correct |
9 |
Correct |
860 ms |
98920 KB |
Output is correct |
10 |
Correct |
801 ms |
103804 KB |
Output is correct |
11 |
Correct |
811 ms |
114112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
1752 KB |
Output is correct |
2 |
Correct |
104 ms |
1824 KB |
Output is correct |
3 |
Correct |
155 ms |
1840 KB |
Output is correct |
4 |
Correct |
203 ms |
2036 KB |
Output is correct |
5 |
Correct |
267 ms |
3280 KB |
Output is correct |
6 |
Correct |
1043 ms |
116252 KB |
Output is correct |
7 |
Correct |
1358 ms |
117520 KB |
Output is correct |
8 |
Correct |
1042 ms |
115216 KB |
Output is correct |
9 |
Correct |
2290 ms |
117228 KB |
Output is correct |
10 |
Correct |
1176 ms |
116340 KB |
Output is correct |
11 |
Correct |
1176 ms |
116360 KB |
Output is correct |
12 |
Correct |
1234 ms |
115228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
896 KB |
Output is correct |
2 |
Correct |
19 ms |
896 KB |
Output is correct |
3 |
Correct |
27 ms |
896 KB |
Output is correct |
4 |
Correct |
17 ms |
888 KB |
Output is correct |
5 |
Correct |
16 ms |
896 KB |
Output is correct |
6 |
Correct |
24 ms |
920 KB |
Output is correct |
7 |
Correct |
24 ms |
888 KB |
Output is correct |
8 |
Correct |
24 ms |
872 KB |
Output is correct |
9 |
Correct |
28 ms |
868 KB |
Output is correct |
10 |
Correct |
25 ms |
884 KB |
Output is correct |
11 |
Correct |
23 ms |
896 KB |
Output is correct |
12 |
Correct |
18 ms |
896 KB |
Output is correct |
13 |
Correct |
50 ms |
2296 KB |
Output is correct |
14 |
Correct |
73 ms |
2292 KB |
Output is correct |
15 |
Correct |
44 ms |
2348 KB |
Output is correct |
16 |
Correct |
32 ms |
2396 KB |
Output is correct |
17 |
Correct |
58 ms |
2432 KB |
Output is correct |
18 |
Correct |
46 ms |
2424 KB |
Output is correct |
19 |
Correct |
45 ms |
2276 KB |
Output is correct |
20 |
Correct |
38 ms |
2424 KB |
Output is correct |
21 |
Correct |
31 ms |
2348 KB |
Output is correct |
22 |
Correct |
36 ms |
2476 KB |
Output is correct |
23 |
Correct |
1738 ms |
101584 KB |
Output is correct |
24 |
Correct |
811 ms |
101608 KB |
Output is correct |
25 |
Correct |
827 ms |
101492 KB |
Output is correct |
26 |
Correct |
677 ms |
99552 KB |
Output is correct |
27 |
Correct |
802 ms |
101608 KB |
Output is correct |
28 |
Correct |
751 ms |
99432 KB |
Output is correct |
29 |
Correct |
805 ms |
101652 KB |
Output is correct |
30 |
Correct |
890 ms |
99604 KB |
Output is correct |
31 |
Correct |
904 ms |
99680 KB |
Output is correct |
32 |
Correct |
847 ms |
100628 KB |
Output is correct |
33 |
Correct |
54 ms |
2304 KB |
Output is correct |
34 |
Correct |
139 ms |
11976 KB |
Output is correct |
35 |
Correct |
781 ms |
101096 KB |
Output is correct |
36 |
Correct |
1607 ms |
101608 KB |
Output is correct |
37 |
Correct |
768 ms |
114744 KB |
Output is correct |
38 |
Correct |
1646 ms |
124608 KB |
Output is correct |
39 |
Correct |
819 ms |
106836 KB |
Output is correct |
40 |
Correct |
815 ms |
101736 KB |
Output is correct |
41 |
Correct |
860 ms |
98920 KB |
Output is correct |
42 |
Correct |
801 ms |
103804 KB |
Output is correct |
43 |
Correct |
811 ms |
114112 KB |
Output is correct |
44 |
Correct |
62 ms |
1752 KB |
Output is correct |
45 |
Correct |
104 ms |
1824 KB |
Output is correct |
46 |
Correct |
155 ms |
1840 KB |
Output is correct |
47 |
Correct |
203 ms |
2036 KB |
Output is correct |
48 |
Correct |
267 ms |
3280 KB |
Output is correct |
49 |
Correct |
1043 ms |
116252 KB |
Output is correct |
50 |
Correct |
1358 ms |
117520 KB |
Output is correct |
51 |
Correct |
1042 ms |
115216 KB |
Output is correct |
52 |
Correct |
2290 ms |
117228 KB |
Output is correct |
53 |
Correct |
1176 ms |
116340 KB |
Output is correct |
54 |
Correct |
1176 ms |
116360 KB |
Output is correct |
55 |
Correct |
1234 ms |
115228 KB |
Output is correct |
56 |
Correct |
129 ms |
1856 KB |
Output is correct |
57 |
Correct |
249 ms |
1908 KB |
Output is correct |
58 |
Correct |
418 ms |
3160 KB |
Output is correct |
59 |
Correct |
1391 ms |
99896 KB |
Output is correct |
60 |
Correct |
2699 ms |
101956 KB |
Output is correct |
61 |
Correct |
1386 ms |
99844 KB |
Output is correct |
62 |
Correct |
1463 ms |
106696 KB |
Output is correct |
63 |
Correct |
2464 ms |
109876 KB |
Output is correct |
64 |
Correct |
1647 ms |
104216 KB |
Output is correct |
65 |
Correct |
1729 ms |
100284 KB |
Output is correct |
66 |
Correct |
1567 ms |
96412 KB |
Output is correct |
67 |
Correct |
1727 ms |
105132 KB |
Output is correct |
68 |
Correct |
1415 ms |
110992 KB |
Output is correct |
69 |
Correct |
2824 ms |
117528 KB |
Output is correct |