Submission #248654

#	Time	Username	Problem	Language	Result	Execution time	Memory
248654		Dormi	Seats (IOI18_seats)	C++14	100 / 100	2745 ms	118332 KiB

seats

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return (int)a.size();}
const int MAXN=1e6+1;
vector<vector<int>> arr;
pii loc[MAXN];
int xc[4]={1,-1,0,0},yc[4]={0,0,1,-1};
int h,w,maxv;
struct seg{
    struct node{
        pii data;
        int lazy;
        node(){
            data={0,0},lazy=0;
        }
    }t[2*MAXN];
    pii pu(pii a, pii b){
        if(a.first<b.first)return a;
        if(b.first<a.first)return b;
        return {a.first,a.second+b.second};
    }
    void mt(int ind, int le, int ri){
        t[ind].data.second=ri-le+1;
        int mid=le+(ri-le)/2;
        int left=ind+1,right=ind+(mid-le+1)*2;
        if(le!=ri)mt(left,le,mid),mt(right,mid+1,ri);
    }
    void rl(int ind, int le, int ri){
        t[ind].data.first+=t[ind].lazy;
        if(le!=ri){
            int mid=le+(ri-le)/2;
            int left=ind+1,right=ind+(mid-le+1)*2;
            t[left].lazy+=t[ind].lazy;
            t[right].lazy+=t[ind].lazy;
        }
        t[ind].lazy=0;
    }
    void update(int ind, int le, int ri, int l, int r, int val){
        rl(ind,le,ri);
        if(le>r||ri<l)return;
        if(le>=l&&ri<=r){
            t[ind].lazy=val;
            rl(ind,le,ri);
            return;
        }
        int mid=le+(ri-le)/2;
        int left=ind+1,right=ind+(mid-le+1)*2;
        update(left,le,mid,l,r,val),update(right,mid+1,ri,l,r,val);
        t[ind].data=pu(t[left].data,t[right].data);
    }
}tree;
bool inbounds(pii a){
    return (a.first>=0&&a.second>=0&&a.first<h&&a.second<w);
}
void update(pii a, int val){
    pii rn={arr[a.first][a.second],maxv};
    if(inbounds({a.first-1,a.second}))rn.second=min(rn.second,arr[a.first-1][a.second]-1);
    if(inbounds({a.first,a.second-1}))rn.second=min(rn.second,arr[a.first][a.second-1]-1);
    if(rn.first<=rn.second)tree.update(0,0,maxv,rn.first,rn.second,val);
    rn={0,arr[a.first][a.second]-1};
    vector<int> te;
    for(int i=0;i<4;i++){
        pii ne={a.first+xc[i],a.second+yc[i]};
        if(inbounds(ne))te.push_back(arr[ne.first][ne.second]);
    }
    sort(te.begin(),te.end());
    if(sz(te)>=2){
        rn.first=te[1];
        if(rn.first<=rn.second)tree.update(0,0,maxv,rn.first,rn.second,val);
    }
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h=H,w=W;
    maxv=h*w-1;
    arr.resize(h);
    tree.mt(0,0,maxv);
    for(int i=0;i<h;i++)arr[i].resize(w);
    for(int i=0;i<h*w;i++){
        loc[i]={R[i],C[i]};
        arr[R[i]][C[i]]=i;
    }
    for(int i=0;i<h;i++)for(int j=0;j<w;j++)update({i,j},1);
}
int swap_seats(int a, int b){
    set<pii> toupdate;
    toupdate.insert(loc[a]),toupdate.insert(loc[b]);
    for(int i=0;i<4;i++){
        pii ne={loc[a].first+xc[i],loc[a].second+yc[i]};
        if(inbounds(ne))toupdate.insert(ne);
        ne={loc[b].first+xc[i],loc[b].second+yc[i]};
        if(inbounds(ne))toupdate.insert(ne);
    }
    for(auto x:toupdate)update(x,-1);
    swap(arr[loc[a].first][loc[a].second],arr[loc[b].first][loc[b].second]);
    swap(loc[a],loc[b]);
    for(auto x:toupdate)update(x,1);
    assert(tree.t[0].data.first==1);
    return tree.t[0].data.second;
}

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