Submission #608339

#	Time	Username	Problem	Language	Result	Execution time	Memory
608339		rrrr10000	Seats (IOI18_seats)	C++14	37 / 100	4059 ms	118056 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#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 pb emplace_back
#define fi first
#define se second
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> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;

vp v;
ll n,h,w;
vvi grid;
vi tate,yoko;
vvi rui;
ll sum;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h=H;w=W;n=H*W;
    rep(i,n)v.pb(R[i],C[i]);
    if(h>10000||w>10000){
        rui=vvi(n,vi(4));
        rep(i,n)rui[i]={v[i].fi,v[i].fi,v[i].se,v[i].se};
        rep(i,n-1){
            chmin(rui[i+1][0],rui[i][0]);
            chmin(rui[i+1][2],rui[i][2]);
            chmax(rui[i+1][1],rui[i][1]);
            chmax(rui[i+1][3],rui[i][3]);
        }
        sum=0;
        rep(i,n)if((rui[i][1]-rui[i][0]+1)*(rui[i][3]-rui[i][2]+1)==i+1)sum++;
        return;
    }
    grid=vvi(h,vi(w));
    rep(i,n)grid[v[i].fi][v[i].se]=i;
    tate=vi(w,inf);
    yoko=vi(h,inf);
    rep(i,h)rep(j,w){
        chmin(tate[j],grid[i][j]);
        chmin(yoko[i],grid[i][j]);
    }
}

int swap_seats(int a, int b) {
    swap(v[a],v[b]);
    if(h>10000||w>10000){
        if(a>b)swap(a,b);
        REP(i,a,b)if((rui[i][1]-rui[i][0]+1)*(rui[i][3]-rui[i][2]+1)==i+1)sum--;
        REP(i,a,b+1)rui[i]={v[i].fi,v[i].fi,v[i].se,v[i].se};
        REP(i,max(0,a-1),b){
            chmin(rui[i+1][0],rui[i][0]);
            chmin(rui[i+1][2],rui[i][2]);
            chmax(rui[i+1][1],rui[i][1]);
            chmax(rui[i+1][3],rui[i][3]);
        }
        REP(i,a,b)if((rui[i][1]-rui[i][0]+1)*(rui[i][3]-rui[i][2]+1)==i+1)sum++;
        return sum;
    }
    swap(grid[v[a].fi][v[a].se],grid[v[b].fi][v[b].se]);
    tate[v[a].se]=tate[v[b].se]=inf;
    yoko[v[a].fi]=yoko[v[b].fi]=inf;
    rep(i,h){
        chmin(tate[v[a].se],grid[i][v[a].se]);
        chmin(tate[v[b].se],grid[i][v[b].se]);
    }
    rep(i,w){
        chmin(yoko[v[a].fi],grid[v[a].fi][i]);
        chmin(yoko[v[b].fi],grid[v[b].fi][i]);
    }
    vi tl=tate,tr=tate,yu=yoko,yd=yoko;
    rep(i,w-1)chmin(tl[i+1],tl[i]);
    for(int i=w-1;i>0;i--)chmin(tr[i-1],tr[i]);
    rep(i,h-1)chmin(yu[i+1],yu[i]);
    for(int i=h-1;i>0;i--)chmin(yd[i-1],yd[i]);
    int ans=1;
    vi cur={v[0].se,v[0].se,v[0].fi,v[0].fi};
    while(true){
        ll s=(cur[1]-cur[0]+1)*(cur[3]-cur[2]+1);
        if(s==n)break;
        ll mi=inf,t;
        if(cur[0]>0&&chmin(mi,tl[cur[0]-1]))t=0;
        if(cur[1]<w-1&&chmin(mi,tr[cur[1]+1]))t=1;
        if(cur[2]>0&&chmin(mi,yu[cur[2]-1]))t=2;
        if(cur[3]<h-1&&chmin(mi,yd[cur[3]+1]))t=3;
        if(mi==s)ans++;
        if(t==0)cur[0]--;
        if(t==1)cur[1]++;
        if(t==2)cur[2]--;
        if(t==3)cur[3]++;
    }
    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:100:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |         if(t==2)cur[2]--;
      |         ^~

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