# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248654 |
2020-07-13T00:56:31 Z |
Dormi |
Seats (IOI18_seats) |
C++14 |
|
2745 ms |
118332 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return (int)a.size();}
const int MAXN=1e6+1;
vector<vector<int>> arr;
pii loc[MAXN];
int xc[4]={1,-1,0,0},yc[4]={0,0,1,-1};
int h,w,maxv;
struct seg{
struct node{
pii data;
int lazy;
node(){
data={0,0},lazy=0;
}
}t[2*MAXN];
pii pu(pii a, pii b){
if(a.first<b.first)return a;
if(b.first<a.first)return b;
return {a.first,a.second+b.second};
}
void mt(int ind, int le, int ri){
t[ind].data.second=ri-le+1;
int mid=le+(ri-le)/2;
int left=ind+1,right=ind+(mid-le+1)*2;
if(le!=ri)mt(left,le,mid),mt(right,mid+1,ri);
}
void rl(int ind, int le, int ri){
t[ind].data.first+=t[ind].lazy;
if(le!=ri){
int mid=le+(ri-le)/2;
int left=ind+1,right=ind+(mid-le+1)*2;
t[left].lazy+=t[ind].lazy;
t[right].lazy+=t[ind].lazy;
}
t[ind].lazy=0;
}
void update(int ind, int le, int ri, int l, int r, int val){
rl(ind,le,ri);
if(le>r||ri<l)return;
if(le>=l&&ri<=r){
t[ind].lazy=val;
rl(ind,le,ri);
return;
}
int mid=le+(ri-le)/2;
int left=ind+1,right=ind+(mid-le+1)*2;
update(left,le,mid,l,r,val),update(right,mid+1,ri,l,r,val);
t[ind].data=pu(t[left].data,t[right].data);
}
}tree;
bool inbounds(pii a){
return (a.first>=0&&a.second>=0&&a.first<h&&a.second<w);
}
void update(pii a, int val){
pii rn={arr[a.first][a.second],maxv};
if(inbounds({a.first-1,a.second}))rn.second=min(rn.second,arr[a.first-1][a.second]-1);
if(inbounds({a.first,a.second-1}))rn.second=min(rn.second,arr[a.first][a.second-1]-1);
if(rn.first<=rn.second)tree.update(0,0,maxv,rn.first,rn.second,val);
rn={0,arr[a.first][a.second]-1};
vector<int> te;
for(int i=0;i<4;i++){
pii ne={a.first+xc[i],a.second+yc[i]};
if(inbounds(ne))te.push_back(arr[ne.first][ne.second]);
}
sort(te.begin(),te.end());
if(sz(te)>=2){
rn.first=te[1];
if(rn.first<=rn.second)tree.update(0,0,maxv,rn.first,rn.second,val);
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h=H,w=W;
maxv=h*w-1;
arr.resize(h);
tree.mt(0,0,maxv);
for(int i=0;i<h;i++)arr[i].resize(w);
for(int i=0;i<h*w;i++){
loc[i]={R[i],C[i]};
arr[R[i]][C[i]]=i;
}
for(int i=0;i<h;i++)for(int j=0;j<w;j++)update({i,j},1);
}
int swap_seats(int a, int b){
set<pii> toupdate;
toupdate.insert(loc[a]),toupdate.insert(loc[b]);
for(int i=0;i<4;i++){
pii ne={loc[a].first+xc[i],loc[a].second+yc[i]};
if(inbounds(ne))toupdate.insert(ne);
ne={loc[b].first+xc[i],loc[b].second+yc[i]};
if(inbounds(ne))toupdate.insert(ne);
}
for(auto x:toupdate)update(x,-1);
swap(arr[loc[a].first][loc[a].second],arr[loc[b].first][loc[b].second]);
swap(loc[a],loc[b]);
for(auto x:toupdate)update(x,1);
assert(tree.t[0].data.first==1);
return tree.t[0].data.second;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
23936 KB |
Output is correct |
2 |
Correct |
43 ms |
23936 KB |
Output is correct |
3 |
Correct |
55 ms |
24060 KB |
Output is correct |
4 |
Correct |
36 ms |
24056 KB |
Output is correct |
5 |
Correct |
27 ms |
24056 KB |
Output is correct |
6 |
Correct |
49 ms |
23936 KB |
Output is correct |
7 |
Correct |
53 ms |
24056 KB |
Output is correct |
8 |
Correct |
48 ms |
24056 KB |
Output is correct |
9 |
Correct |
47 ms |
24056 KB |
Output is correct |
10 |
Correct |
52 ms |
24056 KB |
Output is correct |
11 |
Correct |
50 ms |
23936 KB |
Output is correct |
12 |
Correct |
34 ms |
24012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
23936 KB |
Output is correct |
2 |
Correct |
43 ms |
23936 KB |
Output is correct |
3 |
Correct |
55 ms |
24060 KB |
Output is correct |
4 |
Correct |
36 ms |
24056 KB |
Output is correct |
5 |
Correct |
27 ms |
24056 KB |
Output is correct |
6 |
Correct |
49 ms |
23936 KB |
Output is correct |
7 |
Correct |
53 ms |
24056 KB |
Output is correct |
8 |
Correct |
48 ms |
24056 KB |
Output is correct |
9 |
Correct |
47 ms |
24056 KB |
Output is correct |
10 |
Correct |
52 ms |
24056 KB |
Output is correct |
11 |
Correct |
50 ms |
23936 KB |
Output is correct |
12 |
Correct |
34 ms |
24012 KB |
Output is correct |
13 |
Correct |
80 ms |
24348 KB |
Output is correct |
14 |
Correct |
89 ms |
24320 KB |
Output is correct |
15 |
Correct |
61 ms |
24320 KB |
Output is correct |
16 |
Correct |
36 ms |
24824 KB |
Output is correct |
17 |
Correct |
75 ms |
24320 KB |
Output is correct |
18 |
Correct |
72 ms |
24440 KB |
Output is correct |
19 |
Correct |
67 ms |
24320 KB |
Output is correct |
20 |
Correct |
63 ms |
24576 KB |
Output is correct |
21 |
Correct |
52 ms |
24320 KB |
Output is correct |
22 |
Correct |
48 ms |
24860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1735 ms |
51448 KB |
Output is correct |
2 |
Correct |
922 ms |
51320 KB |
Output is correct |
3 |
Correct |
1170 ms |
67512 KB |
Output is correct |
4 |
Correct |
757 ms |
67424 KB |
Output is correct |
5 |
Correct |
851 ms |
67320 KB |
Output is correct |
6 |
Correct |
1242 ms |
67320 KB |
Output is correct |
7 |
Correct |
1142 ms |
67320 KB |
Output is correct |
8 |
Correct |
1004 ms |
67448 KB |
Output is correct |
9 |
Correct |
1016 ms |
67552 KB |
Output is correct |
10 |
Correct |
865 ms |
67304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
24184 KB |
Output is correct |
2 |
Correct |
155 ms |
26360 KB |
Output is correct |
3 |
Correct |
934 ms |
67448 KB |
Output is correct |
4 |
Correct |
1679 ms |
67320 KB |
Output is correct |
5 |
Correct |
817 ms |
67448 KB |
Output is correct |
6 |
Correct |
1609 ms |
118332 KB |
Output is correct |
7 |
Correct |
840 ms |
67308 KB |
Output is correct |
8 |
Correct |
1242 ms |
67300 KB |
Output is correct |
9 |
Correct |
1008 ms |
67808 KB |
Output is correct |
10 |
Correct |
894 ms |
70480 KB |
Output is correct |
11 |
Correct |
863 ms |
90872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
25628 KB |
Output is correct |
2 |
Correct |
157 ms |
25588 KB |
Output is correct |
3 |
Correct |
229 ms |
25664 KB |
Output is correct |
4 |
Correct |
268 ms |
25588 KB |
Output is correct |
5 |
Correct |
374 ms |
25952 KB |
Output is correct |
6 |
Correct |
1248 ms |
68316 KB |
Output is correct |
7 |
Correct |
1356 ms |
68288 KB |
Output is correct |
8 |
Correct |
1220 ms |
68220 KB |
Output is correct |
9 |
Correct |
1998 ms |
68344 KB |
Output is correct |
10 |
Correct |
1172 ms |
68268 KB |
Output is correct |
11 |
Correct |
1165 ms |
68344 KB |
Output is correct |
12 |
Correct |
746 ms |
68472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
23936 KB |
Output is correct |
2 |
Correct |
43 ms |
23936 KB |
Output is correct |
3 |
Correct |
55 ms |
24060 KB |
Output is correct |
4 |
Correct |
36 ms |
24056 KB |
Output is correct |
5 |
Correct |
27 ms |
24056 KB |
Output is correct |
6 |
Correct |
49 ms |
23936 KB |
Output is correct |
7 |
Correct |
53 ms |
24056 KB |
Output is correct |
8 |
Correct |
48 ms |
24056 KB |
Output is correct |
9 |
Correct |
47 ms |
24056 KB |
Output is correct |
10 |
Correct |
52 ms |
24056 KB |
Output is correct |
11 |
Correct |
50 ms |
23936 KB |
Output is correct |
12 |
Correct |
34 ms |
24012 KB |
Output is correct |
13 |
Correct |
80 ms |
24348 KB |
Output is correct |
14 |
Correct |
89 ms |
24320 KB |
Output is correct |
15 |
Correct |
61 ms |
24320 KB |
Output is correct |
16 |
Correct |
36 ms |
24824 KB |
Output is correct |
17 |
Correct |
75 ms |
24320 KB |
Output is correct |
18 |
Correct |
72 ms |
24440 KB |
Output is correct |
19 |
Correct |
67 ms |
24320 KB |
Output is correct |
20 |
Correct |
63 ms |
24576 KB |
Output is correct |
21 |
Correct |
52 ms |
24320 KB |
Output is correct |
22 |
Correct |
48 ms |
24860 KB |
Output is correct |
23 |
Correct |
1735 ms |
51448 KB |
Output is correct |
24 |
Correct |
922 ms |
51320 KB |
Output is correct |
25 |
Correct |
1170 ms |
67512 KB |
Output is correct |
26 |
Correct |
757 ms |
67424 KB |
Output is correct |
27 |
Correct |
851 ms |
67320 KB |
Output is correct |
28 |
Correct |
1242 ms |
67320 KB |
Output is correct |
29 |
Correct |
1142 ms |
67320 KB |
Output is correct |
30 |
Correct |
1004 ms |
67448 KB |
Output is correct |
31 |
Correct |
1016 ms |
67552 KB |
Output is correct |
32 |
Correct |
865 ms |
67304 KB |
Output is correct |
33 |
Correct |
79 ms |
24184 KB |
Output is correct |
34 |
Correct |
155 ms |
26360 KB |
Output is correct |
35 |
Correct |
934 ms |
67448 KB |
Output is correct |
36 |
Correct |
1679 ms |
67320 KB |
Output is correct |
37 |
Correct |
817 ms |
67448 KB |
Output is correct |
38 |
Correct |
1609 ms |
118332 KB |
Output is correct |
39 |
Correct |
840 ms |
67308 KB |
Output is correct |
40 |
Correct |
1242 ms |
67300 KB |
Output is correct |
41 |
Correct |
1008 ms |
67808 KB |
Output is correct |
42 |
Correct |
894 ms |
70480 KB |
Output is correct |
43 |
Correct |
863 ms |
90872 KB |
Output is correct |
44 |
Correct |
87 ms |
25628 KB |
Output is correct |
45 |
Correct |
157 ms |
25588 KB |
Output is correct |
46 |
Correct |
229 ms |
25664 KB |
Output is correct |
47 |
Correct |
268 ms |
25588 KB |
Output is correct |
48 |
Correct |
374 ms |
25952 KB |
Output is correct |
49 |
Correct |
1248 ms |
68316 KB |
Output is correct |
50 |
Correct |
1356 ms |
68288 KB |
Output is correct |
51 |
Correct |
1220 ms |
68220 KB |
Output is correct |
52 |
Correct |
1998 ms |
68344 KB |
Output is correct |
53 |
Correct |
1172 ms |
68268 KB |
Output is correct |
54 |
Correct |
1165 ms |
68344 KB |
Output is correct |
55 |
Correct |
746 ms |
68472 KB |
Output is correct |
56 |
Correct |
226 ms |
25512 KB |
Output is correct |
57 |
Correct |
485 ms |
25588 KB |
Output is correct |
58 |
Correct |
540 ms |
25912 KB |
Output is correct |
59 |
Correct |
2059 ms |
68300 KB |
Output is correct |
60 |
Correct |
2745 ms |
68300 KB |
Output is correct |
61 |
Correct |
1362 ms |
68576 KB |
Output is correct |
62 |
Correct |
1412 ms |
68296 KB |
Output is correct |
63 |
Correct |
2663 ms |
68204 KB |
Output is correct |
64 |
Correct |
1802 ms |
68304 KB |
Output is correct |
65 |
Correct |
1794 ms |
68312 KB |
Output is correct |
66 |
Correct |
1973 ms |
68728 KB |
Output is correct |
67 |
Correct |
1617 ms |
71492 KB |
Output is correct |
68 |
Correct |
1367 ms |
82652 KB |
Output is correct |
69 |
Correct |
2582 ms |
91692 KB |
Output is correct |