# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
624691 |
2022-08-08T15:40:58 Z |
moonrabbit2 |
Seats (IOI18_seats) |
C++17 |
|
1452 ms |
109504 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
const int N=1e6+5;
int h,w,r[N],c[N],D[N];
vector<vector<int>> a;
int S[2*N];
pii pos[N],T[2*N];
pii mrg(pii A,pii B,int d){
A.fi+=d; B.fi+=d;
if(A.fi<B.fi) return A;
if(A.fi>B.fi) return B;
return pii(A.fi,A.se+B.se);
}
void init(int nd,int l,int r){
S[nd]=0;
if(l==r){
T[nd]=pii(D[l],1);
return;
}
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
init(ln,l,m); init(rn,m+1,r);
T[nd]=mrg(T[ln],T[rn],0);
}
void add(int nd,int l,int r,int s,int e,int v){
if(r<s||e<l) return;
if(s<=l&&r<=e){
S[nd]+=v;
T[nd].fi+=v;
return;
}
int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
add(ln,l,m,s,e,v); add(rn,m+1,r,s,e,v);
T[nd]=mrg(T[ln],T[rn],S[nd]);
}
// (r, c) 오른쪽 아래의 꼭짓점.
void Do(int r,int c,int v=0){
// a[r][c] a[r][c+1]
// a[r+1][c] a[r+1][c+1]
vector<int> X;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) X.emplace_back(a[r+i][c+j]);
sort(X.begin(),X.end());
if(X[0]<h*w+1){
if(v) add(1,1,h*w,X[0],X[1]-1,v);
else{
D[X[0]]++;
D[X[1]]--;
}
}
if(X[2]<h*w+1){
if(v) add(1,1,h*w,X[2],X[3]-1,v);
else{
D[X[2]]++;
D[X[3]]--;
}
}
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
h=H;
w=W;
a.resize(h+2);
for(int i=0;i<=h+1;i++) a[i].resize(w+2);
for(int i=0;i<=h+1;i++) for(int j=0;j<=w+1;j++) a[i][j]=h*w+1;
for(int i=0;i<h*w;i++){
a[R[i]+1][C[i]+1]=i+1;
r[i+1]=R[i]+1;
c[i+1]=C[i]+1;
}
for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) Do(i,j);
for(int i=1;i<=h*w;i++) D[i]+=D[i-1];
init(1,1,h*w);
}
int swap_seats(int x,int y){
x++; y++;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,-1);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,-1);
swap(a[r[x]][c[x]],a[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,1);
for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,1);
return T[1].se;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
468 KB |
Output is correct |
2 |
Correct |
22 ms |
416 KB |
Output is correct |
3 |
Correct |
32 ms |
476 KB |
Output is correct |
4 |
Correct |
21 ms |
472 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
28 ms |
468 KB |
Output is correct |
7 |
Correct |
30 ms |
468 KB |
Output is correct |
8 |
Correct |
32 ms |
456 KB |
Output is correct |
9 |
Correct |
32 ms |
460 KB |
Output is correct |
10 |
Correct |
29 ms |
468 KB |
Output is correct |
11 |
Correct |
27 ms |
472 KB |
Output is correct |
12 |
Correct |
19 ms |
480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
468 KB |
Output is correct |
2 |
Correct |
22 ms |
416 KB |
Output is correct |
3 |
Correct |
32 ms |
476 KB |
Output is correct |
4 |
Correct |
21 ms |
472 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
28 ms |
468 KB |
Output is correct |
7 |
Correct |
30 ms |
468 KB |
Output is correct |
8 |
Correct |
32 ms |
456 KB |
Output is correct |
9 |
Correct |
32 ms |
460 KB |
Output is correct |
10 |
Correct |
29 ms |
468 KB |
Output is correct |
11 |
Correct |
27 ms |
472 KB |
Output is correct |
12 |
Correct |
19 ms |
480 KB |
Output is correct |
13 |
Correct |
58 ms |
1100 KB |
Output is correct |
14 |
Correct |
66 ms |
1108 KB |
Output is correct |
15 |
Correct |
42 ms |
1172 KB |
Output is correct |
16 |
Correct |
32 ms |
1620 KB |
Output is correct |
17 |
Correct |
46 ms |
1140 KB |
Output is correct |
18 |
Correct |
47 ms |
1100 KB |
Output is correct |
19 |
Correct |
46 ms |
1132 KB |
Output is correct |
20 |
Correct |
40 ms |
1356 KB |
Output is correct |
21 |
Correct |
31 ms |
1196 KB |
Output is correct |
22 |
Correct |
33 ms |
1624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
474 ms |
58788 KB |
Output is correct |
2 |
Correct |
399 ms |
58740 KB |
Output is correct |
3 |
Correct |
399 ms |
58920 KB |
Output is correct |
4 |
Correct |
397 ms |
58780 KB |
Output is correct |
5 |
Correct |
401 ms |
58676 KB |
Output is correct |
6 |
Correct |
416 ms |
58612 KB |
Output is correct |
7 |
Correct |
410 ms |
58696 KB |
Output is correct |
8 |
Correct |
406 ms |
58716 KB |
Output is correct |
9 |
Correct |
455 ms |
58736 KB |
Output is correct |
10 |
Correct |
384 ms |
58572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
1116 KB |
Output is correct |
2 |
Correct |
89 ms |
6632 KB |
Output is correct |
3 |
Correct |
396 ms |
58696 KB |
Output is correct |
4 |
Correct |
501 ms |
58680 KB |
Output is correct |
5 |
Correct |
474 ms |
66492 KB |
Output is correct |
6 |
Correct |
686 ms |
109504 KB |
Output is correct |
7 |
Correct |
430 ms |
61176 KB |
Output is correct |
8 |
Correct |
443 ms |
58784 KB |
Output is correct |
9 |
Correct |
424 ms |
58920 KB |
Output is correct |
10 |
Correct |
464 ms |
63536 KB |
Output is correct |
11 |
Correct |
471 ms |
82100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
1992 KB |
Output is correct |
2 |
Correct |
142 ms |
2116 KB |
Output is correct |
3 |
Correct |
188 ms |
1960 KB |
Output is correct |
4 |
Correct |
231 ms |
2124 KB |
Output is correct |
5 |
Correct |
323 ms |
2792 KB |
Output is correct |
6 |
Correct |
873 ms |
66756 KB |
Output is correct |
7 |
Correct |
867 ms |
66868 KB |
Output is correct |
8 |
Correct |
870 ms |
66636 KB |
Output is correct |
9 |
Correct |
1040 ms |
66716 KB |
Output is correct |
10 |
Correct |
791 ms |
66808 KB |
Output is correct |
11 |
Correct |
805 ms |
66764 KB |
Output is correct |
12 |
Correct |
801 ms |
66780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
468 KB |
Output is correct |
2 |
Correct |
22 ms |
416 KB |
Output is correct |
3 |
Correct |
32 ms |
476 KB |
Output is correct |
4 |
Correct |
21 ms |
472 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
28 ms |
468 KB |
Output is correct |
7 |
Correct |
30 ms |
468 KB |
Output is correct |
8 |
Correct |
32 ms |
456 KB |
Output is correct |
9 |
Correct |
32 ms |
460 KB |
Output is correct |
10 |
Correct |
29 ms |
468 KB |
Output is correct |
11 |
Correct |
27 ms |
472 KB |
Output is correct |
12 |
Correct |
19 ms |
480 KB |
Output is correct |
13 |
Correct |
58 ms |
1100 KB |
Output is correct |
14 |
Correct |
66 ms |
1108 KB |
Output is correct |
15 |
Correct |
42 ms |
1172 KB |
Output is correct |
16 |
Correct |
32 ms |
1620 KB |
Output is correct |
17 |
Correct |
46 ms |
1140 KB |
Output is correct |
18 |
Correct |
47 ms |
1100 KB |
Output is correct |
19 |
Correct |
46 ms |
1132 KB |
Output is correct |
20 |
Correct |
40 ms |
1356 KB |
Output is correct |
21 |
Correct |
31 ms |
1196 KB |
Output is correct |
22 |
Correct |
33 ms |
1624 KB |
Output is correct |
23 |
Correct |
474 ms |
58788 KB |
Output is correct |
24 |
Correct |
399 ms |
58740 KB |
Output is correct |
25 |
Correct |
399 ms |
58920 KB |
Output is correct |
26 |
Correct |
397 ms |
58780 KB |
Output is correct |
27 |
Correct |
401 ms |
58676 KB |
Output is correct |
28 |
Correct |
416 ms |
58612 KB |
Output is correct |
29 |
Correct |
410 ms |
58696 KB |
Output is correct |
30 |
Correct |
406 ms |
58716 KB |
Output is correct |
31 |
Correct |
455 ms |
58736 KB |
Output is correct |
32 |
Correct |
384 ms |
58572 KB |
Output is correct |
33 |
Correct |
58 ms |
1116 KB |
Output is correct |
34 |
Correct |
89 ms |
6632 KB |
Output is correct |
35 |
Correct |
396 ms |
58696 KB |
Output is correct |
36 |
Correct |
501 ms |
58680 KB |
Output is correct |
37 |
Correct |
474 ms |
66492 KB |
Output is correct |
38 |
Correct |
686 ms |
109504 KB |
Output is correct |
39 |
Correct |
430 ms |
61176 KB |
Output is correct |
40 |
Correct |
443 ms |
58784 KB |
Output is correct |
41 |
Correct |
424 ms |
58920 KB |
Output is correct |
42 |
Correct |
464 ms |
63536 KB |
Output is correct |
43 |
Correct |
471 ms |
82100 KB |
Output is correct |
44 |
Correct |
115 ms |
1992 KB |
Output is correct |
45 |
Correct |
142 ms |
2116 KB |
Output is correct |
46 |
Correct |
188 ms |
1960 KB |
Output is correct |
47 |
Correct |
231 ms |
2124 KB |
Output is correct |
48 |
Correct |
323 ms |
2792 KB |
Output is correct |
49 |
Correct |
873 ms |
66756 KB |
Output is correct |
50 |
Correct |
867 ms |
66868 KB |
Output is correct |
51 |
Correct |
870 ms |
66636 KB |
Output is correct |
52 |
Correct |
1040 ms |
66716 KB |
Output is correct |
53 |
Correct |
791 ms |
66808 KB |
Output is correct |
54 |
Correct |
805 ms |
66764 KB |
Output is correct |
55 |
Correct |
801 ms |
66780 KB |
Output is correct |
56 |
Correct |
160 ms |
2020 KB |
Output is correct |
57 |
Correct |
302 ms |
2020 KB |
Output is correct |
58 |
Correct |
441 ms |
2620 KB |
Output is correct |
59 |
Correct |
1144 ms |
58968 KB |
Output is correct |
60 |
Correct |
1452 ms |
59032 KB |
Output is correct |
61 |
Correct |
930 ms |
59032 KB |
Output is correct |
62 |
Correct |
900 ms |
62792 KB |
Output is correct |
63 |
Correct |
1436 ms |
61504 KB |
Output is correct |
64 |
Correct |
1132 ms |
59784 KB |
Output is correct |
65 |
Correct |
927 ms |
59016 KB |
Output is correct |
66 |
Correct |
1087 ms |
59368 KB |
Output is correct |
67 |
Correct |
1043 ms |
63564 KB |
Output is correct |
68 |
Correct |
890 ms |
73352 KB |
Output is correct |
69 |
Correct |
1351 ms |
82664 KB |
Output is correct |