# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
119727 |
2019-06-22T03:37:15 Z |
imyujin |
Seats (IOI18_seats) |
C++14 |
|
3592 ms |
65912 KB |
#include "seats.h"
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 1000010
int N, H, W;
vector<int> R, C;
int a[3*MAXN];
int seg[MAXN*6], lazy[MAXN*6], num[MAXN*6];
int t[4];
void mkseg(int idx, int l, int r){
num[idx]=r-l+1;
if(l<r){
int m=l+r>>1;
mkseg(idx*2, l, m);
mkseg(idx*2+1, m+1, r);
}
}
void updseg(int idx, int l, int r, int x, int y, int z){
//if(idx==1) printf("(%d %d %d)\n", x, y, z);
if(x<=l&&r<=y){
lazy[idx]+=z;
seg[idx]+=z;
}
else if(l<=y&&x<=r){
int m=l+r>>1;
lazy[idx*2]+=lazy[idx];
lazy[idx*2+1]+=lazy[idx];
seg[idx*2]+=lazy[idx];
seg[idx*2+1]+=lazy[idx];
lazy[idx]=0;
updseg(idx*2, l, m, x, y, z);
updseg(idx*2+1, m+1, r, x, y, z);
if(seg[idx*2]<seg[idx*2+1]){
seg[idx]=seg[idx*2];
num[idx]=num[idx*2];
}
else if(seg[idx*2+1]<seg[idx*2]){
seg[idx]=seg[idx*2+1];
num[idx]=num[idx*2+1];
}
else{
seg[idx]=seg[idx*2];
num[idx]=num[idx*2]+num[idx*2+1];
}
}
}
void updcor(int i, int j, int z){
t[0]=a[i*(W+2)+j];
t[1]=a[i*(W+2)+j+1];
t[2]=a[(i+1)*(W+2)+j];
t[3]=a[(i+1)*(W+2)+j+1];
sort(t, t+4);
if(t[0]<t[1]) updseg(1, 0, N-1, t[0], t[1]-1, z);
if(t[2]<t[3]) updseg(1, 0, N-1, t[2], t[3]-1, z);
}
void updsea(int i, int j, int z){
//printf("{%d %d %d}\n", i, j, z);
updcor(i, j, z);
updcor(i, j+1, z);
updcor(i+1, j, z);
updcor(i+1, j+1, z);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
H=h;
W=w;
N=H*W;
R=r;
C=c;
for(int i=0; i<N; i++) a[(R[i]+1)*(W+2)+C[i]+1]=i;
for(int i=0; i<=H+1; i++) a[i*(W+2)]=a[i*(W+2)+W+1]=N;
for(int i=0; i<=W+1; i++) a[i]=a[(H+1)*(W+2)+i]=N;
mkseg(1, 0, N-1);
for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) updcor(i, j, 1);
//printf("[%d]\n", num[1]);
}
int swap_seats(int x, int y) {
updsea(R[x], C[x], -1);
updsea(R[y], C[y], -1);
swap(a[(R[x]+1)*(W+2)+C[x]+1], a[(R[y]+1)*(W+2)+C[y]+1]);
swap(R[x], R[y]);
swap(C[x], C[y]);
updsea(R[x], C[x], 1);
updsea(R[y], C[y], 1);
return num[1];
}
Compilation message
seats.cpp: In function 'void mkseg(int, int, int)':
seats.cpp:18:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
seats.cpp: In function 'void updseg(int, int, int, int, int, int)':
seats.cpp:31:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
512 KB |
Output is correct |
2 |
Correct |
20 ms |
512 KB |
Output is correct |
3 |
Correct |
31 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
512 KB |
Output is correct |
5 |
Correct |
17 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
528 KB |
Output is correct |
7 |
Correct |
28 ms |
512 KB |
Output is correct |
8 |
Correct |
26 ms |
512 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
10 |
Correct |
28 ms |
512 KB |
Output is correct |
11 |
Correct |
26 ms |
512 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
512 KB |
Output is correct |
2 |
Correct |
20 ms |
512 KB |
Output is correct |
3 |
Correct |
31 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
512 KB |
Output is correct |
5 |
Correct |
17 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
528 KB |
Output is correct |
7 |
Correct |
28 ms |
512 KB |
Output is correct |
8 |
Correct |
26 ms |
512 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
10 |
Correct |
28 ms |
512 KB |
Output is correct |
11 |
Correct |
26 ms |
512 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
13 |
Correct |
64 ms |
1264 KB |
Output is correct |
14 |
Correct |
76 ms |
1244 KB |
Output is correct |
15 |
Correct |
43 ms |
1280 KB |
Output is correct |
16 |
Correct |
33 ms |
1280 KB |
Output is correct |
17 |
Correct |
54 ms |
1280 KB |
Output is correct |
18 |
Correct |
54 ms |
1272 KB |
Output is correct |
19 |
Correct |
50 ms |
1280 KB |
Output is correct |
20 |
Correct |
45 ms |
1200 KB |
Output is correct |
21 |
Correct |
38 ms |
1280 KB |
Output is correct |
22 |
Correct |
32 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2072 ms |
57424 KB |
Output is correct |
2 |
Correct |
1121 ms |
58024 KB |
Output is correct |
3 |
Correct |
1039 ms |
57976 KB |
Output is correct |
4 |
Correct |
872 ms |
57976 KB |
Output is correct |
5 |
Correct |
955 ms |
58488 KB |
Output is correct |
6 |
Correct |
844 ms |
58508 KB |
Output is correct |
7 |
Correct |
950 ms |
58488 KB |
Output is correct |
8 |
Correct |
1034 ms |
58444 KB |
Output is correct |
9 |
Correct |
1018 ms |
58488 KB |
Output is correct |
10 |
Correct |
977 ms |
58584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
1152 KB |
Output is correct |
2 |
Correct |
156 ms |
7160 KB |
Output is correct |
3 |
Correct |
910 ms |
58232 KB |
Output is correct |
4 |
Correct |
2079 ms |
58236 KB |
Output is correct |
5 |
Correct |
799 ms |
65912 KB |
Output is correct |
6 |
Correct |
1874 ms |
65912 KB |
Output is correct |
7 |
Correct |
881 ms |
60924 KB |
Output is correct |
8 |
Correct |
1214 ms |
58264 KB |
Output is correct |
9 |
Correct |
1047 ms |
58360 KB |
Output is correct |
10 |
Correct |
954 ms |
58908 KB |
Output is correct |
11 |
Correct |
869 ms |
62200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
2020 KB |
Output is correct |
2 |
Correct |
93 ms |
2028 KB |
Output is correct |
3 |
Correct |
144 ms |
1992 KB |
Output is correct |
4 |
Correct |
191 ms |
2120 KB |
Output is correct |
5 |
Correct |
315 ms |
2812 KB |
Output is correct |
6 |
Correct |
1313 ms |
60664 KB |
Output is correct |
7 |
Correct |
1559 ms |
60708 KB |
Output is correct |
8 |
Correct |
1229 ms |
60920 KB |
Output is correct |
9 |
Correct |
2703 ms |
60672 KB |
Output is correct |
10 |
Correct |
1199 ms |
60792 KB |
Output is correct |
11 |
Correct |
1212 ms |
60764 KB |
Output is correct |
12 |
Correct |
1157 ms |
60792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
512 KB |
Output is correct |
2 |
Correct |
20 ms |
512 KB |
Output is correct |
3 |
Correct |
31 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
512 KB |
Output is correct |
5 |
Correct |
17 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
528 KB |
Output is correct |
7 |
Correct |
28 ms |
512 KB |
Output is correct |
8 |
Correct |
26 ms |
512 KB |
Output is correct |
9 |
Correct |
26 ms |
512 KB |
Output is correct |
10 |
Correct |
28 ms |
512 KB |
Output is correct |
11 |
Correct |
26 ms |
512 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
13 |
Correct |
64 ms |
1264 KB |
Output is correct |
14 |
Correct |
76 ms |
1244 KB |
Output is correct |
15 |
Correct |
43 ms |
1280 KB |
Output is correct |
16 |
Correct |
33 ms |
1280 KB |
Output is correct |
17 |
Correct |
54 ms |
1280 KB |
Output is correct |
18 |
Correct |
54 ms |
1272 KB |
Output is correct |
19 |
Correct |
50 ms |
1280 KB |
Output is correct |
20 |
Correct |
45 ms |
1200 KB |
Output is correct |
21 |
Correct |
38 ms |
1280 KB |
Output is correct |
22 |
Correct |
32 ms |
1280 KB |
Output is correct |
23 |
Correct |
2072 ms |
57424 KB |
Output is correct |
24 |
Correct |
1121 ms |
58024 KB |
Output is correct |
25 |
Correct |
1039 ms |
57976 KB |
Output is correct |
26 |
Correct |
872 ms |
57976 KB |
Output is correct |
27 |
Correct |
955 ms |
58488 KB |
Output is correct |
28 |
Correct |
844 ms |
58508 KB |
Output is correct |
29 |
Correct |
950 ms |
58488 KB |
Output is correct |
30 |
Correct |
1034 ms |
58444 KB |
Output is correct |
31 |
Correct |
1018 ms |
58488 KB |
Output is correct |
32 |
Correct |
977 ms |
58584 KB |
Output is correct |
33 |
Correct |
61 ms |
1152 KB |
Output is correct |
34 |
Correct |
156 ms |
7160 KB |
Output is correct |
35 |
Correct |
910 ms |
58232 KB |
Output is correct |
36 |
Correct |
2079 ms |
58236 KB |
Output is correct |
37 |
Correct |
799 ms |
65912 KB |
Output is correct |
38 |
Correct |
1874 ms |
65912 KB |
Output is correct |
39 |
Correct |
881 ms |
60924 KB |
Output is correct |
40 |
Correct |
1214 ms |
58264 KB |
Output is correct |
41 |
Correct |
1047 ms |
58360 KB |
Output is correct |
42 |
Correct |
954 ms |
58908 KB |
Output is correct |
43 |
Correct |
869 ms |
62200 KB |
Output is correct |
44 |
Correct |
48 ms |
2020 KB |
Output is correct |
45 |
Correct |
93 ms |
2028 KB |
Output is correct |
46 |
Correct |
144 ms |
1992 KB |
Output is correct |
47 |
Correct |
191 ms |
2120 KB |
Output is correct |
48 |
Correct |
315 ms |
2812 KB |
Output is correct |
49 |
Correct |
1313 ms |
60664 KB |
Output is correct |
50 |
Correct |
1559 ms |
60708 KB |
Output is correct |
51 |
Correct |
1229 ms |
60920 KB |
Output is correct |
52 |
Correct |
2703 ms |
60672 KB |
Output is correct |
53 |
Correct |
1199 ms |
60792 KB |
Output is correct |
54 |
Correct |
1212 ms |
60764 KB |
Output is correct |
55 |
Correct |
1157 ms |
60792 KB |
Output is correct |
56 |
Correct |
119 ms |
2080 KB |
Output is correct |
57 |
Correct |
282 ms |
2132 KB |
Output is correct |
58 |
Correct |
462 ms |
2984 KB |
Output is correct |
59 |
Correct |
1817 ms |
52864 KB |
Output is correct |
60 |
Correct |
3592 ms |
53012 KB |
Output is correct |
61 |
Correct |
1706 ms |
52984 KB |
Output is correct |
62 |
Correct |
1357 ms |
56828 KB |
Output is correct |
63 |
Correct |
3292 ms |
55544 KB |
Output is correct |
64 |
Correct |
1999 ms |
53752 KB |
Output is correct |
65 |
Correct |
1929 ms |
53084 KB |
Output is correct |
66 |
Correct |
1996 ms |
53112 KB |
Output is correct |
67 |
Correct |
1833 ms |
53880 KB |
Output is correct |
68 |
Correct |
1374 ms |
55544 KB |
Output is correct |
69 |
Correct |
2720 ms |
56860 KB |
Output is correct |