# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
986399 |
2024-05-20T12:50:03 Z |
Pyqe |
Seats (IOI18_seats) |
C++17 |
|
1617 ms |
177896 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,m,a[1000069],ya[1000069],xa[1000069],vy[4]={-1,0,1,0},vx[4]={0,1,0,-1},inf=1e9;
pair<int,int> ps[1000069];
bool alr=0;
struct segtree
{
int l,r,c;
pair<int,int> mn,lz={0,0};
segtree *p[2];
void bd(int lh,int rh)
{
l=lh;
r=rh;
if(l==r)
{
mn=ps[l];
mn.sc+=l+1;
c=1;
}
else
{
int ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
mn=min(p[0]->mn,p[1]->mn);
c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
}
}
inline void blc()
{
if(lz!=mp(0,0))
{
int ii;
for(ii=0;ii<2;ii++)
{
p[ii]->mn.fr+=lz.fr;
p[ii]->mn.sc+=lz.sc;
p[ii]->lz.fr+=lz.fr;
p[ii]->lz.sc+=lz.sc;
}
lz={0,0};
}
}
void ud(int ky,int lh,int rh,int w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
if(!ky)
{
mn.fr+=w;
lz.fr+=w;
}
else
{
mn.sc+=w;
lz.sc+=w;
}
}
else
{
int ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(ky,lh,rh,w);
}
mn=min(p[0]->mn,p[1]->mn);
c=p[0]->c*(p[0]->mn==mn)+p[1]->c*(p[1]->mn==mn);
}
}
}
sg;
void acv(int y,int x,int u)
{
int i,j,im,p=y*m+x,yy,xx,pp,mn[2]={inf,inf};
for(im=0;im<4;im++)
{
yy=y+vy[im];
xx=x+vx[im];
if(yy>=0&&xx>=0&&yy<n&&xx<m)
{
pp=yy*m+xx;
for(i=0;i<2;i++)
{
if(a[pp]<mn[i])
{
for(j=1;j>i;j--)
{
mn[j]=mn[j-1];
}
mn[i]=a[pp];
break;
}
}
}
}
if(alr)
{
sg.ud(0,mn[1],a[p]-1,u);
}
else if(mn[1]<=a[p])
{
ps[mn[1]].fr+=u;
ps[a[p]].fr-=u;
}
}
void give_initial_chart(int on,int om,vector<int> yaa,vector<int> xaa)
{
int i,j,p;
n=on;
m=om;
for(i=0;i<n*m;i++)
{
ya[i]=yaa[i];
xa[i]=xaa[i];
a[ya[i]*m+xa[i]]=i;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
p=i*m+j;
acv(i,j,1);
if(i)
{
ps[max(a[p],a[p-m])].sc--;
}
if(j)
{
ps[max(a[p],a[p-1])].sc--;
}
if(i&&j)
{
ps[max(max(a[p],a[p-1]),max(a[p-m],a[p-m-1]))].sc++;
}
}
}
for(i=1;i<n*m;i++)
{
ps[i].fr+=ps[i-1].fr;
ps[i].sc+=ps[i-1].sc;
}
sg.bd(0,n*m-1);
alr=1;
}
int swap_seats(int w,int w2)
{
int i,ii,iii,im,u,y,x,p,yy,xx,pp;
for(ii=0;ii<2;ii++)
{
y=ya[w];
x=xa[w];
p=y*m+x;
for(iii=0;iii<2;iii++)
{
u=iii*2-1;
acv(y,x,u);
for(im=0;im<4;im++)
{
yy=y+vy[im];
xx=x+vx[im];
if(yy>=0&&xx>=0&&yy<n&&xx<m)
{
pp=yy*m+xx;
acv(yy,xx,u);
sg.ud(1,max(a[p],a[pp]),n*m-1,-u);
}
yy=y+im/2;
xx=x+im%2;
if(yy>0&&xx>0&&yy<n&&xx<m)
{
pp=yy*m+xx;
sg.ud(1,max(max(a[pp],a[pp-1]),max(a[pp-m],a[pp-m-1])),n*m-1,u);
}
}
a[p]=w2;
}
swap(w,w2);
}
swap(ya[w],ya[w2]);
swap(xa[w],xa[w2]);
return sg.c;
}
Compilation message
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:170:6: warning: unused variable 'i' [-Wunused-variable]
170 | int i,ii,iii,im,u,y,x,p,yy,xx,pp;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6720 KB |
Output is correct |
2 |
Correct |
23 ms |
6748 KB |
Output is correct |
3 |
Correct |
32 ms |
6736 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6740 KB |
Output is correct |
6 |
Correct |
26 ms |
6744 KB |
Output is correct |
7 |
Correct |
29 ms |
6740 KB |
Output is correct |
8 |
Correct |
32 ms |
6748 KB |
Output is correct |
9 |
Correct |
30 ms |
6748 KB |
Output is correct |
10 |
Correct |
28 ms |
6724 KB |
Output is correct |
11 |
Correct |
27 ms |
6716 KB |
Output is correct |
12 |
Correct |
16 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6720 KB |
Output is correct |
2 |
Correct |
23 ms |
6748 KB |
Output is correct |
3 |
Correct |
32 ms |
6736 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6740 KB |
Output is correct |
6 |
Correct |
26 ms |
6744 KB |
Output is correct |
7 |
Correct |
29 ms |
6740 KB |
Output is correct |
8 |
Correct |
32 ms |
6748 KB |
Output is correct |
9 |
Correct |
30 ms |
6748 KB |
Output is correct |
10 |
Correct |
28 ms |
6724 KB |
Output is correct |
11 |
Correct |
27 ms |
6716 KB |
Output is correct |
12 |
Correct |
16 ms |
6744 KB |
Output is correct |
13 |
Correct |
64 ms |
8284 KB |
Output is correct |
14 |
Correct |
65 ms |
8292 KB |
Output is correct |
15 |
Correct |
24 ms |
8284 KB |
Output is correct |
16 |
Correct |
21 ms |
8284 KB |
Output is correct |
17 |
Correct |
47 ms |
8284 KB |
Output is correct |
18 |
Correct |
61 ms |
8124 KB |
Output is correct |
19 |
Correct |
54 ms |
8284 KB |
Output is correct |
20 |
Correct |
51 ms |
8284 KB |
Output is correct |
21 |
Correct |
25 ms |
8284 KB |
Output is correct |
22 |
Correct |
23 ms |
8380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
452 ms |
176688 KB |
Output is correct |
2 |
Correct |
369 ms |
176816 KB |
Output is correct |
3 |
Correct |
353 ms |
176820 KB |
Output is correct |
4 |
Correct |
350 ms |
176700 KB |
Output is correct |
5 |
Correct |
377 ms |
176692 KB |
Output is correct |
6 |
Correct |
370 ms |
176816 KB |
Output is correct |
7 |
Correct |
374 ms |
176784 KB |
Output is correct |
8 |
Correct |
364 ms |
176820 KB |
Output is correct |
9 |
Correct |
344 ms |
176924 KB |
Output is correct |
10 |
Correct |
367 ms |
176784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
8312 KB |
Output is correct |
2 |
Correct |
110 ms |
22780 KB |
Output is correct |
3 |
Correct |
368 ms |
176692 KB |
Output is correct |
4 |
Correct |
431 ms |
176692 KB |
Output is correct |
5 |
Correct |
285 ms |
176840 KB |
Output is correct |
6 |
Correct |
322 ms |
176756 KB |
Output is correct |
7 |
Correct |
338 ms |
176860 KB |
Output is correct |
8 |
Correct |
381 ms |
176844 KB |
Output is correct |
9 |
Correct |
374 ms |
176748 KB |
Output is correct |
10 |
Correct |
374 ms |
176704 KB |
Output is correct |
11 |
Correct |
361 ms |
176868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8228 KB |
Output is correct |
2 |
Correct |
64 ms |
8264 KB |
Output is correct |
3 |
Correct |
116 ms |
8236 KB |
Output is correct |
4 |
Correct |
161 ms |
8376 KB |
Output is correct |
5 |
Correct |
216 ms |
9756 KB |
Output is correct |
6 |
Correct |
821 ms |
177716 KB |
Output is correct |
7 |
Correct |
670 ms |
177772 KB |
Output is correct |
8 |
Correct |
630 ms |
177824 KB |
Output is correct |
9 |
Correct |
786 ms |
177572 KB |
Output is correct |
10 |
Correct |
567 ms |
177700 KB |
Output is correct |
11 |
Correct |
561 ms |
177828 KB |
Output is correct |
12 |
Correct |
530 ms |
177812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6720 KB |
Output is correct |
2 |
Correct |
23 ms |
6748 KB |
Output is correct |
3 |
Correct |
32 ms |
6736 KB |
Output is correct |
4 |
Correct |
13 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6740 KB |
Output is correct |
6 |
Correct |
26 ms |
6744 KB |
Output is correct |
7 |
Correct |
29 ms |
6740 KB |
Output is correct |
8 |
Correct |
32 ms |
6748 KB |
Output is correct |
9 |
Correct |
30 ms |
6748 KB |
Output is correct |
10 |
Correct |
28 ms |
6724 KB |
Output is correct |
11 |
Correct |
27 ms |
6716 KB |
Output is correct |
12 |
Correct |
16 ms |
6744 KB |
Output is correct |
13 |
Correct |
64 ms |
8284 KB |
Output is correct |
14 |
Correct |
65 ms |
8292 KB |
Output is correct |
15 |
Correct |
24 ms |
8284 KB |
Output is correct |
16 |
Correct |
21 ms |
8284 KB |
Output is correct |
17 |
Correct |
47 ms |
8284 KB |
Output is correct |
18 |
Correct |
61 ms |
8124 KB |
Output is correct |
19 |
Correct |
54 ms |
8284 KB |
Output is correct |
20 |
Correct |
51 ms |
8284 KB |
Output is correct |
21 |
Correct |
25 ms |
8284 KB |
Output is correct |
22 |
Correct |
23 ms |
8380 KB |
Output is correct |
23 |
Correct |
452 ms |
176688 KB |
Output is correct |
24 |
Correct |
369 ms |
176816 KB |
Output is correct |
25 |
Correct |
353 ms |
176820 KB |
Output is correct |
26 |
Correct |
350 ms |
176700 KB |
Output is correct |
27 |
Correct |
377 ms |
176692 KB |
Output is correct |
28 |
Correct |
370 ms |
176816 KB |
Output is correct |
29 |
Correct |
374 ms |
176784 KB |
Output is correct |
30 |
Correct |
364 ms |
176820 KB |
Output is correct |
31 |
Correct |
344 ms |
176924 KB |
Output is correct |
32 |
Correct |
367 ms |
176784 KB |
Output is correct |
33 |
Correct |
69 ms |
8312 KB |
Output is correct |
34 |
Correct |
110 ms |
22780 KB |
Output is correct |
35 |
Correct |
368 ms |
176692 KB |
Output is correct |
36 |
Correct |
431 ms |
176692 KB |
Output is correct |
37 |
Correct |
285 ms |
176840 KB |
Output is correct |
38 |
Correct |
322 ms |
176756 KB |
Output is correct |
39 |
Correct |
338 ms |
176860 KB |
Output is correct |
40 |
Correct |
381 ms |
176844 KB |
Output is correct |
41 |
Correct |
374 ms |
176748 KB |
Output is correct |
42 |
Correct |
374 ms |
176704 KB |
Output is correct |
43 |
Correct |
361 ms |
176868 KB |
Output is correct |
44 |
Correct |
35 ms |
8228 KB |
Output is correct |
45 |
Correct |
64 ms |
8264 KB |
Output is correct |
46 |
Correct |
116 ms |
8236 KB |
Output is correct |
47 |
Correct |
161 ms |
8376 KB |
Output is correct |
48 |
Correct |
216 ms |
9756 KB |
Output is correct |
49 |
Correct |
821 ms |
177716 KB |
Output is correct |
50 |
Correct |
670 ms |
177772 KB |
Output is correct |
51 |
Correct |
630 ms |
177824 KB |
Output is correct |
52 |
Correct |
786 ms |
177572 KB |
Output is correct |
53 |
Correct |
567 ms |
177700 KB |
Output is correct |
54 |
Correct |
561 ms |
177828 KB |
Output is correct |
55 |
Correct |
530 ms |
177812 KB |
Output is correct |
56 |
Correct |
130 ms |
8276 KB |
Output is correct |
57 |
Correct |
302 ms |
8144 KB |
Output is correct |
58 |
Correct |
581 ms |
9756 KB |
Output is correct |
59 |
Correct |
1417 ms |
177720 KB |
Output is correct |
60 |
Correct |
1617 ms |
177744 KB |
Output is correct |
61 |
Correct |
1105 ms |
177856 KB |
Output is correct |
62 |
Correct |
845 ms |
177860 KB |
Output is correct |
63 |
Correct |
1456 ms |
177860 KB |
Output is correct |
64 |
Correct |
1362 ms |
177896 KB |
Output is correct |
65 |
Correct |
1197 ms |
177804 KB |
Output is correct |
66 |
Correct |
1402 ms |
177880 KB |
Output is correct |
67 |
Correct |
1279 ms |
177848 KB |
Output is correct |
68 |
Correct |
927 ms |
177864 KB |
Output is correct |
69 |
Correct |
1236 ms |
177808 KB |
Output is correct |