# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
296979 |
2020-09-11T06:22:37 Z |
daniel920712 |
Seats (IOI18_seats) |
C++14 |
|
3093 ms |
169072 KB |
#include "seats.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
int N,H,W;
pair < int , int > all[1000005];
vector < vector < int > > what;
vector < int > tt;
int how1[1000005]={0};
int how2[1000005]={0};
int xx[5];
struct A
{
int l,r;
int nxl,nxr;
int small1,small2,con;
int add1,add2;
}Node[4000005];
int now=1;
void UPD(int here)
{
Node[Node[here].nxl].add1+=Node[here].add1;
Node[Node[here].nxl].small1+=Node[here].add1;
Node[Node[here].nxr].add1+=Node[here].add1;
Node[Node[here].nxr].small1+=Node[here].add1;
Node[here].add1=0;
Node[Node[here].nxl].add2+=Node[here].add2;
Node[Node[here].nxl].small2+=Node[here].add2;
Node[Node[here].nxr].add2+=Node[here].add2;
Node[Node[here].nxr].small2+=Node[here].add2;
Node[here].add2=0;
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].small1=0;
Node[here].small2=0;
Node[here].add1=0;
Node[here].add2=0;
if(l==r)
{
Node[here].small1=how1[l];
Node[here].small2=how2[l];
Node[here].con=1;
return;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].con=0;
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxl].con;
if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxr].con;
//printf()
}
void cha(int l,int r,int x,int con,int here)
{
if(l>r) return;
if(l==Node[here].l&&r==Node[here].r)
{
if(x==0)
{
Node[here].add1+=con;
Node[here].small1+=con;
}
else
{
Node[here].add2+=con;
Node[here].small2+=con;
}
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,x,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,x,con,Node[here].nxr);
else
{
cha(l,(Node[here].l+Node[here].r)/2,x,con,Node[here].nxl);
cha((Node[here].l+Node[here].r)/2+1,r,x,con,Node[here].nxr);
}
Node[here].con=0;
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxl].con;
if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==Node[here].small2) Node[here].con+=Node[Node[here].nxr].con;
}
void F(int x,int y,int t)
{
int xx[5]={what[x][y],what[x+1][y],what[x][y+1],what[x+1][y+1]};
sort(xx,xx+4);
if(t==-2)
{
if(xx[1]>xx[0])
{
how1[xx[0]]++;
how1[xx[1]]--;
}
if(xx[3]>xx[2])
{
how2[xx[2]]++;
how2[xx[3]]--;
}
return ;
}
cha(xx[0],xx[1]-1,0,t,0);
cha(xx[2],xx[3]-1,1,t,0);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
int i,j;
N=H*W;
::H=H;
::W=W;
for(j=0;j<=W+1;j++) tt.push_back(N);
for(i=0;i<=H+1;i++) what.push_back(tt);
for(i=0;i<N;i++)
{
R[i]++;
C[i]++;
all[i]=make_pair(R[i],C[i]);
what[R[i]][C[i]]=i;
}
for(i=0;i<=H;i++) for(j=0;j<=W;j++) F(i,j,-2);
for(i=1;i<N;i++) how1[i]+=how1[i-1];
for(i=1;i<N;i++) how2[i]+=how2[i-1];
build(0,N-1,0);
}
int swap_seats(int a, int b)
{
int x1,y1,x2,y2,ans=0;
x1=all[a].first;
y1=all[a].second;
x2=all[b].first;
y2=all[b].second;
F(x1-1,y1-1,-1);
F(x1-1,y1,-1);
F(x1,y1-1,-1);
F(x1,y1,-1);
F(x2-1,y2-1,-1);
F(x2-1,y2,-1);
F(x2,y2-1,-1);
F(x2,y2,-1);
swap(all[a],all[b]);
swap(what[x1][y1],what[x2][y2]);
F(x1-1,y1-1,1);
F(x1-1,y1,1);
F(x1,y1-1,1);
F(x1,y1,1);
F(x2-1,y2-1,1);
F(x2-1,y2,1);
F(x2,y2-1,1);
F(x2,y2,1);
return Node[0].con;
}
Compilation message
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:138:21: warning: unused variable 'ans' [-Wunused-variable]
138 | int x1,y1,x2,y2,ans=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
640 KB |
Output is correct |
2 |
Correct |
32 ms |
504 KB |
Output is correct |
3 |
Correct |
56 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
5 |
Correct |
26 ms |
504 KB |
Output is correct |
6 |
Correct |
45 ms |
504 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
636 KB |
Output is correct |
9 |
Correct |
46 ms |
504 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
44 ms |
512 KB |
Output is correct |
12 |
Correct |
29 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
640 KB |
Output is correct |
2 |
Correct |
32 ms |
504 KB |
Output is correct |
3 |
Correct |
56 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
5 |
Correct |
26 ms |
504 KB |
Output is correct |
6 |
Correct |
45 ms |
504 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
636 KB |
Output is correct |
9 |
Correct |
46 ms |
504 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
44 ms |
512 KB |
Output is correct |
12 |
Correct |
29 ms |
512 KB |
Output is correct |
13 |
Correct |
127 ms |
1536 KB |
Output is correct |
14 |
Correct |
138 ms |
1528 KB |
Output is correct |
15 |
Correct |
69 ms |
1536 KB |
Output is correct |
16 |
Correct |
56 ms |
1980 KB |
Output is correct |
17 |
Correct |
94 ms |
1536 KB |
Output is correct |
18 |
Correct |
96 ms |
1536 KB |
Output is correct |
19 |
Correct |
90 ms |
1528 KB |
Output is correct |
20 |
Correct |
75 ms |
1792 KB |
Output is correct |
21 |
Correct |
55 ms |
1536 KB |
Output is correct |
22 |
Correct |
57 ms |
2100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
817 ms |
106232 KB |
Output is correct |
2 |
Correct |
661 ms |
118008 KB |
Output is correct |
3 |
Correct |
646 ms |
118136 KB |
Output is correct |
4 |
Correct |
618 ms |
118008 KB |
Output is correct |
5 |
Correct |
618 ms |
118008 KB |
Output is correct |
6 |
Correct |
615 ms |
117880 KB |
Output is correct |
7 |
Correct |
627 ms |
117880 KB |
Output is correct |
8 |
Correct |
629 ms |
118008 KB |
Output is correct |
9 |
Correct |
624 ms |
117880 KB |
Output is correct |
10 |
Correct |
614 ms |
118264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
1528 KB |
Output is correct |
2 |
Correct |
178 ms |
9976 KB |
Output is correct |
3 |
Correct |
601 ms |
106104 KB |
Output is correct |
4 |
Correct |
833 ms |
106108 KB |
Output is correct |
5 |
Correct |
573 ms |
129888 KB |
Output is correct |
6 |
Correct |
983 ms |
169072 KB |
Output is correct |
7 |
Correct |
595 ms |
122728 KB |
Output is correct |
8 |
Correct |
640 ms |
118648 KB |
Output is correct |
9 |
Correct |
682 ms |
118832 KB |
Output is correct |
10 |
Correct |
623 ms |
123044 KB |
Output is correct |
11 |
Correct |
611 ms |
141836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
1908 KB |
Output is correct |
2 |
Correct |
142 ms |
1780 KB |
Output is correct |
3 |
Correct |
250 ms |
1948 KB |
Output is correct |
4 |
Correct |
373 ms |
2036 KB |
Output is correct |
5 |
Correct |
649 ms |
2980 KB |
Output is correct |
6 |
Correct |
1368 ms |
119136 KB |
Output is correct |
7 |
Correct |
1425 ms |
118880 KB |
Output is correct |
8 |
Correct |
1373 ms |
119008 KB |
Output is correct |
9 |
Correct |
1761 ms |
119136 KB |
Output is correct |
10 |
Correct |
1299 ms |
126688 KB |
Output is correct |
11 |
Correct |
1293 ms |
130272 KB |
Output is correct |
12 |
Correct |
1286 ms |
130272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
640 KB |
Output is correct |
2 |
Correct |
32 ms |
504 KB |
Output is correct |
3 |
Correct |
56 ms |
504 KB |
Output is correct |
4 |
Correct |
30 ms |
504 KB |
Output is correct |
5 |
Correct |
26 ms |
504 KB |
Output is correct |
6 |
Correct |
45 ms |
504 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
636 KB |
Output is correct |
9 |
Correct |
46 ms |
504 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
44 ms |
512 KB |
Output is correct |
12 |
Correct |
29 ms |
512 KB |
Output is correct |
13 |
Correct |
127 ms |
1536 KB |
Output is correct |
14 |
Correct |
138 ms |
1528 KB |
Output is correct |
15 |
Correct |
69 ms |
1536 KB |
Output is correct |
16 |
Correct |
56 ms |
1980 KB |
Output is correct |
17 |
Correct |
94 ms |
1536 KB |
Output is correct |
18 |
Correct |
96 ms |
1536 KB |
Output is correct |
19 |
Correct |
90 ms |
1528 KB |
Output is correct |
20 |
Correct |
75 ms |
1792 KB |
Output is correct |
21 |
Correct |
55 ms |
1536 KB |
Output is correct |
22 |
Correct |
57 ms |
2100 KB |
Output is correct |
23 |
Correct |
817 ms |
106232 KB |
Output is correct |
24 |
Correct |
661 ms |
118008 KB |
Output is correct |
25 |
Correct |
646 ms |
118136 KB |
Output is correct |
26 |
Correct |
618 ms |
118008 KB |
Output is correct |
27 |
Correct |
618 ms |
118008 KB |
Output is correct |
28 |
Correct |
615 ms |
117880 KB |
Output is correct |
29 |
Correct |
627 ms |
117880 KB |
Output is correct |
30 |
Correct |
629 ms |
118008 KB |
Output is correct |
31 |
Correct |
624 ms |
117880 KB |
Output is correct |
32 |
Correct |
614 ms |
118264 KB |
Output is correct |
33 |
Correct |
130 ms |
1528 KB |
Output is correct |
34 |
Correct |
178 ms |
9976 KB |
Output is correct |
35 |
Correct |
601 ms |
106104 KB |
Output is correct |
36 |
Correct |
833 ms |
106108 KB |
Output is correct |
37 |
Correct |
573 ms |
129888 KB |
Output is correct |
38 |
Correct |
983 ms |
169072 KB |
Output is correct |
39 |
Correct |
595 ms |
122728 KB |
Output is correct |
40 |
Correct |
640 ms |
118648 KB |
Output is correct |
41 |
Correct |
682 ms |
118832 KB |
Output is correct |
42 |
Correct |
623 ms |
123044 KB |
Output is correct |
43 |
Correct |
611 ms |
141836 KB |
Output is correct |
44 |
Correct |
81 ms |
1908 KB |
Output is correct |
45 |
Correct |
142 ms |
1780 KB |
Output is correct |
46 |
Correct |
250 ms |
1948 KB |
Output is correct |
47 |
Correct |
373 ms |
2036 KB |
Output is correct |
48 |
Correct |
649 ms |
2980 KB |
Output is correct |
49 |
Correct |
1368 ms |
119136 KB |
Output is correct |
50 |
Correct |
1425 ms |
118880 KB |
Output is correct |
51 |
Correct |
1373 ms |
119008 KB |
Output is correct |
52 |
Correct |
1761 ms |
119136 KB |
Output is correct |
53 |
Correct |
1299 ms |
126688 KB |
Output is correct |
54 |
Correct |
1293 ms |
130272 KB |
Output is correct |
55 |
Correct |
1286 ms |
130272 KB |
Output is correct |
56 |
Correct |
193 ms |
2096 KB |
Output is correct |
57 |
Correct |
520 ms |
2100 KB |
Output is correct |
58 |
Correct |
961 ms |
3652 KB |
Output is correct |
59 |
Correct |
2187 ms |
115056 KB |
Output is correct |
60 |
Correct |
3093 ms |
114936 KB |
Output is correct |
61 |
Correct |
1889 ms |
114808 KB |
Output is correct |
62 |
Correct |
1612 ms |
120936 KB |
Output is correct |
63 |
Correct |
2651 ms |
119048 KB |
Output is correct |
64 |
Correct |
2058 ms |
115696 KB |
Output is correct |
65 |
Correct |
1870 ms |
114936 KB |
Output is correct |
66 |
Correct |
2270 ms |
115380 KB |
Output is correct |
67 |
Correct |
2037 ms |
119592 KB |
Output is correct |
68 |
Correct |
1673 ms |
129420 KB |
Output is correct |
69 |
Correct |
2743 ms |
138596 KB |
Output is correct |