# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282062 |
2020-08-23T23:09:47 Z |
doowey |
Seats (IOI18_seats) |
C++14 |
|
2660 ms |
99652 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int M = (int)1e6 + 10;
int cur;
int pi[M], pj[M];
vector<vector<int>> tt;
int val[M * 4 + 512];
int cnt[M * 4 + 512];
int lazy[M * 4 + 512];
void push(int node, int cl, int cr){
val[node] += lazy[node];
if(cl != cr){
lazy[node << 1] += lazy[node];
lazy[node << 1 | 1] += lazy[node];
}
lazy[node] = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, int x){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
lazy[node] = x;
push(node, cl, cr);
return;
}
int mid = (cl + cr) >> 1;
upd(node << 1, cl, mid, tl, tr, x);
upd(node << 1 | 1, mid + 1, cr, tl, tr, x);
val[node] = val[node << 1];
cnt[node] = cnt[node << 1];
if(val[node << 1 | 1] == val[node]){
cnt[node] += cnt[node << 1 | 1];
}
else if(val[node << 1 | 1] < val[node]){
val[node] = val[node << 1 | 1];
cnt[node] = cnt[node << 1 | 1];
}
}
void upd_rect(int i, int j, int v){
vector<int> tc;
for(int p = 0; p < 2; p ++ ){
for(int q = 0; q < 2; q ++ ){
tc.push_back(tt[i + p][j + q]);
}
}
sort(tc.begin(), tc.end());
if(tc[0] < tc[1])
upd(1, 0, cur - 1, tc[0], tc[1] - 1, v);
if(tc[2] < tc[3])
upd(1, 0, cur - 1, tc[2], tc[3] - 1, 4 * v);
}
int pf[M];
void build(int node, int cl, int cr){
if(cl == cr){
cnt[node] = 1;
val[node] = pf[cl];
return;
}
int mid = (cl + cr) >> 1;
build(node << 1, cl, mid);
build(node << 1 | 1, mid + 1, cr);
val[node] = val[node << 1];
cnt[node] = cnt[node << 1];
if(val[node << 1 | 1] == val[node]){
cnt[node] += cnt[node << 1 | 1];
}
else if(val[node << 1 | 1] < val[node]){
val[node] = val[node << 1 | 1];
cnt[node] = cnt[node << 1 | 1];
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
cur = H * W;
tt.resize(H + 2);
for(int i = 0 ; i <= H + 1;i ++ )
tt[i].resize(W + 2, cur);
for(int i = 0 ; i < cur ;i ++ ){
R[i] ++ ;
C[i] ++ ;
pi[i] = R[i];
pj[i] = C[i];
tt[R[i]][C[i]] = i;
}
for(int i = 0 ; i <= H; i ++ ){
for(int j = 0 ; j <= W; j ++ ){
vector<int> pq;
for(int l = 0; l < 2; l ++ ){
for(int r = 0; r < 2; r ++ ){
pq.push_back(tt[i + l][j + r]);
}
}
sort(pq.begin(), pq.end());
pf[pq[0]] ++ ;
pf[pq[1]] -- ;
pf[pq[2]] += 4 ;
pf[pq[3]] -= 4 ;
}
}
for(int i = 1; i < cur; i ++ ){
pf[i] += pf[i - 1];
}
build(1, 0, cur - 1);
}
int swap_seats(int a, int b) {
vector<pii> nigs;
for(int i = 0; i <= 1; i ++ ){
for(int j = 0; j <= 1 ; j ++ ){
nigs.push_back(mp(pi[a] - i, pj[a] - j));
nigs.push_back(mp(pi[b] - i, pj[b] - j));
}
}
sort(nigs.begin(), nigs.end());
nigs.resize(unique(nigs.begin(), nigs.end()) - nigs.begin());
for(auto x : nigs)
upd_rect(x.fi, x.se, -1);
swap(tt[pi[a]][pj[a]], tt[pi[b]][pj[b]]);
swap(pi[a], pi[b]);
swap(pj[a], pj[b]);
for(auto x : nigs)
upd_rect(x.fi, x.se, +1);
return cnt[1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
36 ms |
504 KB |
Output is correct |
3 |
Correct |
46 ms |
504 KB |
Output is correct |
4 |
Correct |
33 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
636 KB |
Output is correct |
6 |
Correct |
42 ms |
512 KB |
Output is correct |
7 |
Correct |
44 ms |
508 KB |
Output is correct |
8 |
Correct |
42 ms |
504 KB |
Output is correct |
9 |
Correct |
48 ms |
504 KB |
Output is correct |
10 |
Correct |
44 ms |
512 KB |
Output is correct |
11 |
Correct |
43 ms |
632 KB |
Output is correct |
12 |
Correct |
36 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
36 ms |
504 KB |
Output is correct |
3 |
Correct |
46 ms |
504 KB |
Output is correct |
4 |
Correct |
33 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
636 KB |
Output is correct |
6 |
Correct |
42 ms |
512 KB |
Output is correct |
7 |
Correct |
44 ms |
508 KB |
Output is correct |
8 |
Correct |
42 ms |
504 KB |
Output is correct |
9 |
Correct |
48 ms |
504 KB |
Output is correct |
10 |
Correct |
44 ms |
512 KB |
Output is correct |
11 |
Correct |
43 ms |
632 KB |
Output is correct |
12 |
Correct |
36 ms |
504 KB |
Output is correct |
13 |
Correct |
93 ms |
1152 KB |
Output is correct |
14 |
Correct |
106 ms |
1152 KB |
Output is correct |
15 |
Correct |
65 ms |
1224 KB |
Output is correct |
16 |
Correct |
60 ms |
1652 KB |
Output is correct |
17 |
Correct |
77 ms |
1152 KB |
Output is correct |
18 |
Correct |
78 ms |
1152 KB |
Output is correct |
19 |
Correct |
77 ms |
1272 KB |
Output is correct |
20 |
Correct |
68 ms |
1400 KB |
Output is correct |
21 |
Correct |
65 ms |
1152 KB |
Output is correct |
22 |
Correct |
60 ms |
1784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
849 ms |
48644 KB |
Output is correct |
2 |
Correct |
685 ms |
48640 KB |
Output is correct |
3 |
Correct |
701 ms |
48580 KB |
Output is correct |
4 |
Correct |
659 ms |
48736 KB |
Output is correct |
5 |
Correct |
657 ms |
48672 KB |
Output is correct |
6 |
Correct |
689 ms |
48744 KB |
Output is correct |
7 |
Correct |
721 ms |
48612 KB |
Output is correct |
8 |
Correct |
673 ms |
48752 KB |
Output is correct |
9 |
Correct |
679 ms |
48740 KB |
Output is correct |
10 |
Correct |
649 ms |
48736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
1152 KB |
Output is correct |
2 |
Correct |
152 ms |
5688 KB |
Output is correct |
3 |
Correct |
649 ms |
48676 KB |
Output is correct |
4 |
Correct |
835 ms |
48804 KB |
Output is correct |
5 |
Correct |
751 ms |
56516 KB |
Output is correct |
6 |
Correct |
1165 ms |
99652 KB |
Output is correct |
7 |
Correct |
689 ms |
51304 KB |
Output is correct |
8 |
Correct |
678 ms |
48772 KB |
Output is correct |
9 |
Correct |
677 ms |
49032 KB |
Output is correct |
10 |
Correct |
723 ms |
53316 KB |
Output is correct |
11 |
Correct |
788 ms |
72320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
1396 KB |
Output is correct |
2 |
Correct |
222 ms |
1396 KB |
Output is correct |
3 |
Correct |
305 ms |
1656 KB |
Output is correct |
4 |
Correct |
391 ms |
1524 KB |
Output is correct |
5 |
Correct |
589 ms |
2272 KB |
Output is correct |
6 |
Correct |
1536 ms |
57444 KB |
Output is correct |
7 |
Correct |
1556 ms |
57476 KB |
Output is correct |
8 |
Correct |
1539 ms |
57536 KB |
Output is correct |
9 |
Correct |
1892 ms |
57488 KB |
Output is correct |
10 |
Correct |
1446 ms |
74212 KB |
Output is correct |
11 |
Correct |
1410 ms |
74084 KB |
Output is correct |
12 |
Correct |
1388 ms |
74212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
512 KB |
Output is correct |
2 |
Correct |
36 ms |
504 KB |
Output is correct |
3 |
Correct |
46 ms |
504 KB |
Output is correct |
4 |
Correct |
33 ms |
504 KB |
Output is correct |
5 |
Correct |
31 ms |
636 KB |
Output is correct |
6 |
Correct |
42 ms |
512 KB |
Output is correct |
7 |
Correct |
44 ms |
508 KB |
Output is correct |
8 |
Correct |
42 ms |
504 KB |
Output is correct |
9 |
Correct |
48 ms |
504 KB |
Output is correct |
10 |
Correct |
44 ms |
512 KB |
Output is correct |
11 |
Correct |
43 ms |
632 KB |
Output is correct |
12 |
Correct |
36 ms |
504 KB |
Output is correct |
13 |
Correct |
93 ms |
1152 KB |
Output is correct |
14 |
Correct |
106 ms |
1152 KB |
Output is correct |
15 |
Correct |
65 ms |
1224 KB |
Output is correct |
16 |
Correct |
60 ms |
1652 KB |
Output is correct |
17 |
Correct |
77 ms |
1152 KB |
Output is correct |
18 |
Correct |
78 ms |
1152 KB |
Output is correct |
19 |
Correct |
77 ms |
1272 KB |
Output is correct |
20 |
Correct |
68 ms |
1400 KB |
Output is correct |
21 |
Correct |
65 ms |
1152 KB |
Output is correct |
22 |
Correct |
60 ms |
1784 KB |
Output is correct |
23 |
Correct |
849 ms |
48644 KB |
Output is correct |
24 |
Correct |
685 ms |
48640 KB |
Output is correct |
25 |
Correct |
701 ms |
48580 KB |
Output is correct |
26 |
Correct |
659 ms |
48736 KB |
Output is correct |
27 |
Correct |
657 ms |
48672 KB |
Output is correct |
28 |
Correct |
689 ms |
48744 KB |
Output is correct |
29 |
Correct |
721 ms |
48612 KB |
Output is correct |
30 |
Correct |
673 ms |
48752 KB |
Output is correct |
31 |
Correct |
679 ms |
48740 KB |
Output is correct |
32 |
Correct |
649 ms |
48736 KB |
Output is correct |
33 |
Correct |
92 ms |
1152 KB |
Output is correct |
34 |
Correct |
152 ms |
5688 KB |
Output is correct |
35 |
Correct |
649 ms |
48676 KB |
Output is correct |
36 |
Correct |
835 ms |
48804 KB |
Output is correct |
37 |
Correct |
751 ms |
56516 KB |
Output is correct |
38 |
Correct |
1165 ms |
99652 KB |
Output is correct |
39 |
Correct |
689 ms |
51304 KB |
Output is correct |
40 |
Correct |
678 ms |
48772 KB |
Output is correct |
41 |
Correct |
677 ms |
49032 KB |
Output is correct |
42 |
Correct |
723 ms |
53316 KB |
Output is correct |
43 |
Correct |
788 ms |
72320 KB |
Output is correct |
44 |
Correct |
166 ms |
1396 KB |
Output is correct |
45 |
Correct |
222 ms |
1396 KB |
Output is correct |
46 |
Correct |
305 ms |
1656 KB |
Output is correct |
47 |
Correct |
391 ms |
1524 KB |
Output is correct |
48 |
Correct |
589 ms |
2272 KB |
Output is correct |
49 |
Correct |
1536 ms |
57444 KB |
Output is correct |
50 |
Correct |
1556 ms |
57476 KB |
Output is correct |
51 |
Correct |
1539 ms |
57536 KB |
Output is correct |
52 |
Correct |
1892 ms |
57488 KB |
Output is correct |
53 |
Correct |
1446 ms |
74212 KB |
Output is correct |
54 |
Correct |
1410 ms |
74084 KB |
Output is correct |
55 |
Correct |
1388 ms |
74212 KB |
Output is correct |
56 |
Correct |
233 ms |
2036 KB |
Output is correct |
57 |
Correct |
461 ms |
2128 KB |
Output is correct |
58 |
Correct |
769 ms |
3000 KB |
Output is correct |
59 |
Correct |
1965 ms |
66528 KB |
Output is correct |
60 |
Correct |
2660 ms |
66284 KB |
Output is correct |
61 |
Correct |
1765 ms |
66276 KB |
Output is correct |
62 |
Correct |
1587 ms |
70116 KB |
Output is correct |
63 |
Correct |
2534 ms |
68836 KB |
Output is correct |
64 |
Correct |
1860 ms |
67044 KB |
Output is correct |
65 |
Correct |
1677 ms |
66308 KB |
Output is correct |
66 |
Correct |
1982 ms |
66660 KB |
Output is correct |
67 |
Correct |
1914 ms |
71020 KB |
Output is correct |
68 |
Correct |
1669 ms |
80868 KB |
Output is correct |
69 |
Correct |
2540 ms |
89748 KB |
Output is correct |