#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
vector<int>A[1000007];
const int pot=1<<20;
int seg[2*pot+7];
int lzy[2*pot+7];
int ile[2*pot+7];
void push(int v)
{
seg[2*v]+=lzy[v];
seg[2*v+1]+=lzy[v];
lzy[2*v]+=lzy[v];
lzy[2*v+1]+=lzy[v];
lzy[v]=0;
}
void ins(int v,int a,int b,int l,int r,int x)
{
if(a<=l&&b>=r)
{
seg[v]+=x;
lzy[v]+=x;
return ;
}
if(r<a||l>b) return ;
push(v);
ins(2*v,a,b,l,(l+r)/2,x);
ins(2*v+1,a,b,(l+r)/2+1,r,x);
seg[v]=min(seg[2*v],seg[2*v+1]);
ile[v]=0;
if(seg[v]==seg[2*v]) ile[v]+=ile[2*v];
if(seg[v]==seg[2*v+1]) ile[v]+=ile[2*v+1];
}
void upd(int i,int j,int x)
{
vector<int>V={A[i][j],A[i+1][j],A[i][j+1],A[i+1][j+1]};
sort(all(V));
ins(1,V[0],V[1]-1,1,pot,x);
ins(1,V[2],V[3]-1,1,pot,x);
}
void S(int i,int j,int x)
{
upd(i-1,j-1,x);
upd(i,j-1,x);
upd(i-1,j,x);
upd(i,j,x);
}
vector<int>x,y;
void give_initial_chart(int h,int w,vector<int>R,vector<int>C)
{
x=R,y=C;
for(int i=0;i<=h+1;i++) A[i].resize(w+2,h*w+1);
for(int i=0;i<h*w;i++) A[x[i]+1][y[i]+1]=i+1;
for(int i=1;i<=h*w;i++) ile[i+pot-1]=1;
for(int i=h*w+1;i<=pot;i++) seg[i+pot-1]=inf;
for(int i=pot-1;i>0;i--)
{
seg[i]=min(seg[2*i],seg[2*i+1]);
ile[i]=ile[2*i]+ile[2*i+1];
}
for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) upd(i,j,1);
}
int swap_seats(int a, int b)
{
S(x[a]+1,y[a]+1,-1);
S(x[b]+1,y[b]+1,-1);
swap(A[x[a]+1][y[a]+1],A[x[b]+1][y[b]+1]);
swap(x[a],x[b]);
swap(y[a],y[b]);
S(x[a]+1,y[a]+1,1);
S(x[b]+1,y[b]+1,1);
return ile[1];
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
cout<<swap_seats(0, 5)<<endl;
cout<<swap_seats(0, 5)<<endl;
return 0;
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
36384 KB |
Output is correct |
2 |
Correct |
76 ms |
36268 KB |
Output is correct |
3 |
Correct |
80 ms |
36236 KB |
Output is correct |
4 |
Correct |
72 ms |
36300 KB |
Output is correct |
5 |
Correct |
72 ms |
36272 KB |
Output is correct |
6 |
Correct |
75 ms |
36284 KB |
Output is correct |
7 |
Correct |
80 ms |
36300 KB |
Output is correct |
8 |
Correct |
84 ms |
36304 KB |
Output is correct |
9 |
Correct |
85 ms |
36304 KB |
Output is correct |
10 |
Correct |
82 ms |
36352 KB |
Output is correct |
11 |
Correct |
77 ms |
36264 KB |
Output is correct |
12 |
Correct |
73 ms |
36288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
36384 KB |
Output is correct |
2 |
Correct |
76 ms |
36268 KB |
Output is correct |
3 |
Correct |
80 ms |
36236 KB |
Output is correct |
4 |
Correct |
72 ms |
36300 KB |
Output is correct |
5 |
Correct |
72 ms |
36272 KB |
Output is correct |
6 |
Correct |
75 ms |
36284 KB |
Output is correct |
7 |
Correct |
80 ms |
36300 KB |
Output is correct |
8 |
Correct |
84 ms |
36304 KB |
Output is correct |
9 |
Correct |
85 ms |
36304 KB |
Output is correct |
10 |
Correct |
82 ms |
36352 KB |
Output is correct |
11 |
Correct |
77 ms |
36264 KB |
Output is correct |
12 |
Correct |
73 ms |
36288 KB |
Output is correct |
13 |
Correct |
133 ms |
36796 KB |
Output is correct |
14 |
Correct |
119 ms |
36768 KB |
Output is correct |
15 |
Correct |
95 ms |
36860 KB |
Output is correct |
16 |
Correct |
98 ms |
37032 KB |
Output is correct |
17 |
Correct |
114 ms |
36760 KB |
Output is correct |
18 |
Correct |
99 ms |
36768 KB |
Output is correct |
19 |
Correct |
93 ms |
36692 KB |
Output is correct |
20 |
Correct |
85 ms |
36820 KB |
Output is correct |
21 |
Correct |
86 ms |
36844 KB |
Output is correct |
22 |
Correct |
85 ms |
36940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2061 ms |
75584 KB |
Output is correct |
2 |
Correct |
1226 ms |
91336 KB |
Output is correct |
3 |
Correct |
1286 ms |
91404 KB |
Output is correct |
4 |
Correct |
1072 ms |
91280 KB |
Output is correct |
5 |
Correct |
990 ms |
91320 KB |
Output is correct |
6 |
Correct |
1052 ms |
91192 KB |
Output is correct |
7 |
Correct |
1097 ms |
91312 KB |
Output is correct |
8 |
Correct |
1235 ms |
91312 KB |
Output is correct |
9 |
Correct |
1217 ms |
91308 KB |
Output is correct |
10 |
Correct |
1229 ms |
91320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
36768 KB |
Output is correct |
2 |
Correct |
202 ms |
39952 KB |
Output is correct |
3 |
Correct |
1004 ms |
91200 KB |
Output is correct |
4 |
Correct |
2029 ms |
91316 KB |
Output is correct |
5 |
Correct |
1278 ms |
99328 KB |
Output is correct |
6 |
Correct |
2253 ms |
118800 KB |
Output is correct |
7 |
Correct |
1161 ms |
93956 KB |
Output is correct |
8 |
Correct |
1115 ms |
91392 KB |
Output is correct |
9 |
Correct |
1052 ms |
91456 KB |
Output is correct |
10 |
Correct |
1129 ms |
93632 KB |
Output is correct |
11 |
Correct |
1139 ms |
103112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
515 ms |
37384 KB |
Output is correct |
2 |
Correct |
499 ms |
37832 KB |
Output is correct |
3 |
Correct |
512 ms |
37892 KB |
Output is correct |
4 |
Correct |
532 ms |
37880 KB |
Output is correct |
5 |
Correct |
593 ms |
38360 KB |
Output is correct |
6 |
Correct |
1904 ms |
100204 KB |
Output is correct |
7 |
Correct |
2041 ms |
100172 KB |
Output is correct |
8 |
Correct |
1817 ms |
100248 KB |
Output is correct |
9 |
Correct |
2917 ms |
100084 KB |
Output is correct |
10 |
Correct |
1839 ms |
100100 KB |
Output is correct |
11 |
Correct |
1776 ms |
100368 KB |
Output is correct |
12 |
Correct |
1761 ms |
100348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
36384 KB |
Output is correct |
2 |
Correct |
76 ms |
36268 KB |
Output is correct |
3 |
Correct |
80 ms |
36236 KB |
Output is correct |
4 |
Correct |
72 ms |
36300 KB |
Output is correct |
5 |
Correct |
72 ms |
36272 KB |
Output is correct |
6 |
Correct |
75 ms |
36284 KB |
Output is correct |
7 |
Correct |
80 ms |
36300 KB |
Output is correct |
8 |
Correct |
84 ms |
36304 KB |
Output is correct |
9 |
Correct |
85 ms |
36304 KB |
Output is correct |
10 |
Correct |
82 ms |
36352 KB |
Output is correct |
11 |
Correct |
77 ms |
36264 KB |
Output is correct |
12 |
Correct |
73 ms |
36288 KB |
Output is correct |
13 |
Correct |
133 ms |
36796 KB |
Output is correct |
14 |
Correct |
119 ms |
36768 KB |
Output is correct |
15 |
Correct |
95 ms |
36860 KB |
Output is correct |
16 |
Correct |
98 ms |
37032 KB |
Output is correct |
17 |
Correct |
114 ms |
36760 KB |
Output is correct |
18 |
Correct |
99 ms |
36768 KB |
Output is correct |
19 |
Correct |
93 ms |
36692 KB |
Output is correct |
20 |
Correct |
85 ms |
36820 KB |
Output is correct |
21 |
Correct |
86 ms |
36844 KB |
Output is correct |
22 |
Correct |
85 ms |
36940 KB |
Output is correct |
23 |
Correct |
2061 ms |
75584 KB |
Output is correct |
24 |
Correct |
1226 ms |
91336 KB |
Output is correct |
25 |
Correct |
1286 ms |
91404 KB |
Output is correct |
26 |
Correct |
1072 ms |
91280 KB |
Output is correct |
27 |
Correct |
990 ms |
91320 KB |
Output is correct |
28 |
Correct |
1052 ms |
91192 KB |
Output is correct |
29 |
Correct |
1097 ms |
91312 KB |
Output is correct |
30 |
Correct |
1235 ms |
91312 KB |
Output is correct |
31 |
Correct |
1217 ms |
91308 KB |
Output is correct |
32 |
Correct |
1229 ms |
91320 KB |
Output is correct |
33 |
Correct |
104 ms |
36768 KB |
Output is correct |
34 |
Correct |
202 ms |
39952 KB |
Output is correct |
35 |
Correct |
1004 ms |
91200 KB |
Output is correct |
36 |
Correct |
2029 ms |
91316 KB |
Output is correct |
37 |
Correct |
1278 ms |
99328 KB |
Output is correct |
38 |
Correct |
2253 ms |
118800 KB |
Output is correct |
39 |
Correct |
1161 ms |
93956 KB |
Output is correct |
40 |
Correct |
1115 ms |
91392 KB |
Output is correct |
41 |
Correct |
1052 ms |
91456 KB |
Output is correct |
42 |
Correct |
1129 ms |
93632 KB |
Output is correct |
43 |
Correct |
1139 ms |
103112 KB |
Output is correct |
44 |
Correct |
515 ms |
37384 KB |
Output is correct |
45 |
Correct |
499 ms |
37832 KB |
Output is correct |
46 |
Correct |
512 ms |
37892 KB |
Output is correct |
47 |
Correct |
532 ms |
37880 KB |
Output is correct |
48 |
Correct |
593 ms |
38360 KB |
Output is correct |
49 |
Correct |
1904 ms |
100204 KB |
Output is correct |
50 |
Correct |
2041 ms |
100172 KB |
Output is correct |
51 |
Correct |
1817 ms |
100248 KB |
Output is correct |
52 |
Correct |
2917 ms |
100084 KB |
Output is correct |
53 |
Correct |
1839 ms |
100100 KB |
Output is correct |
54 |
Correct |
1776 ms |
100368 KB |
Output is correct |
55 |
Correct |
1761 ms |
100348 KB |
Output is correct |
56 |
Correct |
526 ms |
37756 KB |
Output is correct |
57 |
Correct |
624 ms |
37812 KB |
Output is correct |
58 |
Correct |
666 ms |
38360 KB |
Output is correct |
59 |
Correct |
1798 ms |
92300 KB |
Output is correct |
60 |
Correct |
2951 ms |
92416 KB |
Output is correct |
61 |
Correct |
1651 ms |
92508 KB |
Output is correct |
62 |
Correct |
1700 ms |
96272 KB |
Output is correct |
63 |
Correct |
3184 ms |
94860 KB |
Output is correct |
64 |
Correct |
1958 ms |
93076 KB |
Output is correct |
65 |
Correct |
1714 ms |
92492 KB |
Output is correct |
66 |
Correct |
1903 ms |
92680 KB |
Output is correct |
67 |
Correct |
1946 ms |
94660 KB |
Output is correct |
68 |
Correct |
1784 ms |
98792 KB |
Output is correct |
69 |
Correct |
3021 ms |
104064 KB |
Output is correct |