# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
819979 |
2023-08-10T16:52:59 Z |
ttamx |
Seats (IOI18_seats) |
C++14 |
|
834 ms |
103308 KB |
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int K=(1<<21)+5;
const int inf=1e9;
int h,w,n;
int r[N],c[N];
vector<vector<int>> val;
int pref[N];
int tmp[N];
int calc(int id){
if(id==n+1)return inf;
int x=r[id],y=c[id];
int res=0;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int cnt=1;
for(int k=0;k<2;k++){
for(int l=0;l<2;l++){
if(val[x+i-k][y+j-l]<id)cnt++;
}
}
res+=cnt%2==1?1:-1;
}
}
return res;
}
struct segtree{
struct node{
int val,freq;
node():val(inf),freq(0){}
node(int val,int freq=1):val(val),freq(freq){}
friend node operator+(node a,node b){
if(a.val<b.val)return a;
if(b.val<a.val)return b;
return node(a.val,a.freq+b.freq);
}
}t[K];
int lz[K];
void pushlz(int l,int r,int i){
t[i].val+=lz[i];
if(l<r){
lz[i*2]+=lz[i];
lz[i*2+1]+=lz[i];
}
lz[i]=0;
}
void build(int l,int r,int i){
if(l==r)return void(t[i]=node(pref[l]));
int m=(l+r)/2;
build(l,m,i*2);
build(m+1,r,i*2+1);
t[i]=t[i*2]+t[i*2+1];
}
void build(){
build(1,n,1);
}
void update(int l,int r,int i,int x,int y,int v){
pushlz(l,r,i);
if(y<l||r<x)return;
if(x<=l&&r<=y)return lz[i]=v,pushlz(l,r,i),void();
int m=(l+r)/2;
update(l,m,i*2,x,y,v);
update(m+1,r,i*2+1,x,y,v);
t[i]=t[i*2]+t[i*2+1];
}
void update(int x,int y,int v){
update(1,n,1,x,y,v);
}
int query(int l,int r,int i,int x){
pushlz(l,r,i);
if(l==r)return t[i].val;
int m=(l+r)/2;
if(x<=m)return query(l,m,i*2,x);
return query(m+1,r,i*2+1,x);
}
int query(int x){
return query(1,n,1,x);
}
}s;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h=H,w=W;
n=h*w;
val=vector<vector<int>>(h+2,vector<int>(w+2,n+1));
for(int i=1;i<=n;i++){
r[i]=R[i-1]+1;
c[i]=C[i-1]+1;
val[r[i]][c[i]]=i;
tmp[i]=inf;
}
for(int i=1;i<=n;i++){
pref[i]=pref[i-1]+calc(i);
}
s.build();
}
int swap_seats(int a, int b){
a++,b++;
if(c[a]>c[b])swap(a,b);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
int id1=val[r[a]+i][c[a]+j];
int id2=val[r[b]+i][c[b]+j];
if(tmp[id1]==inf)tmp[id1]=calc(id1);
if(tmp[id2]==inf)tmp[id2]=calc(id2);
}
}
swap(r[a],r[b]);
swap(c[a],c[b]);
val[r[a]][c[a]]=a;
val[r[b]][c[b]]=b;
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
int id1=val[r[a]+i][c[a]+j];
int id2=val[r[b]+i][c[b]+j];
if(tmp[id1]!=inf){
s.update(id1,n,calc(id1)-tmp[id1]);
tmp[id1]=inf;
}
if(tmp[id2]!=inf){
s.update(id2,n,calc(id2)-tmp[id2]);
tmp[id2]=inf;
}
}
}
return s.t[1].freq;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16852 KB |
Output is correct |
2 |
Correct |
16 ms |
16840 KB |
Output is correct |
3 |
Correct |
26 ms |
16800 KB |
Output is correct |
4 |
Correct |
12 ms |
16768 KB |
Output is correct |
5 |
Correct |
12 ms |
16876 KB |
Output is correct |
6 |
Correct |
17 ms |
16852 KB |
Output is correct |
7 |
Correct |
20 ms |
16808 KB |
Output is correct |
8 |
Correct |
19 ms |
16840 KB |
Output is correct |
9 |
Correct |
19 ms |
16772 KB |
Output is correct |
10 |
Correct |
19 ms |
16804 KB |
Output is correct |
11 |
Correct |
18 ms |
16828 KB |
Output is correct |
12 |
Correct |
13 ms |
16888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16852 KB |
Output is correct |
2 |
Correct |
16 ms |
16840 KB |
Output is correct |
3 |
Correct |
26 ms |
16800 KB |
Output is correct |
4 |
Correct |
12 ms |
16768 KB |
Output is correct |
5 |
Correct |
12 ms |
16876 KB |
Output is correct |
6 |
Correct |
17 ms |
16852 KB |
Output is correct |
7 |
Correct |
20 ms |
16808 KB |
Output is correct |
8 |
Correct |
19 ms |
16840 KB |
Output is correct |
9 |
Correct |
19 ms |
16772 KB |
Output is correct |
10 |
Correct |
19 ms |
16804 KB |
Output is correct |
11 |
Correct |
18 ms |
16828 KB |
Output is correct |
12 |
Correct |
13 ms |
16888 KB |
Output is correct |
13 |
Correct |
32 ms |
17384 KB |
Output is correct |
14 |
Correct |
34 ms |
17268 KB |
Output is correct |
15 |
Correct |
17 ms |
17388 KB |
Output is correct |
16 |
Correct |
16 ms |
17700 KB |
Output is correct |
17 |
Correct |
25 ms |
17356 KB |
Output is correct |
18 |
Correct |
30 ms |
17268 KB |
Output is correct |
19 |
Correct |
27 ms |
17316 KB |
Output is correct |
20 |
Correct |
23 ms |
17508 KB |
Output is correct |
21 |
Correct |
17 ms |
17304 KB |
Output is correct |
22 |
Correct |
17 ms |
17700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
291 ms |
52432 KB |
Output is correct |
2 |
Correct |
295 ms |
52432 KB |
Output is correct |
3 |
Correct |
235 ms |
52404 KB |
Output is correct |
4 |
Correct |
238 ms |
52560 KB |
Output is correct |
5 |
Correct |
232 ms |
52456 KB |
Output is correct |
6 |
Correct |
224 ms |
52452 KB |
Output is correct |
7 |
Correct |
243 ms |
52548 KB |
Output is correct |
8 |
Correct |
234 ms |
52420 KB |
Output is correct |
9 |
Correct |
227 ms |
52420 KB |
Output is correct |
10 |
Correct |
233 ms |
52436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
17276 KB |
Output is correct |
2 |
Correct |
51 ms |
20288 KB |
Output is correct |
3 |
Correct |
230 ms |
52428 KB |
Output is correct |
4 |
Correct |
290 ms |
52440 KB |
Output is correct |
5 |
Correct |
212 ms |
60188 KB |
Output is correct |
6 |
Correct |
426 ms |
103308 KB |
Output is correct |
7 |
Correct |
251 ms |
54984 KB |
Output is correct |
8 |
Correct |
241 ms |
52444 KB |
Output is correct |
9 |
Correct |
259 ms |
52824 KB |
Output is correct |
10 |
Correct |
239 ms |
57044 KB |
Output is correct |
11 |
Correct |
238 ms |
75856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
17760 KB |
Output is correct |
2 |
Correct |
41 ms |
17760 KB |
Output is correct |
3 |
Correct |
55 ms |
17732 KB |
Output is correct |
4 |
Correct |
70 ms |
17840 KB |
Output is correct |
5 |
Correct |
89 ms |
18356 KB |
Output is correct |
6 |
Correct |
378 ms |
61252 KB |
Output is correct |
7 |
Correct |
379 ms |
61244 KB |
Output is correct |
8 |
Correct |
379 ms |
61340 KB |
Output is correct |
9 |
Correct |
436 ms |
61316 KB |
Output is correct |
10 |
Correct |
325 ms |
61312 KB |
Output is correct |
11 |
Correct |
332 ms |
61296 KB |
Output is correct |
12 |
Correct |
332 ms |
61252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16852 KB |
Output is correct |
2 |
Correct |
16 ms |
16840 KB |
Output is correct |
3 |
Correct |
26 ms |
16800 KB |
Output is correct |
4 |
Correct |
12 ms |
16768 KB |
Output is correct |
5 |
Correct |
12 ms |
16876 KB |
Output is correct |
6 |
Correct |
17 ms |
16852 KB |
Output is correct |
7 |
Correct |
20 ms |
16808 KB |
Output is correct |
8 |
Correct |
19 ms |
16840 KB |
Output is correct |
9 |
Correct |
19 ms |
16772 KB |
Output is correct |
10 |
Correct |
19 ms |
16804 KB |
Output is correct |
11 |
Correct |
18 ms |
16828 KB |
Output is correct |
12 |
Correct |
13 ms |
16888 KB |
Output is correct |
13 |
Correct |
32 ms |
17384 KB |
Output is correct |
14 |
Correct |
34 ms |
17268 KB |
Output is correct |
15 |
Correct |
17 ms |
17388 KB |
Output is correct |
16 |
Correct |
16 ms |
17700 KB |
Output is correct |
17 |
Correct |
25 ms |
17356 KB |
Output is correct |
18 |
Correct |
30 ms |
17268 KB |
Output is correct |
19 |
Correct |
27 ms |
17316 KB |
Output is correct |
20 |
Correct |
23 ms |
17508 KB |
Output is correct |
21 |
Correct |
17 ms |
17304 KB |
Output is correct |
22 |
Correct |
17 ms |
17700 KB |
Output is correct |
23 |
Correct |
291 ms |
52432 KB |
Output is correct |
24 |
Correct |
295 ms |
52432 KB |
Output is correct |
25 |
Correct |
235 ms |
52404 KB |
Output is correct |
26 |
Correct |
238 ms |
52560 KB |
Output is correct |
27 |
Correct |
232 ms |
52456 KB |
Output is correct |
28 |
Correct |
224 ms |
52452 KB |
Output is correct |
29 |
Correct |
243 ms |
52548 KB |
Output is correct |
30 |
Correct |
234 ms |
52420 KB |
Output is correct |
31 |
Correct |
227 ms |
52420 KB |
Output is correct |
32 |
Correct |
233 ms |
52436 KB |
Output is correct |
33 |
Correct |
31 ms |
17276 KB |
Output is correct |
34 |
Correct |
51 ms |
20288 KB |
Output is correct |
35 |
Correct |
230 ms |
52428 KB |
Output is correct |
36 |
Correct |
290 ms |
52440 KB |
Output is correct |
37 |
Correct |
212 ms |
60188 KB |
Output is correct |
38 |
Correct |
426 ms |
103308 KB |
Output is correct |
39 |
Correct |
251 ms |
54984 KB |
Output is correct |
40 |
Correct |
241 ms |
52444 KB |
Output is correct |
41 |
Correct |
259 ms |
52824 KB |
Output is correct |
42 |
Correct |
239 ms |
57044 KB |
Output is correct |
43 |
Correct |
238 ms |
75856 KB |
Output is correct |
44 |
Correct |
35 ms |
17760 KB |
Output is correct |
45 |
Correct |
41 ms |
17760 KB |
Output is correct |
46 |
Correct |
55 ms |
17732 KB |
Output is correct |
47 |
Correct |
70 ms |
17840 KB |
Output is correct |
48 |
Correct |
89 ms |
18356 KB |
Output is correct |
49 |
Correct |
378 ms |
61252 KB |
Output is correct |
50 |
Correct |
379 ms |
61244 KB |
Output is correct |
51 |
Correct |
379 ms |
61340 KB |
Output is correct |
52 |
Correct |
436 ms |
61316 KB |
Output is correct |
53 |
Correct |
325 ms |
61312 KB |
Output is correct |
54 |
Correct |
332 ms |
61296 KB |
Output is correct |
55 |
Correct |
332 ms |
61252 KB |
Output is correct |
56 |
Correct |
62 ms |
18388 KB |
Output is correct |
57 |
Correct |
143 ms |
18396 KB |
Output is correct |
58 |
Correct |
238 ms |
18988 KB |
Output is correct |
59 |
Correct |
634 ms |
70148 KB |
Output is correct |
60 |
Correct |
834 ms |
70188 KB |
Output is correct |
61 |
Correct |
541 ms |
70068 KB |
Output is correct |
62 |
Correct |
420 ms |
73924 KB |
Output is correct |
63 |
Correct |
716 ms |
72632 KB |
Output is correct |
64 |
Correct |
605 ms |
70880 KB |
Output is correct |
65 |
Correct |
548 ms |
70092 KB |
Output is correct |
66 |
Correct |
640 ms |
70508 KB |
Output is correct |
67 |
Correct |
592 ms |
74680 KB |
Output is correct |
68 |
Correct |
494 ms |
84404 KB |
Output is correct |
69 |
Correct |
819 ms |
93492 KB |
Output is correct |