Submission #991416

#	Time	Username	Problem	Language	Result	Execution time	Memory
991416		hirayuu_oj	Seats (IOI18_seats)	C++17	25 / 100	4090 ms	56972 KiB

seats

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
using pll=pair<int,int>;
constexpr ll LINF=(1LL<<62)-(1LL<<31);

#include "seats.h"

template<class T,auto op,auto e>
struct SegTree{
    vector<T> val;
    int size;
    SegTree(int sz){
        size=sz;
        val.resize(size*2,e());
    }
    void set(int pos,T v){
        pos+=size;
        val[pos]=v;
        while(pos>1){
            pos/=2;
            val[pos]=op(val[pos*2],val[pos*2+1]);
        }
    }
    T get(int pos){
        return val[pos];
    }
    T prod(int lf,int ri){
        lf+=size;
        ri+=size;
        T ret_lf=e();
        T ret_ri=e();
        while(lf<ri){
            if(lf&1){
                ret_lf=op(ret_lf,val[lf]);
                lf++;
            }
            if(ri&1){
                ri--;
                ret_ri=op(val[ri],ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
};

pll mx(pll x,pll y){
    return {min(x.first,y.first),max(x.second,y.second)};
}
pll e(){
    return {1<<20,-(1<<20)};
}
SegTree<pll, mx, e> x(1<<20);
SegTree<pll, mx, e> y(1<<20);
vector<int> r,c;
int h,w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h=H;
    w=W;
    r=R;
    c=C;
    rep(i,H*W){
        x.set(i,pll(R[i],R[i]));
    }
    rep(i,H*W){
        y.set(i,pll(C[i],C[i]));
    }
}
int get(int i){
    pll xs=x.prod(0,i+1);
    pll ys=y.prod(0,i+1);
    return (xs.second-xs.first+1)*(ys.second-ys.first+1);
}
int getbypair(pll xs,pll ys){
    return (xs.second-xs.first+1)*(ys.second-ys.first+1);
}
int swap_seats(int a, int b) {
    if(a>b)swap(a,b);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    x.set(a,{r[a],r[a]});
    x.set(b,{r[b],r[b]});
    y.set(a,{c[a],c[a]});
    y.set(b,{c[b],c[b]});
    int ans=1;
    int now=1;
    while(now<h*w){
        int pos=1;
        pll nmx=e();
        pll nmy=e();
        rep(i,20){
            if(getbypair(mx(nmx,x.get(pos*2)),mx(nmy,y.get(pos*2)))<=now){
                nmx=mx(nmx,x.get(pos*2));
                nmy=mx(nmy,y.get(pos*2));
                pos=pos*2+1;
            }
            else{
                pos=pos*2;
            }
        }
        int ok=pos-(1<<20);
        now=get(ok);
        if(now==get(now-1)){
            ans++;
        }
    }
    return ans;
}

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