#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
int h, w, lz[1<<21], b[1000001];
vector<int> r, c;
vector<vector<int>> a;
ar<int, 2> st[1<<21];
void cmb(int i) {
st[i]={min(st[2*i][0], st[2*i+1][0])};
st[i][1]=(st[2*i][0]>st[i][0]?0:st[2*i][1])+(st[2*i+1][0]>st[i][0]?0:st[2*i+1][1]);
}
void bld(int i=1, int l2=0, int r2=h*w-1) {
if(l2==r2) {
st[i]={b[l2], 1};
return;
}
int m2=(l2+r2)/2;
bld(2*i, l2, m2);
bld(2*i+1, m2+1, r2);
cmb(i);
}
void app(int i, int x) {
st[i][0]+=x;
lz[i]+=x;
}
void upd(int l1, int r1, int x, int i=1, int l2=0, int r2=h*w-1) {
if(!st[1][1]) {
b[l1]+=x;
b[r1+1]-=x;
return;
}
if(l1<=l2&&r2<=r1) {
app(i, x);
return;
}
int m2=(l2+r2)/2;
app(2*i, lz[i]);
app(2*i+1, lz[i]);
lz[i]=0;
if(l1<=m2)
upd(l1, r1, x, 2*i, l2, m2);
if(m2<r1)
upd(l1, r1, x, 2*i+1, m2+1, r2);
cmb(i);
}
void cs(int x, int y, int z) {
vector<int> v;
for(int d=!x-1; d<(x<h); ++d)
for(int e=!y-1; e<(y<w); ++e)
v.push_back(a[x+d][y+e]);
sort(v.begin(), v.end());
upd(v[0], (v.size()>1?v[1]:h*w)-1, z);
if(v.size()>2)
upd(v[2], v[3]-1, z);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
::h=h;
::w=w;
::r=r;
::c=c;
a=vector<vector<int>>(h, vector<int>(w));
for(int i=0; i<h*w; ++i)
a[r[i]][c[i]]=i;
for(int i=0; i<=h; ++i)
for(int j=0; j<=w; ++j)
cs(i, j, 1);
for(int i=0; i<h*w; ++i)
b[i+1]+=b[i];
bld();
}
int swap_seats(int x, int y) {
vector<ar<int, 2>> v;
for(int i : {x, y})
for(int d : {0, 1})
for(int e : {0, 1})
v.push_back({r[i]+d, c[i]+e});
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
for(auto a : v)
cs(a[0], a[1], -1);
swap(a[r[x]][c[x]], a[r[y]][c[y]]);
swap(r[x], r[y]);
swap(c[x], c[y]);
for(auto a : v)
cs(a[0], a[1], 1);
return st[1][1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
512 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
46 ms |
632 KB |
Output is correct |
4 |
Correct |
28 ms |
512 KB |
Output is correct |
5 |
Correct |
25 ms |
512 KB |
Output is correct |
6 |
Correct |
38 ms |
512 KB |
Output is correct |
7 |
Correct |
42 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
512 KB |
Output is correct |
9 |
Correct |
39 ms |
512 KB |
Output is correct |
10 |
Correct |
41 ms |
512 KB |
Output is correct |
11 |
Correct |
39 ms |
512 KB |
Output is correct |
12 |
Correct |
26 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
512 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
46 ms |
632 KB |
Output is correct |
4 |
Correct |
28 ms |
512 KB |
Output is correct |
5 |
Correct |
25 ms |
512 KB |
Output is correct |
6 |
Correct |
38 ms |
512 KB |
Output is correct |
7 |
Correct |
42 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
512 KB |
Output is correct |
9 |
Correct |
39 ms |
512 KB |
Output is correct |
10 |
Correct |
41 ms |
512 KB |
Output is correct |
11 |
Correct |
39 ms |
512 KB |
Output is correct |
12 |
Correct |
26 ms |
512 KB |
Output is correct |
13 |
Correct |
85 ms |
1300 KB |
Output is correct |
14 |
Correct |
99 ms |
1280 KB |
Output is correct |
15 |
Correct |
54 ms |
1280 KB |
Output is correct |
16 |
Correct |
46 ms |
1824 KB |
Output is correct |
17 |
Correct |
74 ms |
1280 KB |
Output is correct |
18 |
Correct |
73 ms |
1328 KB |
Output is correct |
19 |
Correct |
70 ms |
1280 KB |
Output is correct |
20 |
Correct |
59 ms |
1536 KB |
Output is correct |
21 |
Correct |
45 ms |
1280 KB |
Output is correct |
22 |
Correct |
46 ms |
1792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
789 ms |
56308 KB |
Output is correct |
2 |
Correct |
641 ms |
56164 KB |
Output is correct |
3 |
Correct |
639 ms |
56168 KB |
Output is correct |
4 |
Correct |
628 ms |
56420 KB |
Output is correct |
5 |
Correct |
638 ms |
56320 KB |
Output is correct |
6 |
Correct |
641 ms |
56164 KB |
Output is correct |
7 |
Correct |
638 ms |
56184 KB |
Output is correct |
8 |
Correct |
636 ms |
56164 KB |
Output is correct |
9 |
Correct |
634 ms |
56180 KB |
Output is correct |
10 |
Correct |
633 ms |
56036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
1308 KB |
Output is correct |
2 |
Correct |
145 ms |
7088 KB |
Output is correct |
3 |
Correct |
619 ms |
55908 KB |
Output is correct |
4 |
Correct |
754 ms |
55652 KB |
Output is correct |
5 |
Correct |
611 ms |
55580 KB |
Output is correct |
6 |
Correct |
926 ms |
105956 KB |
Output is correct |
7 |
Correct |
620 ms |
54988 KB |
Output is correct |
8 |
Correct |
637 ms |
55012 KB |
Output is correct |
9 |
Correct |
634 ms |
55396 KB |
Output is correct |
10 |
Correct |
644 ms |
57972 KB |
Output is correct |
11 |
Correct |
684 ms |
78180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
2036 KB |
Output is correct |
2 |
Correct |
186 ms |
2088 KB |
Output is correct |
3 |
Correct |
251 ms |
2036 KB |
Output is correct |
4 |
Correct |
310 ms |
2164 KB |
Output is correct |
5 |
Correct |
485 ms |
3168 KB |
Output is correct |
6 |
Correct |
1258 ms |
51540 KB |
Output is correct |
7 |
Correct |
1262 ms |
53112 KB |
Output is correct |
8 |
Correct |
1235 ms |
51080 KB |
Output is correct |
9 |
Correct |
1498 ms |
52640 KB |
Output is correct |
10 |
Correct |
1163 ms |
51872 KB |
Output is correct |
11 |
Correct |
1173 ms |
50972 KB |
Output is correct |
12 |
Correct |
1128 ms |
50716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
512 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
46 ms |
632 KB |
Output is correct |
4 |
Correct |
28 ms |
512 KB |
Output is correct |
5 |
Correct |
25 ms |
512 KB |
Output is correct |
6 |
Correct |
38 ms |
512 KB |
Output is correct |
7 |
Correct |
42 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
512 KB |
Output is correct |
9 |
Correct |
39 ms |
512 KB |
Output is correct |
10 |
Correct |
41 ms |
512 KB |
Output is correct |
11 |
Correct |
39 ms |
512 KB |
Output is correct |
12 |
Correct |
26 ms |
512 KB |
Output is correct |
13 |
Correct |
85 ms |
1300 KB |
Output is correct |
14 |
Correct |
99 ms |
1280 KB |
Output is correct |
15 |
Correct |
54 ms |
1280 KB |
Output is correct |
16 |
Correct |
46 ms |
1824 KB |
Output is correct |
17 |
Correct |
74 ms |
1280 KB |
Output is correct |
18 |
Correct |
73 ms |
1328 KB |
Output is correct |
19 |
Correct |
70 ms |
1280 KB |
Output is correct |
20 |
Correct |
59 ms |
1536 KB |
Output is correct |
21 |
Correct |
45 ms |
1280 KB |
Output is correct |
22 |
Correct |
46 ms |
1792 KB |
Output is correct |
23 |
Correct |
789 ms |
56308 KB |
Output is correct |
24 |
Correct |
641 ms |
56164 KB |
Output is correct |
25 |
Correct |
639 ms |
56168 KB |
Output is correct |
26 |
Correct |
628 ms |
56420 KB |
Output is correct |
27 |
Correct |
638 ms |
56320 KB |
Output is correct |
28 |
Correct |
641 ms |
56164 KB |
Output is correct |
29 |
Correct |
638 ms |
56184 KB |
Output is correct |
30 |
Correct |
636 ms |
56164 KB |
Output is correct |
31 |
Correct |
634 ms |
56180 KB |
Output is correct |
32 |
Correct |
633 ms |
56036 KB |
Output is correct |
33 |
Correct |
84 ms |
1308 KB |
Output is correct |
34 |
Correct |
145 ms |
7088 KB |
Output is correct |
35 |
Correct |
619 ms |
55908 KB |
Output is correct |
36 |
Correct |
754 ms |
55652 KB |
Output is correct |
37 |
Correct |
611 ms |
55580 KB |
Output is correct |
38 |
Correct |
926 ms |
105956 KB |
Output is correct |
39 |
Correct |
620 ms |
54988 KB |
Output is correct |
40 |
Correct |
637 ms |
55012 KB |
Output is correct |
41 |
Correct |
634 ms |
55396 KB |
Output is correct |
42 |
Correct |
644 ms |
57972 KB |
Output is correct |
43 |
Correct |
684 ms |
78180 KB |
Output is correct |
44 |
Correct |
123 ms |
2036 KB |
Output is correct |
45 |
Correct |
186 ms |
2088 KB |
Output is correct |
46 |
Correct |
251 ms |
2036 KB |
Output is correct |
47 |
Correct |
310 ms |
2164 KB |
Output is correct |
48 |
Correct |
485 ms |
3168 KB |
Output is correct |
49 |
Correct |
1258 ms |
51540 KB |
Output is correct |
50 |
Correct |
1262 ms |
53112 KB |
Output is correct |
51 |
Correct |
1235 ms |
51080 KB |
Output is correct |
52 |
Correct |
1498 ms |
52640 KB |
Output is correct |
53 |
Correct |
1163 ms |
51872 KB |
Output is correct |
54 |
Correct |
1173 ms |
50972 KB |
Output is correct |
55 |
Correct |
1128 ms |
50716 KB |
Output is correct |
56 |
Correct |
227 ms |
2032 KB |
Output is correct |
57 |
Correct |
436 ms |
2036 KB |
Output is correct |
58 |
Correct |
696 ms |
2848 KB |
Output is correct |
59 |
Correct |
1713 ms |
50232 KB |
Output is correct |
60 |
Correct |
2382 ms |
50408 KB |
Output is correct |
61 |
Correct |
1547 ms |
66404 KB |
Output is correct |
62 |
Correct |
1358 ms |
66368 KB |
Output is correct |
63 |
Correct |
2064 ms |
66504 KB |
Output is correct |
64 |
Correct |
1700 ms |
66480 KB |
Output is correct |
65 |
Correct |
1503 ms |
66416 KB |
Output is correct |
66 |
Correct |
1773 ms |
66656 KB |
Output is correct |
67 |
Correct |
1661 ms |
69512 KB |
Output is correct |
68 |
Correct |
1451 ms |
80776 KB |
Output is correct |
69 |
Correct |
2089 ms |
89812 KB |
Output is correct |