제출 #800342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800342		gagik_2007	자리 배치 (IOI18_seats)	C++17	37 / 100	4083 ms	86460 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
ll n,m,k;
vector<int>r,c;
ll sum=0;
vector<int>corr;
vector<int>ci1,ci2,cj1,cj2;
vector<int>trl,trh,tcl,tch;

void valnode(int v, int tl){
    trl[v]=r[tl];
    trh[v]=r[tl];
    tcl[v]=c[tl];
    tch[v]=c[tl];
}

void updnode(int v){
    trl[v]=min(trl[2*v],trl[2*v+1]);
    trh[v]=max(trh[2*v],trh[2*v+1]);
    tcl[v]=min(tcl[2*v],tcl[2*v+1]);
    tch[v]=max(tch[2*v],tch[2*v+1]);
}

void build(int v, int tl, int tr){
    if(tl==tr){
        valnode(v,tl);
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        updnode(v);
    }
}

void update(int v, int tl, int tr, int ind){
    if(tl==tr){
        valnode(v,tl);
    }
    else{
        int tm=(tl+tr)/2;
        if(tm>=ind){
            update(2*v,tl,tm,ind);
        }
        else update(2*v+1,tm+1,tr,ind);
        updnode(v);
    }
}

pair<pii,pii>join(pair<pii,pii>x,pair<pii,pii>y){
    return {{min(x.ff.ff,y.ff.ff),max(x.ff.ss,y.ff.ss)},
            {min(x.ss.ff,y.ss.ff),max(x.ss.ss,y.ss.ss)}};
}

pair<pii,pii>get_val(int v, int tl, int tr, int l, int r){
    if(l>r)return {{MOD,0},{MOD,0}};
    if(tl==l&&tr==r)return {{trl[v],trh[v]},{tcl[v],tch[v]}};
    else{
        int tm=(tl+tr)/2;
        return join(get_val(2*v,tl,tm,l,min(r,tm)),
                get_val(2*v+1,tm+1,tr,max(l,tm+1),r));
    }
}

void update_corr(int a, int b){
    int i1,i2,j1,j2;
    if(a!=0){
        i1=ci1[a-1];
        i2=ci2[a-1];
        j1=cj1[a-1];
        j2=cj2[a-1];
    }
    else{
        i1=i2=r[a];
        j1=j2=c[a];
    }
    for(int i=a;i<b;i++){
        if(i1>r[i])i1=r[i];
        if(i2<r[i])i2=r[i];
        if(j1>c[i])j1=c[i];
        if(j2<c[i])j2=c[i];
        // cout<<i<<": "<<i1<<" "<<i2<<" "<<j1<<" "<<j2<<endl;
        bool rgh=false;
        if((j2-j1+1)*(i2-i1+1)==i+1){
            rgh=true;
        }
        if(rgh&&!corr[i])sum++;
        else if(!rgh&&corr[i])sum--;
        corr[i]=rgh;
        ci1[i]=i1;
        ci2[i]=i2;
        cj1[i]=j1;
        cj2[i]=j2;
    }
}

int calc_ST(){
    int v=0;
    int cur=0;
    while(v<n*m){
        // cout<<v<<endl;
        pair<pii,pii>res=get_val(1,0,n*m-1,0,v);
        int i1,i2,j1,j2;
        i1=res.ff.ff;
        i2=res.ff.ss;
        j1=res.ss.ff;
        j2=res.ss.ss;
        if((j2-j1+1)*(i2-i1+1)==v+1){
            cur++;
            v++;
        }
        else{
            v=(j2-j1+1)*(i2-i1+1)-1;
        }
    }
    return cur;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    r=R;
    c=C;
    n=H;
    m=W;
    if(n<=1000&&m<=1000){
        trl.resize(4*n*m,0);
        trh.resize(4*n*m,0);
        tcl.resize(4*n*m,0);
        tch.resize(4*n*m,0);
        build(1,0,n*m-1);
        // cout<<"BUILD COMPLETED"<<endl;
        return;
    }
    corr.resize(n*m,0);
    ci1.resize(n*m,0);
    ci2.resize(n*m,0);
    cj1.resize(n*m,0);
    cj2.resize(n*m,0);
    update_corr(0,n*m);
}

int swap_seats(int a, int b) {
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    if(n<=1000&&m<=1000){
        update(1,0,n*m-1,a);
        update(1,0,n*m-1,b);
        // cout<<"UPDATES COMPLETED"<<endl;
        return calc_ST();
    }
    update_corr(min(a,b),max(a,b));
    return sum;
}

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