# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
116051 |
2019-06-10T09:34:13 Z |
roseanne_pcy |
Seats (IOI18_seats) |
C++14 |
|
1785 ms |
141688 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "seats.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e6+5;
int n, m;
int tot;
int r[maxn];
struct node
{
int val, cnt, lz;
node(int a = 0, int b = 0) : val(a), cnt(b)
{
lz = 0;
}
};
node st[4*maxn];
node pull(node &x, node &y)
{
if(x.val< y.val) return x;
if(x.val> y.val) return y;
return node(x.val, x.cnt+y.cnt);
}
void pushdown(int p, int L, int R)
{
if(st[p].lz == 0) return;
st[p].val += st[p].lz;
if(L != R)
{
st[2*p].lz += st[p].lz;
st[2*p+1].lz += st[p].lz;
}
st[p].lz = 0;
}
void build(int p = 1, int L = 0, int R = tot-1)
{
if(L == R)
{
st[p] = node(0, 1);
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int dx, int p = 1, int L = 0, int R = tot-1)
{
pushdown(p, L, R);
if(i> j || i> R || j< L) return;
if(i<= L && R<= j)
{
st[p].lz += dx;
pushdown(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, 2*p, L, M);
update(i, j, dx, 2*p+1, M+1, R);
st[p] = pull(st[2*p], st[2*p+1]);
}
node ask(int i, int j, int p = 1, int L = 0, int R = tot-1)
{
if(i> R || j< L) return node(1e9, 0);
pushdown(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
node x = ask(i, j, 2*p, L, M);
node y = ask(i, j, 2*p+1, M+1, R);
return pull(x, y);
}
vector< vector<int> > bow;
int row[maxn];
int col[maxn];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
void add(int x, int y, int a, int b)
{
// printf("add %d to [%d %d]\n", val, a, b);
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
// printf("%d ", pos);
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
// printf("\n");
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), 1);
update(max(a, t0), min(t1-1, b), -1);
update(max(a, t1), min(t2-1, b), 1);
update(max(a, t2), b, -1);
}
}
void rem(int x, int y, int a, int b)
{
for(int base = 0; base< 8; base += 2)
{
vector<int> t;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 1e9;
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]];
}
t.pb(loc);
}
sort(t.begin(), t.end());
int t0 = t[0], t1 = t[1], t2 = t[2];
// printf("%d %d %d\n", t0, t1, t2);
update(a, min(t0-1, b), -1);
update(max(a, t0), min(t1-1, b), 1);
update(max(a, t1), min(t2-1, b), -1);
update(max(a, t2), b, 1);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
n = H; m = W;
tot = n*m;
bow.assign(n, vector<int>(m));
build();
int prv = 0;
for(int i = 0; i< tot; i++)
{
bow[R[i]][C[i]] = i;
row[i] = R[i];
col[i] = C[i];
}
for(int i = 0; i< tot; i++)
{
int cur = prv;
for(int base = 0; base< 8; base += 2)
{
int cnt = 0;
for(int pp = base; pp<= base+2; pp++)
{
int pos = pp%8;
int loc = 0;
int x = row[i], y = col[i];
if(0<= x+dx[pos] && x+dx[pos]< n && 0<= y+dy[pos] && y+dy[pos]< m)
{
loc = bow[x+dx[pos]][y+dy[pos]]< i;
}
cnt += loc;
}
if(cnt == 1 || cnt == 3) cur--;
else cur++;
}
update(i, i, cur);
// printf("f[%d] = %d\n", i, cur);
prv = cur;
}
// printf("(%d, %d)\n", kk.val, kk.cnt);
}
int swap_seats(int a, int b)
{
if(a> b) swap(a, b);
rem(row[a], col[a], a, b-1);
// printf("finished reming\n");
// printf("f' = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
swap(bow[row[a]][col[a]], bow[row[b]][col[b]]);
add(row[b], col[b], a, b-1);
swap(row[a], row[b]);
swap(col[a], col[b]);
node kk = ask(0, tot-1);
// printf("f = ");
// for(int i = 0; i< tot; i++) printf("%d ", ask(i, i).val);
// printf("\n");
// printf("(%d, %d)\n", kk.val, kk.cnt);
if(kk.val == 4) return kk.cnt;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
47480 KB |
Output is correct |
2 |
Correct |
59 ms |
47480 KB |
Output is correct |
3 |
Correct |
63 ms |
47352 KB |
Output is correct |
4 |
Correct |
76 ms |
47480 KB |
Output is correct |
5 |
Correct |
57 ms |
47352 KB |
Output is correct |
6 |
Correct |
62 ms |
47452 KB |
Output is correct |
7 |
Correct |
63 ms |
47552 KB |
Output is correct |
8 |
Correct |
63 ms |
47484 KB |
Output is correct |
9 |
Correct |
64 ms |
47480 KB |
Output is correct |
10 |
Correct |
62 ms |
47452 KB |
Output is correct |
11 |
Correct |
68 ms |
47352 KB |
Output is correct |
12 |
Correct |
59 ms |
47480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
47480 KB |
Output is correct |
2 |
Correct |
59 ms |
47480 KB |
Output is correct |
3 |
Correct |
63 ms |
47352 KB |
Output is correct |
4 |
Correct |
76 ms |
47480 KB |
Output is correct |
5 |
Correct |
57 ms |
47352 KB |
Output is correct |
6 |
Correct |
62 ms |
47452 KB |
Output is correct |
7 |
Correct |
63 ms |
47552 KB |
Output is correct |
8 |
Correct |
63 ms |
47484 KB |
Output is correct |
9 |
Correct |
64 ms |
47480 KB |
Output is correct |
10 |
Correct |
62 ms |
47452 KB |
Output is correct |
11 |
Correct |
68 ms |
47352 KB |
Output is correct |
12 |
Correct |
59 ms |
47480 KB |
Output is correct |
13 |
Correct |
86 ms |
47864 KB |
Output is correct |
14 |
Correct |
87 ms |
47736 KB |
Output is correct |
15 |
Correct |
77 ms |
47808 KB |
Output is correct |
16 |
Correct |
73 ms |
48248 KB |
Output is correct |
17 |
Correct |
82 ms |
47800 KB |
Output is correct |
18 |
Correct |
84 ms |
47816 KB |
Output is correct |
19 |
Correct |
86 ms |
47828 KB |
Output is correct |
20 |
Correct |
87 ms |
47956 KB |
Output is correct |
21 |
Correct |
72 ms |
47728 KB |
Output is correct |
22 |
Correct |
76 ms |
48336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
902 ms |
85784 KB |
Output is correct |
2 |
Correct |
711 ms |
86472 KB |
Output is correct |
3 |
Correct |
683 ms |
86524 KB |
Output is correct |
4 |
Correct |
653 ms |
87544 KB |
Output is correct |
5 |
Correct |
682 ms |
86660 KB |
Output is correct |
6 |
Correct |
632 ms |
86520 KB |
Output is correct |
7 |
Correct |
669 ms |
86392 KB |
Output is correct |
8 |
Correct |
693 ms |
86284 KB |
Output is correct |
9 |
Correct |
697 ms |
86392 KB |
Output is correct |
10 |
Correct |
681 ms |
86336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
47840 KB |
Output is correct |
2 |
Correct |
146 ms |
51108 KB |
Output is correct |
3 |
Correct |
651 ms |
90852 KB |
Output is correct |
4 |
Correct |
834 ms |
90852 KB |
Output is correct |
5 |
Correct |
619 ms |
90732 KB |
Output is correct |
6 |
Correct |
1244 ms |
141688 KB |
Output is correct |
7 |
Correct |
672 ms |
90720 KB |
Output is correct |
8 |
Correct |
696 ms |
90656 KB |
Output is correct |
9 |
Correct |
718 ms |
91000 KB |
Output is correct |
10 |
Correct |
674 ms |
93804 KB |
Output is correct |
11 |
Correct |
690 ms |
114296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
48884 KB |
Output is correct |
2 |
Correct |
165 ms |
48908 KB |
Output is correct |
3 |
Correct |
222 ms |
49028 KB |
Output is correct |
4 |
Correct |
272 ms |
49012 KB |
Output is correct |
5 |
Correct |
361 ms |
49396 KB |
Output is correct |
6 |
Correct |
1056 ms |
75184 KB |
Output is correct |
7 |
Correct |
1103 ms |
75232 KB |
Output is correct |
8 |
Correct |
1024 ms |
75312 KB |
Output is correct |
9 |
Correct |
1354 ms |
75184 KB |
Output is correct |
10 |
Correct |
1058 ms |
75160 KB |
Output is correct |
11 |
Correct |
990 ms |
75352 KB |
Output is correct |
12 |
Correct |
965 ms |
75312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
47480 KB |
Output is correct |
2 |
Correct |
59 ms |
47480 KB |
Output is correct |
3 |
Correct |
63 ms |
47352 KB |
Output is correct |
4 |
Correct |
76 ms |
47480 KB |
Output is correct |
5 |
Correct |
57 ms |
47352 KB |
Output is correct |
6 |
Correct |
62 ms |
47452 KB |
Output is correct |
7 |
Correct |
63 ms |
47552 KB |
Output is correct |
8 |
Correct |
63 ms |
47484 KB |
Output is correct |
9 |
Correct |
64 ms |
47480 KB |
Output is correct |
10 |
Correct |
62 ms |
47452 KB |
Output is correct |
11 |
Correct |
68 ms |
47352 KB |
Output is correct |
12 |
Correct |
59 ms |
47480 KB |
Output is correct |
13 |
Correct |
86 ms |
47864 KB |
Output is correct |
14 |
Correct |
87 ms |
47736 KB |
Output is correct |
15 |
Correct |
77 ms |
47808 KB |
Output is correct |
16 |
Correct |
73 ms |
48248 KB |
Output is correct |
17 |
Correct |
82 ms |
47800 KB |
Output is correct |
18 |
Correct |
84 ms |
47816 KB |
Output is correct |
19 |
Correct |
86 ms |
47828 KB |
Output is correct |
20 |
Correct |
87 ms |
47956 KB |
Output is correct |
21 |
Correct |
72 ms |
47728 KB |
Output is correct |
22 |
Correct |
76 ms |
48336 KB |
Output is correct |
23 |
Correct |
902 ms |
85784 KB |
Output is correct |
24 |
Correct |
711 ms |
86472 KB |
Output is correct |
25 |
Correct |
683 ms |
86524 KB |
Output is correct |
26 |
Correct |
653 ms |
87544 KB |
Output is correct |
27 |
Correct |
682 ms |
86660 KB |
Output is correct |
28 |
Correct |
632 ms |
86520 KB |
Output is correct |
29 |
Correct |
669 ms |
86392 KB |
Output is correct |
30 |
Correct |
693 ms |
86284 KB |
Output is correct |
31 |
Correct |
697 ms |
86392 KB |
Output is correct |
32 |
Correct |
681 ms |
86336 KB |
Output is correct |
33 |
Correct |
92 ms |
47840 KB |
Output is correct |
34 |
Correct |
146 ms |
51108 KB |
Output is correct |
35 |
Correct |
651 ms |
90852 KB |
Output is correct |
36 |
Correct |
834 ms |
90852 KB |
Output is correct |
37 |
Correct |
619 ms |
90732 KB |
Output is correct |
38 |
Correct |
1244 ms |
141688 KB |
Output is correct |
39 |
Correct |
672 ms |
90720 KB |
Output is correct |
40 |
Correct |
696 ms |
90656 KB |
Output is correct |
41 |
Correct |
718 ms |
91000 KB |
Output is correct |
42 |
Correct |
674 ms |
93804 KB |
Output is correct |
43 |
Correct |
690 ms |
114296 KB |
Output is correct |
44 |
Correct |
135 ms |
48884 KB |
Output is correct |
45 |
Correct |
165 ms |
48908 KB |
Output is correct |
46 |
Correct |
222 ms |
49028 KB |
Output is correct |
47 |
Correct |
272 ms |
49012 KB |
Output is correct |
48 |
Correct |
361 ms |
49396 KB |
Output is correct |
49 |
Correct |
1056 ms |
75184 KB |
Output is correct |
50 |
Correct |
1103 ms |
75232 KB |
Output is correct |
51 |
Correct |
1024 ms |
75312 KB |
Output is correct |
52 |
Correct |
1354 ms |
75184 KB |
Output is correct |
53 |
Correct |
1058 ms |
75160 KB |
Output is correct |
54 |
Correct |
990 ms |
75352 KB |
Output is correct |
55 |
Correct |
965 ms |
75312 KB |
Output is correct |
56 |
Correct |
165 ms |
49012 KB |
Output is correct |
57 |
Correct |
267 ms |
49208 KB |
Output is correct |
58 |
Correct |
502 ms |
49568 KB |
Output is correct |
59 |
Correct |
1390 ms |
91896 KB |
Output is correct |
60 |
Correct |
1625 ms |
91792 KB |
Output is correct |
61 |
Correct |
1229 ms |
91780 KB |
Output is correct |
62 |
Correct |
1031 ms |
91752 KB |
Output is correct |
63 |
Correct |
1498 ms |
91788 KB |
Output is correct |
64 |
Correct |
1342 ms |
91756 KB |
Output is correct |
65 |
Correct |
1363 ms |
91768 KB |
Output is correct |
66 |
Correct |
1406 ms |
92252 KB |
Output is correct |
67 |
Correct |
1383 ms |
94840 KB |
Output is correct |
68 |
Correct |
1202 ms |
106000 KB |
Output is correct |
69 |
Correct |
1785 ms |
115332 KB |
Output is correct |