# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
851206 |
2023-09-18T20:46:24 Z |
Pajaraja |
Seats (IOI18_seats) |
C++17 |
|
2240 ms |
117144 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int seg[4*MAXN],bag[4*MAXN],kol[4*MAXN];
vector<vector<int>> mat;
vector<int> row,col;
int h,w;
void relax(int ind)
{
bag[2*ind]+=bag[ind];
bag[2*ind+1]+=bag[ind];
kol[ind]=0;
bag[ind]=0;
}
void upd(int l,int r,int lt,int val,int ind)
{
if(l>=lt)
{
bag[ind]+=val;
return;
}
if(r<lt) return;
relax(ind);
int s=(l+r)/2;
upd(l,s,lt,val,2*ind);
upd(s+1,r,lt,val,2*ind+1);
seg[ind]=min(seg[2*ind]+bag[2*ind],seg[2*ind+1]+bag[2*ind+1]);
if(seg[ind]==seg[2*ind]+bag[2*ind]) kol[ind]+=kol[2*ind];
if(seg[ind]==seg[2*ind+1]+bag[2*ind+1]) kol[ind]+=kol[2*ind+1];
}
void build(int l,int r,int ind)
{
kol[ind]=r-l+1;
if(l==r) return;
int s=(l+r)/2;
build(l,s,2*ind);
build(s+1,r,2*ind+1);
}
void twobytwo(int x,int y,int what)
{
vector<int> v;
v.push_back(mat[x][y]); v.push_back(mat[x+1][y]); v.push_back(mat[x][y+1]);v.push_back(mat[x+1][y+1]);
sort(v.begin(),v.end());
for(int i=0;i<4;i++) upd(1,h*w,v[i],1-((i+what)&1)*2,1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h=H;
w=W;
for(int i=0;i<h*w;i++) row.push_back(R[i]+1);
for(int i=0;i<h*w;i++) col.push_back(C[i]+1);
vector<int> v;
for(int i=0;i<w+2;i++) v.push_back(MAXN);
for(int i=0;i<h+2;i++) mat.push_back(v);
for(int i=0;i<h*w;i++) mat[row[i]][col[i]]=i;
build(1,h*w,1);
for(int i=0;i<h+1;i++) for(int j=0;j<w+1;j++) twobytwo(i,j,0);
}
int swap_seats(int a, int b) {
twobytwo(row[a],col[a],1); twobytwo(row[a]-1,col[a],1); twobytwo(row[a],col[a]-1,1); twobytwo(row[a]-1,col[a]-1,1);
twobytwo(row[b],col[b],1); twobytwo(row[b]-1,col[b],1); twobytwo(row[b],col[b]-1,1); twobytwo(row[b]-1,col[b]-1,1);
swap(row[a],row[b]);
swap(col[a],col[b]);
swap(mat[row[a]][col[a]],mat[row[b]][col[b]]);
twobytwo(row[a],col[a],0); twobytwo(row[a]-1,col[a],0); twobytwo(row[a],col[a]-1,0); twobytwo(row[a]-1,col[a]-1,0);
twobytwo(row[b],col[b],0); twobytwo(row[b]-1,col[b],0); twobytwo(row[b],col[b]-1,0); twobytwo(row[b]-1,col[b]-1,0);
return kol[1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
344 KB |
Output is correct |
2 |
Correct |
22 ms |
604 KB |
Output is correct |
3 |
Correct |
28 ms |
576 KB |
Output is correct |
4 |
Correct |
19 ms |
600 KB |
Output is correct |
5 |
Correct |
19 ms |
2628 KB |
Output is correct |
6 |
Correct |
25 ms |
600 KB |
Output is correct |
7 |
Correct |
29 ms |
820 KB |
Output is correct |
8 |
Correct |
30 ms |
600 KB |
Output is correct |
9 |
Correct |
30 ms |
2644 KB |
Output is correct |
10 |
Correct |
27 ms |
2644 KB |
Output is correct |
11 |
Correct |
25 ms |
600 KB |
Output is correct |
12 |
Correct |
19 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
344 KB |
Output is correct |
2 |
Correct |
22 ms |
604 KB |
Output is correct |
3 |
Correct |
28 ms |
576 KB |
Output is correct |
4 |
Correct |
19 ms |
600 KB |
Output is correct |
5 |
Correct |
19 ms |
2628 KB |
Output is correct |
6 |
Correct |
25 ms |
600 KB |
Output is correct |
7 |
Correct |
29 ms |
820 KB |
Output is correct |
8 |
Correct |
30 ms |
600 KB |
Output is correct |
9 |
Correct |
30 ms |
2644 KB |
Output is correct |
10 |
Correct |
27 ms |
2644 KB |
Output is correct |
11 |
Correct |
25 ms |
600 KB |
Output is correct |
12 |
Correct |
19 ms |
604 KB |
Output is correct |
13 |
Correct |
60 ms |
3160 KB |
Output is correct |
14 |
Correct |
62 ms |
1116 KB |
Output is correct |
15 |
Correct |
40 ms |
1412 KB |
Output is correct |
16 |
Correct |
37 ms |
3712 KB |
Output is correct |
17 |
Correct |
51 ms |
1336 KB |
Output is correct |
18 |
Correct |
62 ms |
3200 KB |
Output is correct |
19 |
Correct |
59 ms |
1116 KB |
Output is correct |
20 |
Correct |
51 ms |
1588 KB |
Output is correct |
21 |
Correct |
39 ms |
1624 KB |
Output is correct |
22 |
Correct |
37 ms |
1796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1394 ms |
49972 KB |
Output is correct |
2 |
Correct |
1131 ms |
67616 KB |
Output is correct |
3 |
Correct |
1162 ms |
67756 KB |
Output is correct |
4 |
Correct |
1035 ms |
67644 KB |
Output is correct |
5 |
Correct |
1067 ms |
67620 KB |
Output is correct |
6 |
Correct |
1029 ms |
67636 KB |
Output is correct |
7 |
Correct |
1099 ms |
67836 KB |
Output is correct |
8 |
Correct |
1136 ms |
67616 KB |
Output is correct |
9 |
Correct |
1153 ms |
65924 KB |
Output is correct |
10 |
Correct |
1182 ms |
66724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
2908 KB |
Output is correct |
2 |
Correct |
156 ms |
10980 KB |
Output is correct |
3 |
Correct |
1056 ms |
66328 KB |
Output is correct |
4 |
Correct |
1394 ms |
65920 KB |
Output is correct |
5 |
Correct |
1041 ms |
79392 KB |
Output is correct |
6 |
Correct |
1515 ms |
117144 KB |
Output is correct |
7 |
Correct |
1077 ms |
70568 KB |
Output is correct |
8 |
Correct |
1168 ms |
66036 KB |
Output is correct |
9 |
Correct |
1096 ms |
65944 KB |
Output is correct |
10 |
Correct |
1123 ms |
71572 KB |
Output is correct |
11 |
Correct |
1055 ms |
89428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
1488 KB |
Output is correct |
2 |
Correct |
117 ms |
2024 KB |
Output is correct |
3 |
Correct |
187 ms |
2156 KB |
Output is correct |
4 |
Correct |
239 ms |
4508 KB |
Output is correct |
5 |
Correct |
294 ms |
2768 KB |
Output is correct |
6 |
Correct |
1469 ms |
80248 KB |
Output is correct |
7 |
Correct |
1579 ms |
78748 KB |
Output is correct |
8 |
Correct |
1432 ms |
80644 KB |
Output is correct |
9 |
Correct |
1904 ms |
78708 KB |
Output is correct |
10 |
Correct |
1398 ms |
79900 KB |
Output is correct |
11 |
Correct |
1408 ms |
79716 KB |
Output is correct |
12 |
Correct |
1397 ms |
79912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
344 KB |
Output is correct |
2 |
Correct |
22 ms |
604 KB |
Output is correct |
3 |
Correct |
28 ms |
576 KB |
Output is correct |
4 |
Correct |
19 ms |
600 KB |
Output is correct |
5 |
Correct |
19 ms |
2628 KB |
Output is correct |
6 |
Correct |
25 ms |
600 KB |
Output is correct |
7 |
Correct |
29 ms |
820 KB |
Output is correct |
8 |
Correct |
30 ms |
600 KB |
Output is correct |
9 |
Correct |
30 ms |
2644 KB |
Output is correct |
10 |
Correct |
27 ms |
2644 KB |
Output is correct |
11 |
Correct |
25 ms |
600 KB |
Output is correct |
12 |
Correct |
19 ms |
604 KB |
Output is correct |
13 |
Correct |
60 ms |
3160 KB |
Output is correct |
14 |
Correct |
62 ms |
1116 KB |
Output is correct |
15 |
Correct |
40 ms |
1412 KB |
Output is correct |
16 |
Correct |
37 ms |
3712 KB |
Output is correct |
17 |
Correct |
51 ms |
1336 KB |
Output is correct |
18 |
Correct |
62 ms |
3200 KB |
Output is correct |
19 |
Correct |
59 ms |
1116 KB |
Output is correct |
20 |
Correct |
51 ms |
1588 KB |
Output is correct |
21 |
Correct |
39 ms |
1624 KB |
Output is correct |
22 |
Correct |
37 ms |
1796 KB |
Output is correct |
23 |
Correct |
1394 ms |
49972 KB |
Output is correct |
24 |
Correct |
1131 ms |
67616 KB |
Output is correct |
25 |
Correct |
1162 ms |
67756 KB |
Output is correct |
26 |
Correct |
1035 ms |
67644 KB |
Output is correct |
27 |
Correct |
1067 ms |
67620 KB |
Output is correct |
28 |
Correct |
1029 ms |
67636 KB |
Output is correct |
29 |
Correct |
1099 ms |
67836 KB |
Output is correct |
30 |
Correct |
1136 ms |
67616 KB |
Output is correct |
31 |
Correct |
1153 ms |
65924 KB |
Output is correct |
32 |
Correct |
1182 ms |
66724 KB |
Output is correct |
33 |
Correct |
59 ms |
2908 KB |
Output is correct |
34 |
Correct |
156 ms |
10980 KB |
Output is correct |
35 |
Correct |
1056 ms |
66328 KB |
Output is correct |
36 |
Correct |
1394 ms |
65920 KB |
Output is correct |
37 |
Correct |
1041 ms |
79392 KB |
Output is correct |
38 |
Correct |
1515 ms |
117144 KB |
Output is correct |
39 |
Correct |
1077 ms |
70568 KB |
Output is correct |
40 |
Correct |
1168 ms |
66036 KB |
Output is correct |
41 |
Correct |
1096 ms |
65944 KB |
Output is correct |
42 |
Correct |
1123 ms |
71572 KB |
Output is correct |
43 |
Correct |
1055 ms |
89428 KB |
Output is correct |
44 |
Correct |
85 ms |
1488 KB |
Output is correct |
45 |
Correct |
117 ms |
2024 KB |
Output is correct |
46 |
Correct |
187 ms |
2156 KB |
Output is correct |
47 |
Correct |
239 ms |
4508 KB |
Output is correct |
48 |
Correct |
294 ms |
2768 KB |
Output is correct |
49 |
Correct |
1469 ms |
80248 KB |
Output is correct |
50 |
Correct |
1579 ms |
78748 KB |
Output is correct |
51 |
Correct |
1432 ms |
80644 KB |
Output is correct |
52 |
Correct |
1904 ms |
78708 KB |
Output is correct |
53 |
Correct |
1398 ms |
79900 KB |
Output is correct |
54 |
Correct |
1408 ms |
79716 KB |
Output is correct |
55 |
Correct |
1397 ms |
79912 KB |
Output is correct |
56 |
Correct |
149 ms |
2000 KB |
Output is correct |
57 |
Correct |
285 ms |
2012 KB |
Output is correct |
58 |
Correct |
571 ms |
4956 KB |
Output is correct |
59 |
Correct |
1896 ms |
68748 KB |
Output is correct |
60 |
Correct |
2240 ms |
66892 KB |
Output is correct |
61 |
Correct |
1870 ms |
68576 KB |
Output is correct |
62 |
Correct |
1587 ms |
72796 KB |
Output is correct |
63 |
Correct |
2081 ms |
73936 KB |
Output is correct |
64 |
Correct |
1960 ms |
68508 KB |
Output is correct |
65 |
Correct |
1892 ms |
67004 KB |
Output is correct |
66 |
Correct |
1899 ms |
69016 KB |
Output is correct |
67 |
Correct |
1877 ms |
71732 KB |
Output is correct |
68 |
Correct |
1656 ms |
82624 KB |
Output is correct |
69 |
Correct |
2077 ms |
90528 KB |
Output is correct |