# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
138726 |
2019-07-30T09:13:47 Z |
ckodser |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
48440 KB |
#include "seats.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=1e5+500;
const ll inf=1e9+900;
ll mn[2][maxn*4];
ll mx[2][maxn*4];
ll n;
pii findM(ll b,ll L,ll R,ll node,ll l,ll r){
if(l<=L && R<=r){
return mp(mn[b][node],mx[b][node]);
}
if(R<=l || r<=L){
return mp(inf,0);
}
ll mid=(L+R)/2;
pii w1=findM(b,L,mid,2*node,l,r);
pii w2=findM(b,mid,R,2*node+1,l,r);
return mp(min(w1.F,w2.F),max(w1.S,w2.S));
}
ll nxtmn(ll b,ll L,ll R,ll node,ll v){// akharin jaee ke mn>v
if(L+1==R){
if(mn[b][node]>v)return R;
return L;
}
ll mid=(L+R)/2;
if(mn[b][2*node]>v)return nxtmn(b,mid,R,2*node+1,v);
else return nxtmn(b,L,mid,2*node ,v);
}
ll nxtmx(ll b,ll L,ll R,ll node,ll v){// akharin jaee ke mx<v
if(L+1==R){
if(mx[b][node]<v)return R;
return L;
}
ll mid=(L+R)/2;
if(mx[b][2*node]<v)return nxtmx(b,mid,R,2*node+1,v);
else return nxtmx(b,L,mid,2*node ,v);
}
vector<ll> a[2];
vector<ll> get(ll b,ll w){
vector<ll> ans;
for(ll i=0;i<=w;i++){
ans.pb(nxtmn(b,0,n,1,i)-1);
ans.pb(nxtmx(b,0,n,1,i)-1);
}
return ans;
}
void update(ll b,ll l,ll r,ll node,ll x,ll v){
if(l+1==r){
mx[b][node]=v;
mn[b][node]=v;
return;
}
ll mid=(l+r)/2;
if(x<mid)
update(b,l,mid,2*node ,x,v);
else
update(b,mid,r,2*node+1,x,v);
mn[b][node]=min(mn[b][2*node],mn[b][2*node+1]);
mx[b][node]=max(mx[b][2*node],mx[b][2*node+1]);
}
bool isGood(ll x){
pii w1=findM(0,0,n,1,0,x+1);
pii w2=findM(1,0,n,1,0,x+1);
ll r1=w1.S-w1.F+1;
ll r2=w2.S-w2.F+1;
return (r1*r2==x+1);
}
void bild(ll b,ll l,ll r,ll node){
for(ll i=0;i<n;i++){
update(b,l,r,node,i,a[b][i]);
}
}
ll ww,hh;
int findANS(){
vector<ll> imp;
if(ww+hh<2100){
imp.pb(0);
imp.pb(n-1);
vector<ll> v1=get(0,hh);
vector<ll> v2=get(1,ww);
for(auto x:v1)imp.pb(x);
for(auto x:v2)imp.pb(x);
}else{
ll ans=0;
pii w0=mp(inf,0);
pii w1=mp(inf,0);
for(ll i=0;i<n;i++){
w0.F=min(w0.F,a[0][i]);
w0.S=max(w0.S,a[0][i]);
w1.F=min(w1.F,a[1][i]);
w1.S=max(w1.S,a[1][i]);
ll r0=w0.S-w0.F+1;
ll r1=w1.S-w1.F+1;
ans+=(r0*r1==i+1);
}
return ans;
}
sort(imp.begin(),imp.end());
imp.resize(unique(imp.begin(),imp.end())-imp.begin());
ll ans=0;
for(auto x:imp){
ans+=isGood(x);
}
return ans;
}
void give_initial_chart(int H, int W,vector<int> R,vector<int> C) {
if(H>W){
swap(H,W);
swap(R,C);
}
ww=W;
hh=H;
n=W*H;
a[0]=R;
a[1]=C;
bild(0,0,n,1);
bild(1,0,n,1);
}
int swap_seats(int A, int B){
ll ra=a[0][A];
ll rb=a[0][B];
ll ca=a[1][A];
ll cb=a[1][B];
swap(a[0][A],a[0][B]);
swap(a[1][A],a[1][B]);
update(0,0,n,1,A,rb);
update(0,0,n,1,B,ra);
update(1,0,n,1,A,cb);
update(1,0,n,1,B,ca);
return findANS();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
15 ms |
504 KB |
Output is correct |
3 |
Correct |
21 ms |
504 KB |
Output is correct |
4 |
Correct |
50 ms |
480 KB |
Output is correct |
5 |
Correct |
102 ms |
504 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
27 ms |
504 KB |
Output is correct |
8 |
Correct |
23 ms |
504 KB |
Output is correct |
9 |
Correct |
24 ms |
504 KB |
Output is correct |
10 |
Correct |
27 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
528 KB |
Output is correct |
12 |
Correct |
74 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
15 ms |
504 KB |
Output is correct |
3 |
Correct |
21 ms |
504 KB |
Output is correct |
4 |
Correct |
50 ms |
480 KB |
Output is correct |
5 |
Correct |
102 ms |
504 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
27 ms |
504 KB |
Output is correct |
8 |
Correct |
23 ms |
504 KB |
Output is correct |
9 |
Correct |
24 ms |
504 KB |
Output is correct |
10 |
Correct |
27 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
528 KB |
Output is correct |
12 |
Correct |
74 ms |
504 KB |
Output is correct |
13 |
Correct |
128 ms |
1244 KB |
Output is correct |
14 |
Correct |
121 ms |
1168 KB |
Output is correct |
15 |
Correct |
162 ms |
1168 KB |
Output is correct |
16 |
Correct |
160 ms |
1272 KB |
Output is correct |
17 |
Correct |
161 ms |
1400 KB |
Output is correct |
18 |
Correct |
1958 ms |
1344 KB |
Output is correct |
19 |
Correct |
1918 ms |
1336 KB |
Output is correct |
20 |
Correct |
162 ms |
1404 KB |
Output is correct |
21 |
Correct |
160 ms |
1340 KB |
Output is correct |
22 |
Correct |
160 ms |
1348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
341 ms |
48272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
127 ms |
1208 KB |
Output is correct |
2 |
Correct |
822 ms |
6616 KB |
Output is correct |
3 |
Runtime error |
343 ms |
48440 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
1408 KB |
Output is correct |
2 |
Correct |
122 ms |
1616 KB |
Output is correct |
3 |
Correct |
720 ms |
1352 KB |
Output is correct |
4 |
Execution timed out |
4018 ms |
1320 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
504 KB |
Output is correct |
2 |
Correct |
15 ms |
504 KB |
Output is correct |
3 |
Correct |
21 ms |
504 KB |
Output is correct |
4 |
Correct |
50 ms |
480 KB |
Output is correct |
5 |
Correct |
102 ms |
504 KB |
Output is correct |
6 |
Correct |
32 ms |
504 KB |
Output is correct |
7 |
Correct |
27 ms |
504 KB |
Output is correct |
8 |
Correct |
23 ms |
504 KB |
Output is correct |
9 |
Correct |
24 ms |
504 KB |
Output is correct |
10 |
Correct |
27 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
528 KB |
Output is correct |
12 |
Correct |
74 ms |
504 KB |
Output is correct |
13 |
Correct |
128 ms |
1244 KB |
Output is correct |
14 |
Correct |
121 ms |
1168 KB |
Output is correct |
15 |
Correct |
162 ms |
1168 KB |
Output is correct |
16 |
Correct |
160 ms |
1272 KB |
Output is correct |
17 |
Correct |
161 ms |
1400 KB |
Output is correct |
18 |
Correct |
1958 ms |
1344 KB |
Output is correct |
19 |
Correct |
1918 ms |
1336 KB |
Output is correct |
20 |
Correct |
162 ms |
1404 KB |
Output is correct |
21 |
Correct |
160 ms |
1340 KB |
Output is correct |
22 |
Correct |
160 ms |
1348 KB |
Output is correct |
23 |
Runtime error |
341 ms |
48272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
24 |
Halted |
0 ms |
0 KB |
- |