Submission #711722

#	Time	Username	Problem	Language	Result	Execution time	Memory
711722		rrrr10000	Seats (IOI18_seats)	C++14	37 / 100	4061 ms	151788 KiB

seats

#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){
        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;
        eval(k,l,r);
        if(a<=l&&r<=b){
            lazy[k]+=x;
            eval(k,l,r);
            return;
        }
        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));
    }
};

vvi g;
ll h,w;
vp v;
segtree seg;
void upd(ll i,ll j,ll c){
    vi srt;
    rep(ti,2)rep(tj,2)srt.pb(g[i+ti][j+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;w=W;
    g=vvi(h+2,vi(w+2,h*w));
    rep(i,h*w)g[R[i]+1][C[i]+1]=i;
    rep(i,h*w)v.pb(R[i]+1,C[i]+1);
    seg.init(h*w);
    rep(i,h+1)rep(j,w+1)upd(i,j,1);
}
int swap_seats(int a, int b){
    vp al;
    rep(i,2)rep(j,2){
        al.pb(v[a].fi-i,v[a].se-j);
        al.pb(v[b].fi-i,v[b].se-j);
    }
    dupli(al);
    for(auto x:al)upd(x.fi,x.se,-1);
    swap(g[v[a].fi][v[a].se],g[v[b].fi][v[b].se]);
    swap(v[a],v[b]);
    for(auto x:al)upd(x.fi,x.se,1);
    return seg.get(0,h*w).se;
}

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