Submission #138753

#	Time	Username	Problem	Language	Result	Execution time	Memory
138753		ckodser	Seats (IOI18_seats)	C++14	11 / 100	4101 ms	56860 KiB

seats

#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=1e6+500;
const ll inf=1e9+900;

bool sub3;

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));
}
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]);
}
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];

ll imp[maxn*5];
ll cntimp;
void get(ll b,ll w){
    ll s=a[b][0];
    for(ll i=s;i<=w;i++){
	imp[cntimp++]=(nxtmx(b,0,n,1,i)-1);
    }
    for(ll i=0;i<=s;i++){
	imp[cntimp++]=(nxtmn(b,0,n,1,i)-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(){
    if(sub3){
	cntimp=0;
	get(0,hh);
	get(1,ww);
	imp[cntimp++]=0;
	imp[cntimp++]=n-1;

	sort(imp,imp+cntimp);
	cntimp=(unique(imp,imp+cntimp)-imp);
    }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;
    }
    ll ans=0;
    for(ll i=0;i<cntimp;i++){
	ll v=imp[i];
	if(0<=v && v<n)
	ans+=isGood(v);
    }
    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);
    }
    if(H<=1000 && W<=1000)sub3=1;
    ww=W;
    hh=H;
    n=W*H;
    a[0]=R;
    a[1]=C;
    if(sub3){
	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();
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30