#include<bits/stdc++.h>
#include "seats.h"
#define ll long long
using namespace std;
int lazy[1<<21],b[1000005],h,w;
vector<int>r,c;
vector<vector<int>>auxi;
array<int,2>aint[1<<21];
void comb(int nod)
{
aint[nod]={min(aint[nod*2][0],aint[nod*2+1][0])};
aint[nod][1]=0;
if (aint[nod*2][0]>aint[nod][0])
aint[nod][1]+=0;
else
aint[nod][1]+=aint[nod*2][1];
if (aint[nod*2+1][0]>aint[nod][0])
aint[nod][1]+=0;
else
aint[nod][1]+=aint[nod*2+1][1];
}
void build(int nod=1,int st=0,int dr=h*w-1)
{
if (st==dr){
aint[nod]={b[st],1};
return ;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
comb(nod);
}
void add(int nod,int x)
{
aint[nod][0]+=x;
lazy[nod]+=x;
}
void update(int st,int dr,int val,int nod=1,int l=0,int r=h*w-1)
{
if (aint[1][1]==0){
b[st]+=val;
b[dr+1]-=val;
return ;
}
if (st<=l && r<=dr){
add(nod,val);
return ;
}
int mij=(l+r)/2;
add(2*nod,lazy[nod]);
add(2*nod+1,lazy[nod]);
lazy[nod]=0;
if (st<=mij)
update(st,dr,val,2*nod,l,mij);
if (mij+1<=dr)
update(st,dr,val,2*nod+1,mij+1,r);
comb(nod);
}
void swa(int x,int y,int z)
{
vector<int>v;
int i,j;
for(i=!x-1;i<(x<h);i++)
for(j=!y-1;j<(y<w);j++)
v.push_back(auxi[x+i][y+j]);
sort(v.begin(),v.end());
update(v[0],(v.size()>1?v[1]:h*w)-1,z);
if (v.size()>2)
update(v[2],v[3]-1,z);
}
void give_initial_chart(int h2,int w2,vector<int>r2,vector<int>c2)
{
h=h2;
w=w2;
r=r2;
c=c2;
auxi=vector<vector<int>>(h,vector<int>(w));
int i,j;
for(i=0;i<h*w;i++)
auxi[r[i]][c[i]]=i;
for(i=0;i<=h;i++)
for(j=0;j<=w;j++)
swa(i,j,1);
for(i=0;i<h*w;i++)
b[i+1]+=b[i];
build();
}
int swap_seats(int x,int y)
{
int i,j,k;
vector<array<int,2>>v;
for(int i:{x,y})
for(int j:{0,1})
for(int k:{0,1})
v.push_back({r[i]+j,c[i]+k});
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(auto it:v)
swa(it[0],it[1],-1);
swap(auxi[r[x]][c[x]],auxi[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
for(auto it:v)
swa(it[0],it[1],1);
return aint[1][1];
}
Compilation message
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:90:9: warning: unused variable 'i' [-Wunused-variable]
90 | int i,j,k;
| ^
seats.cpp:90:11: warning: unused variable 'j' [-Wunused-variable]
90 | int i,j,k;
| ^
seats.cpp:90:13: warning: unused variable 'k' [-Wunused-variable]
90 | int i,j,k;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
492 KB |
Output is correct |
2 |
Correct |
28 ms |
492 KB |
Output is correct |
3 |
Correct |
41 ms |
492 KB |
Output is correct |
4 |
Correct |
25 ms |
492 KB |
Output is correct |
5 |
Correct |
22 ms |
492 KB |
Output is correct |
6 |
Correct |
37 ms |
492 KB |
Output is correct |
7 |
Correct |
38 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
35 ms |
492 KB |
Output is correct |
10 |
Correct |
40 ms |
492 KB |
Output is correct |
11 |
Correct |
35 ms |
492 KB |
Output is correct |
12 |
Correct |
24 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
492 KB |
Output is correct |
2 |
Correct |
28 ms |
492 KB |
Output is correct |
3 |
Correct |
41 ms |
492 KB |
Output is correct |
4 |
Correct |
25 ms |
492 KB |
Output is correct |
5 |
Correct |
22 ms |
492 KB |
Output is correct |
6 |
Correct |
37 ms |
492 KB |
Output is correct |
7 |
Correct |
38 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
35 ms |
492 KB |
Output is correct |
10 |
Correct |
40 ms |
492 KB |
Output is correct |
11 |
Correct |
35 ms |
492 KB |
Output is correct |
12 |
Correct |
24 ms |
620 KB |
Output is correct |
13 |
Correct |
82 ms |
1260 KB |
Output is correct |
14 |
Correct |
106 ms |
1260 KB |
Output is correct |
15 |
Correct |
54 ms |
1408 KB |
Output is correct |
16 |
Correct |
41 ms |
1772 KB |
Output is correct |
17 |
Correct |
65 ms |
1260 KB |
Output is correct |
18 |
Correct |
69 ms |
1280 KB |
Output is correct |
19 |
Correct |
65 ms |
1388 KB |
Output is correct |
20 |
Correct |
56 ms |
1644 KB |
Output is correct |
21 |
Correct |
41 ms |
1388 KB |
Output is correct |
22 |
Correct |
44 ms |
1772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
726 ms |
64748 KB |
Output is correct |
2 |
Correct |
598 ms |
64732 KB |
Output is correct |
3 |
Correct |
594 ms |
64588 KB |
Output is correct |
4 |
Correct |
579 ms |
64664 KB |
Output is correct |
5 |
Correct |
581 ms |
64860 KB |
Output is correct |
6 |
Correct |
571 ms |
64988 KB |
Output is correct |
7 |
Correct |
588 ms |
64664 KB |
Output is correct |
8 |
Correct |
599 ms |
64604 KB |
Output is correct |
9 |
Correct |
576 ms |
64776 KB |
Output is correct |
10 |
Correct |
566 ms |
64604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
1260 KB |
Output is correct |
2 |
Correct |
137 ms |
6956 KB |
Output is correct |
3 |
Correct |
572 ms |
64804 KB |
Output is correct |
4 |
Correct |
777 ms |
64808 KB |
Output is correct |
5 |
Correct |
548 ms |
64592 KB |
Output is correct |
6 |
Correct |
828 ms |
115548 KB |
Output is correct |
7 |
Correct |
571 ms |
64708 KB |
Output is correct |
8 |
Correct |
596 ms |
64604 KB |
Output is correct |
9 |
Correct |
590 ms |
65176 KB |
Output is correct |
10 |
Correct |
587 ms |
67804 KB |
Output is correct |
11 |
Correct |
622 ms |
88156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
2172 KB |
Output is correct |
2 |
Correct |
152 ms |
2024 KB |
Output is correct |
3 |
Correct |
221 ms |
2024 KB |
Output is correct |
4 |
Correct |
300 ms |
2184 KB |
Output is correct |
5 |
Correct |
455 ms |
3136 KB |
Output is correct |
6 |
Correct |
1162 ms |
66420 KB |
Output is correct |
7 |
Correct |
1166 ms |
66300 KB |
Output is correct |
8 |
Correct |
1204 ms |
66492 KB |
Output is correct |
9 |
Correct |
1446 ms |
66332 KB |
Output is correct |
10 |
Correct |
1088 ms |
66568 KB |
Output is correct |
11 |
Correct |
1073 ms |
66616 KB |
Output is correct |
12 |
Correct |
1042 ms |
66320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
492 KB |
Output is correct |
2 |
Correct |
28 ms |
492 KB |
Output is correct |
3 |
Correct |
41 ms |
492 KB |
Output is correct |
4 |
Correct |
25 ms |
492 KB |
Output is correct |
5 |
Correct |
22 ms |
492 KB |
Output is correct |
6 |
Correct |
37 ms |
492 KB |
Output is correct |
7 |
Correct |
38 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
35 ms |
492 KB |
Output is correct |
10 |
Correct |
40 ms |
492 KB |
Output is correct |
11 |
Correct |
35 ms |
492 KB |
Output is correct |
12 |
Correct |
24 ms |
620 KB |
Output is correct |
13 |
Correct |
82 ms |
1260 KB |
Output is correct |
14 |
Correct |
106 ms |
1260 KB |
Output is correct |
15 |
Correct |
54 ms |
1408 KB |
Output is correct |
16 |
Correct |
41 ms |
1772 KB |
Output is correct |
17 |
Correct |
65 ms |
1260 KB |
Output is correct |
18 |
Correct |
69 ms |
1280 KB |
Output is correct |
19 |
Correct |
65 ms |
1388 KB |
Output is correct |
20 |
Correct |
56 ms |
1644 KB |
Output is correct |
21 |
Correct |
41 ms |
1388 KB |
Output is correct |
22 |
Correct |
44 ms |
1772 KB |
Output is correct |
23 |
Correct |
726 ms |
64748 KB |
Output is correct |
24 |
Correct |
598 ms |
64732 KB |
Output is correct |
25 |
Correct |
594 ms |
64588 KB |
Output is correct |
26 |
Correct |
579 ms |
64664 KB |
Output is correct |
27 |
Correct |
581 ms |
64860 KB |
Output is correct |
28 |
Correct |
571 ms |
64988 KB |
Output is correct |
29 |
Correct |
588 ms |
64664 KB |
Output is correct |
30 |
Correct |
599 ms |
64604 KB |
Output is correct |
31 |
Correct |
576 ms |
64776 KB |
Output is correct |
32 |
Correct |
566 ms |
64604 KB |
Output is correct |
33 |
Correct |
89 ms |
1260 KB |
Output is correct |
34 |
Correct |
137 ms |
6956 KB |
Output is correct |
35 |
Correct |
572 ms |
64804 KB |
Output is correct |
36 |
Correct |
777 ms |
64808 KB |
Output is correct |
37 |
Correct |
548 ms |
64592 KB |
Output is correct |
38 |
Correct |
828 ms |
115548 KB |
Output is correct |
39 |
Correct |
571 ms |
64708 KB |
Output is correct |
40 |
Correct |
596 ms |
64604 KB |
Output is correct |
41 |
Correct |
590 ms |
65176 KB |
Output is correct |
42 |
Correct |
587 ms |
67804 KB |
Output is correct |
43 |
Correct |
622 ms |
88156 KB |
Output is correct |
44 |
Correct |
103 ms |
2172 KB |
Output is correct |
45 |
Correct |
152 ms |
2024 KB |
Output is correct |
46 |
Correct |
221 ms |
2024 KB |
Output is correct |
47 |
Correct |
300 ms |
2184 KB |
Output is correct |
48 |
Correct |
455 ms |
3136 KB |
Output is correct |
49 |
Correct |
1162 ms |
66420 KB |
Output is correct |
50 |
Correct |
1166 ms |
66300 KB |
Output is correct |
51 |
Correct |
1204 ms |
66492 KB |
Output is correct |
52 |
Correct |
1446 ms |
66332 KB |
Output is correct |
53 |
Correct |
1088 ms |
66568 KB |
Output is correct |
54 |
Correct |
1073 ms |
66616 KB |
Output is correct |
55 |
Correct |
1042 ms |
66320 KB |
Output is correct |
56 |
Correct |
197 ms |
2096 KB |
Output is correct |
57 |
Correct |
410 ms |
2248 KB |
Output is correct |
58 |
Correct |
663 ms |
2792 KB |
Output is correct |
59 |
Correct |
1645 ms |
66384 KB |
Output is correct |
60 |
Correct |
2264 ms |
66360 KB |
Output is correct |
61 |
Correct |
1488 ms |
66284 KB |
Output is correct |
62 |
Correct |
1245 ms |
66312 KB |
Output is correct |
63 |
Correct |
1926 ms |
66272 KB |
Output is correct |
64 |
Correct |
1587 ms |
66500 KB |
Output is correct |
65 |
Correct |
1429 ms |
66196 KB |
Output is correct |
66 |
Correct |
1779 ms |
66820 KB |
Output is correct |
67 |
Correct |
1579 ms |
69460 KB |
Output is correct |
68 |
Correct |
1365 ms |
80624 KB |
Output is correct |
69 |
Correct |
1949 ms |
89824 KB |
Output is correct |