Submission #1061979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061979		shenfe1	Seats (IOI18_seats)	C++17	100 / 100	1698 ms	135760 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define lb lower_bound
#define pii pair<int,int>
#define F first
#define S second
#define in insert
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))

const int MAX=1e6+10;
const int inf=1e9;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int h,w;
vector<vector<int>> a;

struct node{
    int mn,cnt;

    node(){
        mn=cnt=0;
    }
};

node mrg(node a,node b){
    node res;
    if(a.mn<b.mn){
        res=a;
    }
    else if(a.mn>b.mn){
        res=b;
    }
    else{
        res.mn=a.mn;
        res.cnt=a.cnt+b.cnt;
    }
    return res;
}

struct segtree{
    node t[4*MAX];
    int add[4*MAX];

    void build(int v,int tl,int tr){
        add[v]=0;
        if(tl==tr){
            t[v].mn=0;
            t[v].cnt=1;
            return;
        }
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=mrg(t[2*v],t[2*v+1]);
    }

    void upd(int v,int x){
        t[v].mn+=x;
        add[v]+=x;
    }

    void push(int v){
        if(add[v]){
            upd(2*v,add[v]);
            upd(2*v+1,add[v]);
            add[v]=0;
        }
    }

    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            upd(v,x);
            return;
        }
        push(v);
        int tm=(tl+tr)/2;
        update(2*v,tl,tm,l,r,x);
        update(2*v+1,tm+1,tr,l,r,x);
        t[v]=mrg(t[2*v],t[2*v+1]);
    }

    int get(int v,int tl,int tr,int pos){
        if(tl==tr){
            return t[v].mn;
        }
        int tm=(tl+tr)/2;
        push(v);
        if(pos<=tm)return get(2*v,tl,tm,pos);
        else return get(2*v+1,tm+1,tr,pos);
    }
}T;

void upd(int i,int j,int x){
    vector<int> v={a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]};
    sort(all(v));
    T.update(1,0,h*w-1,v[0],v[1]-1,x);
    T.update(1,0,h*w-1,v[2],v[3]-1,x*10);
}

vector<int> r,c;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h=H,w=W;
    a.resize(h+2);
    for(int i=0;i<=h+1;i++)a[i].resize(w+2);
    for(int i=0;i<sz(R);i++){
        R[i]++,C[i]++;
    }
    r=R,c=C;
    for(int i=0;i<=h+1;i++){
        for(int j=0;j<=w+1;j++){
            a[i][j]=h*w;
        }
    }
    for(int i=0;i<sz(R);i++){
        a[R[i]][C[i]]=i;
    }
    T.build(1,0,h*w-1);
    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++){
            upd(i,j,1);
        }
    }
}

int swap_seats(int A,int B){
    vector<pii> vec;
    for(int i=r[A]-1;i<=r[A];i++){
        for(int j=c[A]-1;j<=c[A];j++){
            vec.pb({i,j});
        }
    }
    for(int i=r[B]-1;i<=r[B];i++){
        for(int j=c[B]-1;j<=c[B];j++){
            vec.pb({i,j});
        }
    }
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    for(auto [i,j]:vec)upd(i,j,-1);
    swap(a[r[A]][c[A]],a[r[B]][c[B]]);
    swap(r[A],r[B]);
    swap(c[A],c[B]);
    for(auto [i,j]:vec)upd(i,j,1);
    return T.t[1].cnt;
}

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