# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
711746 |
2023-03-17T11:58:07 Z |
rrrr10000 |
Seats (IOI18_seats) |
C++14 |
|
3739 ms |
97548 KB |
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
struct segtree{
vp seg;
vi lazy;
P f(P a,P b){
if(a.fi==b.fi)return P(a.fi,a.se+b.se);
return min(a,b);
}
ll N=1;
void init(ll n){
while(N<n)N*=2;
seg=vp(N*2);
lazy=vi(N*2);
rep(i,N)seg[i+N]=P(0,1);
for(ll i=N-1;i>0;i--)seg[i]=f(seg[i*2],seg[i*2+1]);
}
void eval(ll k,ll l,ll r){
if(lazy[k]==0)return;
seg[k].fi+=lazy[k];
if(r-l>1)rep(t,2)lazy[k*2+t]+=lazy[k];
lazy[k]=0;
}
void add(ll x,ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=N;
if(a<=l&&r<=b){
lazy[k]+=x;
eval(k,l,r);
return;
}
eval(k,l,r);
if(r<=a||b<=l)return;
add(x,a,b,k*2,l,(l+r)/2);
add(x,a,b,k*2+1,(l+r)/2,r);
seg[k]=f(seg[k*2],seg[k*2+1]);
}
P get(ll a,ll b,ll k=1,ll l=0,ll r=-1){
if(r==-1)r=N;
eval(k,l,r);
if(a<=l&&r<=b)return seg[k];
if(r<=a||b<=l)return P(inf,1);
return f(get(a,b,k*2,l,(l+r)/2),get(a,b,k*2+1,(l+r)/2,r));
}
};
vi g;
ll h,w;
vi v;
segtree seg;
void upd(ll i,ll c){
vi srt;
rep(ti,2)rep(tj,2)srt.pb(g[i+ti*w+tj]);
sort(all(srt));
seg.add(c,srt[0],srt[1]);
seg.add(c,srt[2],srt[3]);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
h=H+2;w=W+2;
g=vi(h*w,H*W);
rep(i,H*W)g[(R[i]+1)*w+(C[i]+1)]=i;
rep(i,H*W)v.pb((R[i]+1)*w+(C[i]+1));
seg.init(H*W);
rep(i,H+1)rep(j,W+1)upd(i*w+j,1);
}
int swap_seats(int a, int b){
vi al;
rep(i,2)rep(j,2){
al.pb(v[a]-i*w-j);
al.pb(v[b]-i*w-j);
}
dupli(al);
for(auto x:al)upd(x,-1);
swap(g[v[a]],g[v[b]]);
swap(v[a],v[b]);
for(auto x:al)upd(x,1);
return seg.get(0,(h-2)*(w-2)).se;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
460 KB |
Output is correct |
2 |
Correct |
32 ms |
396 KB |
Output is correct |
3 |
Correct |
43 ms |
360 KB |
Output is correct |
4 |
Correct |
34 ms |
460 KB |
Output is correct |
5 |
Correct |
29 ms |
384 KB |
Output is correct |
6 |
Correct |
39 ms |
340 KB |
Output is correct |
7 |
Correct |
42 ms |
376 KB |
Output is correct |
8 |
Correct |
37 ms |
340 KB |
Output is correct |
9 |
Correct |
35 ms |
428 KB |
Output is correct |
10 |
Correct |
43 ms |
376 KB |
Output is correct |
11 |
Correct |
39 ms |
460 KB |
Output is correct |
12 |
Correct |
31 ms |
388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
460 KB |
Output is correct |
2 |
Correct |
32 ms |
396 KB |
Output is correct |
3 |
Correct |
43 ms |
360 KB |
Output is correct |
4 |
Correct |
34 ms |
460 KB |
Output is correct |
5 |
Correct |
29 ms |
384 KB |
Output is correct |
6 |
Correct |
39 ms |
340 KB |
Output is correct |
7 |
Correct |
42 ms |
376 KB |
Output is correct |
8 |
Correct |
37 ms |
340 KB |
Output is correct |
9 |
Correct |
35 ms |
428 KB |
Output is correct |
10 |
Correct |
43 ms |
376 KB |
Output is correct |
11 |
Correct |
39 ms |
460 KB |
Output is correct |
12 |
Correct |
31 ms |
388 KB |
Output is correct |
13 |
Correct |
86 ms |
1588 KB |
Output is correct |
14 |
Correct |
105 ms |
1592 KB |
Output is correct |
15 |
Correct |
75 ms |
1760 KB |
Output is correct |
16 |
Correct |
61 ms |
1840 KB |
Output is correct |
17 |
Correct |
78 ms |
1680 KB |
Output is correct |
18 |
Correct |
69 ms |
1624 KB |
Output is correct |
19 |
Correct |
67 ms |
1596 KB |
Output is correct |
20 |
Correct |
63 ms |
1620 KB |
Output is correct |
21 |
Correct |
60 ms |
1748 KB |
Output is correct |
22 |
Correct |
60 ms |
1748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2312 ms |
81348 KB |
Output is correct |
2 |
Correct |
1242 ms |
81504 KB |
Output is correct |
3 |
Correct |
1194 ms |
81332 KB |
Output is correct |
4 |
Correct |
1008 ms |
81332 KB |
Output is correct |
5 |
Correct |
1106 ms |
81348 KB |
Output is correct |
6 |
Correct |
1058 ms |
81452 KB |
Output is correct |
7 |
Correct |
1084 ms |
81448 KB |
Output is correct |
8 |
Correct |
1195 ms |
81532 KB |
Output is correct |
9 |
Correct |
1145 ms |
81504 KB |
Output is correct |
10 |
Correct |
1093 ms |
81520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
1720 KB |
Output is correct |
2 |
Correct |
185 ms |
9756 KB |
Output is correct |
3 |
Correct |
1060 ms |
81420 KB |
Output is correct |
4 |
Correct |
2330 ms |
81504 KB |
Output is correct |
5 |
Correct |
1475 ms |
97156 KB |
Output is correct |
6 |
Correct |
2657 ms |
97092 KB |
Output is correct |
7 |
Correct |
1268 ms |
86712 KB |
Output is correct |
8 |
Correct |
1215 ms |
81640 KB |
Output is correct |
9 |
Correct |
1161 ms |
81672 KB |
Output is correct |
10 |
Correct |
1163 ms |
83080 KB |
Output is correct |
11 |
Correct |
1282 ms |
89392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
1476 KB |
Output is correct |
2 |
Correct |
211 ms |
1452 KB |
Output is correct |
3 |
Correct |
291 ms |
1492 KB |
Output is correct |
4 |
Correct |
376 ms |
1544 KB |
Output is correct |
5 |
Correct |
580 ms |
2692 KB |
Output is correct |
6 |
Correct |
2195 ms |
97400 KB |
Output is correct |
7 |
Correct |
2407 ms |
97388 KB |
Output is correct |
8 |
Correct |
2113 ms |
97216 KB |
Output is correct |
9 |
Correct |
3645 ms |
97356 KB |
Output is correct |
10 |
Correct |
2124 ms |
97284 KB |
Output is correct |
11 |
Correct |
2107 ms |
97548 KB |
Output is correct |
12 |
Correct |
2053 ms |
97372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
460 KB |
Output is correct |
2 |
Correct |
32 ms |
396 KB |
Output is correct |
3 |
Correct |
43 ms |
360 KB |
Output is correct |
4 |
Correct |
34 ms |
460 KB |
Output is correct |
5 |
Correct |
29 ms |
384 KB |
Output is correct |
6 |
Correct |
39 ms |
340 KB |
Output is correct |
7 |
Correct |
42 ms |
376 KB |
Output is correct |
8 |
Correct |
37 ms |
340 KB |
Output is correct |
9 |
Correct |
35 ms |
428 KB |
Output is correct |
10 |
Correct |
43 ms |
376 KB |
Output is correct |
11 |
Correct |
39 ms |
460 KB |
Output is correct |
12 |
Correct |
31 ms |
388 KB |
Output is correct |
13 |
Correct |
86 ms |
1588 KB |
Output is correct |
14 |
Correct |
105 ms |
1592 KB |
Output is correct |
15 |
Correct |
75 ms |
1760 KB |
Output is correct |
16 |
Correct |
61 ms |
1840 KB |
Output is correct |
17 |
Correct |
78 ms |
1680 KB |
Output is correct |
18 |
Correct |
69 ms |
1624 KB |
Output is correct |
19 |
Correct |
67 ms |
1596 KB |
Output is correct |
20 |
Correct |
63 ms |
1620 KB |
Output is correct |
21 |
Correct |
60 ms |
1748 KB |
Output is correct |
22 |
Correct |
60 ms |
1748 KB |
Output is correct |
23 |
Correct |
2312 ms |
81348 KB |
Output is correct |
24 |
Correct |
1242 ms |
81504 KB |
Output is correct |
25 |
Correct |
1194 ms |
81332 KB |
Output is correct |
26 |
Correct |
1008 ms |
81332 KB |
Output is correct |
27 |
Correct |
1106 ms |
81348 KB |
Output is correct |
28 |
Correct |
1058 ms |
81452 KB |
Output is correct |
29 |
Correct |
1084 ms |
81448 KB |
Output is correct |
30 |
Correct |
1195 ms |
81532 KB |
Output is correct |
31 |
Correct |
1145 ms |
81504 KB |
Output is correct |
32 |
Correct |
1093 ms |
81520 KB |
Output is correct |
33 |
Correct |
83 ms |
1720 KB |
Output is correct |
34 |
Correct |
185 ms |
9756 KB |
Output is correct |
35 |
Correct |
1060 ms |
81420 KB |
Output is correct |
36 |
Correct |
2330 ms |
81504 KB |
Output is correct |
37 |
Correct |
1475 ms |
97156 KB |
Output is correct |
38 |
Correct |
2657 ms |
97092 KB |
Output is correct |
39 |
Correct |
1268 ms |
86712 KB |
Output is correct |
40 |
Correct |
1215 ms |
81640 KB |
Output is correct |
41 |
Correct |
1161 ms |
81672 KB |
Output is correct |
42 |
Correct |
1163 ms |
83080 KB |
Output is correct |
43 |
Correct |
1282 ms |
89392 KB |
Output is correct |
44 |
Correct |
156 ms |
1476 KB |
Output is correct |
45 |
Correct |
211 ms |
1452 KB |
Output is correct |
46 |
Correct |
291 ms |
1492 KB |
Output is correct |
47 |
Correct |
376 ms |
1544 KB |
Output is correct |
48 |
Correct |
580 ms |
2692 KB |
Output is correct |
49 |
Correct |
2195 ms |
97400 KB |
Output is correct |
50 |
Correct |
2407 ms |
97388 KB |
Output is correct |
51 |
Correct |
2113 ms |
97216 KB |
Output is correct |
52 |
Correct |
3645 ms |
97356 KB |
Output is correct |
53 |
Correct |
2124 ms |
97284 KB |
Output is correct |
54 |
Correct |
2107 ms |
97548 KB |
Output is correct |
55 |
Correct |
2053 ms |
97372 KB |
Output is correct |
56 |
Correct |
216 ms |
1908 KB |
Output is correct |
57 |
Correct |
417 ms |
2040 KB |
Output is correct |
58 |
Correct |
635 ms |
3304 KB |
Output is correct |
59 |
Correct |
2070 ms |
84236 KB |
Output is correct |
60 |
Correct |
3623 ms |
84240 KB |
Output is correct |
61 |
Correct |
1899 ms |
84220 KB |
Output is correct |
62 |
Correct |
1938 ms |
91960 KB |
Output is correct |
63 |
Correct |
3739 ms |
89356 KB |
Output is correct |
64 |
Correct |
2270 ms |
85784 KB |
Output is correct |
65 |
Correct |
1974 ms |
84360 KB |
Output is correct |
66 |
Correct |
2113 ms |
84384 KB |
Output is correct |
67 |
Correct |
2136 ms |
85424 KB |
Output is correct |
68 |
Correct |
1992 ms |
88236 KB |
Output is correct |
69 |
Correct |
3480 ms |
89900 KB |
Output is correct |