# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
674398 |
2022-12-24T02:34:03 Z |
alvingogo |
Seats (IOI18_seats) |
C++14 |
|
2683 ms |
142080 KB |
#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int h,w;
vector<vector<int> > val;
vector<pair<int,int> > y;
int n;
struct ST{
struct no{
int mn=0,cnt=1,tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void upd(int v,int k){
st[v].mn+=k;
st[v].tag+=k;
}
void pudo(int v){
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=0;
}
void pull(int v){
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
st[v].cnt=0;
if(st[2*v+1].mn==st[v].mn){
st[v].cnt+=st[2*v+1].cnt;
}
if(st[2*v+2].mn==st[v].mn){
st[v].cnt+=st[2*v+2].cnt;
}
}
void update(int v,int L,int R,int l,int r,int k){
if(r<l){
return;
}
if(L==l && r==R){
upd(v,k);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,k);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,k);
}
else{
update(2*v+1,L,m,l,m,k);
update(2*v+2,m+1,R,m+1,r,k);
}
pull(v);
}
int query(){
return st[0].cnt;
}
}st;
void ud(int a,int b,int c,int d,int k){
vector<int> g{a,b,c,d};
sort(g.begin(),g.end());
st.update(0,0,n-1,g[0],g[1]-1,k);
st.update(0,0,n-1,g[2],g[3]-1,k);
}
inline void chg(int i,int j,int t){
ud(val[i][j],val[i+1][j],val[i+1][j+1],val[i][j+1],t);
}
void give_initial_chart(int a,int b,vector<int> r,vector<int> c){
h=a;
w=b;
val.clear();
val.resize(h+2,vector<int>(w+2,h*w));
n=h*w+1;
st.init(n);
st.update(0,0,n-1,n-1,n-1,1e9);
for(int i=0;i<h*w;i++){
val[r[i]+1][c[i]+1]=i;
y.push_back({r[i]+1,c[i]+1});
}
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
chg(i,j,1);
}
}
}
const int dx[4]={0,0,-1,-1};
const int dy[4]={0,-1,0,-1};
int swap_seats(int a,int b){
auto c=y[a];
auto d=y[b];
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],-1);
chg(d.fs+dx[i],d.sc+dy[i],-1);
}
swap(val[c.fs][c.sc],val[d.fs][d.sc]);
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],1);
chg(d.fs+dx[i],d.sc+dy[i],1);
}
swap(y[a],y[b]);
return st.query();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
340 KB |
Output is correct |
2 |
Correct |
17 ms |
420 KB |
Output is correct |
3 |
Correct |
28 ms |
416 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
15 ms |
468 KB |
Output is correct |
6 |
Correct |
23 ms |
424 KB |
Output is correct |
7 |
Correct |
25 ms |
448 KB |
Output is correct |
8 |
Correct |
22 ms |
460 KB |
Output is correct |
9 |
Correct |
22 ms |
444 KB |
Output is correct |
10 |
Correct |
26 ms |
460 KB |
Output is correct |
11 |
Correct |
23 ms |
428 KB |
Output is correct |
12 |
Correct |
15 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
340 KB |
Output is correct |
2 |
Correct |
17 ms |
420 KB |
Output is correct |
3 |
Correct |
28 ms |
416 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
15 ms |
468 KB |
Output is correct |
6 |
Correct |
23 ms |
424 KB |
Output is correct |
7 |
Correct |
25 ms |
448 KB |
Output is correct |
8 |
Correct |
22 ms |
460 KB |
Output is correct |
9 |
Correct |
22 ms |
444 KB |
Output is correct |
10 |
Correct |
26 ms |
460 KB |
Output is correct |
11 |
Correct |
23 ms |
428 KB |
Output is correct |
12 |
Correct |
15 ms |
452 KB |
Output is correct |
13 |
Correct |
61 ms |
1388 KB |
Output is correct |
14 |
Correct |
74 ms |
1364 KB |
Output is correct |
15 |
Correct |
42 ms |
1480 KB |
Output is correct |
16 |
Correct |
31 ms |
1908 KB |
Output is correct |
17 |
Correct |
52 ms |
1436 KB |
Output is correct |
18 |
Correct |
50 ms |
1408 KB |
Output is correct |
19 |
Correct |
46 ms |
1448 KB |
Output is correct |
20 |
Correct |
40 ms |
1628 KB |
Output is correct |
21 |
Correct |
32 ms |
1484 KB |
Output is correct |
22 |
Correct |
32 ms |
1892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1686 ms |
75184 KB |
Output is correct |
2 |
Correct |
908 ms |
91192 KB |
Output is correct |
3 |
Correct |
870 ms |
91168 KB |
Output is correct |
4 |
Correct |
766 ms |
91168 KB |
Output is correct |
5 |
Correct |
794 ms |
91172 KB |
Output is correct |
6 |
Correct |
751 ms |
91160 KB |
Output is correct |
7 |
Correct |
805 ms |
91172 KB |
Output is correct |
8 |
Correct |
832 ms |
91172 KB |
Output is correct |
9 |
Correct |
832 ms |
91152 KB |
Output is correct |
10 |
Correct |
853 ms |
91200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
1236 KB |
Output is correct |
2 |
Correct |
134 ms |
8792 KB |
Output is correct |
3 |
Correct |
790 ms |
91248 KB |
Output is correct |
4 |
Correct |
1675 ms |
91168 KB |
Output is correct |
5 |
Correct |
739 ms |
103052 KB |
Output is correct |
6 |
Correct |
1734 ms |
142080 KB |
Output is correct |
7 |
Correct |
771 ms |
95644 KB |
Output is correct |
8 |
Correct |
921 ms |
91232 KB |
Output is correct |
9 |
Correct |
788 ms |
91520 KB |
Output is correct |
10 |
Correct |
849 ms |
95820 KB |
Output is correct |
11 |
Correct |
807 ms |
114680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
1268 KB |
Output is correct |
2 |
Correct |
99 ms |
1984 KB |
Output is correct |
3 |
Correct |
143 ms |
1924 KB |
Output is correct |
4 |
Correct |
207 ms |
2120 KB |
Output is correct |
5 |
Correct |
313 ms |
2952 KB |
Output is correct |
6 |
Correct |
1186 ms |
104080 KB |
Output is correct |
7 |
Correct |
1339 ms |
103864 KB |
Output is correct |
8 |
Correct |
1144 ms |
103992 KB |
Output is correct |
9 |
Correct |
2180 ms |
103892 KB |
Output is correct |
10 |
Correct |
1091 ms |
103984 KB |
Output is correct |
11 |
Correct |
1172 ms |
103868 KB |
Output is correct |
12 |
Correct |
1035 ms |
103836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
340 KB |
Output is correct |
2 |
Correct |
17 ms |
420 KB |
Output is correct |
3 |
Correct |
28 ms |
416 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
15 ms |
468 KB |
Output is correct |
6 |
Correct |
23 ms |
424 KB |
Output is correct |
7 |
Correct |
25 ms |
448 KB |
Output is correct |
8 |
Correct |
22 ms |
460 KB |
Output is correct |
9 |
Correct |
22 ms |
444 KB |
Output is correct |
10 |
Correct |
26 ms |
460 KB |
Output is correct |
11 |
Correct |
23 ms |
428 KB |
Output is correct |
12 |
Correct |
15 ms |
452 KB |
Output is correct |
13 |
Correct |
61 ms |
1388 KB |
Output is correct |
14 |
Correct |
74 ms |
1364 KB |
Output is correct |
15 |
Correct |
42 ms |
1480 KB |
Output is correct |
16 |
Correct |
31 ms |
1908 KB |
Output is correct |
17 |
Correct |
52 ms |
1436 KB |
Output is correct |
18 |
Correct |
50 ms |
1408 KB |
Output is correct |
19 |
Correct |
46 ms |
1448 KB |
Output is correct |
20 |
Correct |
40 ms |
1628 KB |
Output is correct |
21 |
Correct |
32 ms |
1484 KB |
Output is correct |
22 |
Correct |
32 ms |
1892 KB |
Output is correct |
23 |
Correct |
1686 ms |
75184 KB |
Output is correct |
24 |
Correct |
908 ms |
91192 KB |
Output is correct |
25 |
Correct |
870 ms |
91168 KB |
Output is correct |
26 |
Correct |
766 ms |
91168 KB |
Output is correct |
27 |
Correct |
794 ms |
91172 KB |
Output is correct |
28 |
Correct |
751 ms |
91160 KB |
Output is correct |
29 |
Correct |
805 ms |
91172 KB |
Output is correct |
30 |
Correct |
832 ms |
91172 KB |
Output is correct |
31 |
Correct |
832 ms |
91152 KB |
Output is correct |
32 |
Correct |
853 ms |
91200 KB |
Output is correct |
33 |
Correct |
58 ms |
1236 KB |
Output is correct |
34 |
Correct |
134 ms |
8792 KB |
Output is correct |
35 |
Correct |
790 ms |
91248 KB |
Output is correct |
36 |
Correct |
1675 ms |
91168 KB |
Output is correct |
37 |
Correct |
739 ms |
103052 KB |
Output is correct |
38 |
Correct |
1734 ms |
142080 KB |
Output is correct |
39 |
Correct |
771 ms |
95644 KB |
Output is correct |
40 |
Correct |
921 ms |
91232 KB |
Output is correct |
41 |
Correct |
788 ms |
91520 KB |
Output is correct |
42 |
Correct |
849 ms |
95820 KB |
Output is correct |
43 |
Correct |
807 ms |
114680 KB |
Output is correct |
44 |
Correct |
64 ms |
1268 KB |
Output is correct |
45 |
Correct |
99 ms |
1984 KB |
Output is correct |
46 |
Correct |
143 ms |
1924 KB |
Output is correct |
47 |
Correct |
207 ms |
2120 KB |
Output is correct |
48 |
Correct |
313 ms |
2952 KB |
Output is correct |
49 |
Correct |
1186 ms |
104080 KB |
Output is correct |
50 |
Correct |
1339 ms |
103864 KB |
Output is correct |
51 |
Correct |
1144 ms |
103992 KB |
Output is correct |
52 |
Correct |
2180 ms |
103892 KB |
Output is correct |
53 |
Correct |
1091 ms |
103984 KB |
Output is correct |
54 |
Correct |
1172 ms |
103868 KB |
Output is correct |
55 |
Correct |
1035 ms |
103836 KB |
Output is correct |
56 |
Correct |
117 ms |
1992 KB |
Output is correct |
57 |
Correct |
274 ms |
2056 KB |
Output is correct |
58 |
Correct |
444 ms |
2860 KB |
Output is correct |
59 |
Correct |
1471 ms |
92264 KB |
Output is correct |
60 |
Correct |
2683 ms |
92068 KB |
Output is correct |
61 |
Correct |
1397 ms |
92180 KB |
Output is correct |
62 |
Correct |
1159 ms |
97904 KB |
Output is correct |
63 |
Correct |
2477 ms |
96684 KB |
Output is correct |
64 |
Correct |
1601 ms |
93356 KB |
Output is correct |
65 |
Correct |
1439 ms |
92156 KB |
Output is correct |
66 |
Correct |
1539 ms |
92512 KB |
Output is correct |
67 |
Correct |
1627 ms |
96816 KB |
Output is correct |
68 |
Correct |
1325 ms |
106684 KB |
Output is correct |
69 |
Correct |
2494 ms |
115528 KB |
Output is correct |