Submission #1290781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290781		Math4Life2020	자리 배치 (IOI18_seats)	C++20	100 / 100	3976 ms	172672 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 5e8;

vector<vector<ll>> vals;
vector<pii> locs;
ll N;

pii fz(pii p1, pii p2) {
    if (p1.first<p2.first) {
        return p1;
    }
    if (p2.first<p1.first) {
        return p2;
    }
    assert(p1.first==p2.first);
    return {p1.first,p1.second+p2.second};
}

struct Node {
    ll xl=-1; ll xr=-1;
    Node *l=nullptr,*r=nullptr;
    pii val = {INF,-1}; //val, qty: store min value in subtree and multiplicity
    ll lz = 0; //lazy tag: applied to this but not to children
    Node(){};
    Node(ll _xl, ll _xr) {
        xl = _xl; xr = _xr;
        val = {0,xr-xl+1};
        if (xl!=xr) {
            ll xm = (xl+xr)/2;
            l = new Node(xl,xm);
            r = new Node(xm+1,xr);
        }
    }
    void pdn() {
        if (xl==xr) {
            lz=0; return;
        }
        l->val.first += lz;
        l->lz += lz;
        r->val.first += lz;
        r->lz += lz;
        lz = 0;
    }
    void lft() {
        assert(lz==0);
        if (xl==xr) {
            return;
        }
        val = fz(l->val,r->val);
    }
    void appl(ll ql, ll qr, ll v) { //change ql,qr by v
        if (qr<xl || ql>xr) {
            return;
        }
        pdn();
        if (ql<=xl && xr<=qr) {
            val.first+=v;
            lz+=v;
            return;
        }
        assert(xl!=xr);
        l->appl(ql,qr,v);
        r->appl(ql,qr,v);
        lft();
    }
    ll extr() {
        //cout << "val = "<<val.first<<", "<<val.second<<"\n";
        assert(val.first>=4);
        if (val.first==4) {
            return val.second;
        }
        return 0;
    }
};

Node* root = new Node();

void prc(ll x, ll y, ll v) { //process square; determine whether to add or subtract
    //cout << "prc: x,y="<<x<<","<<y<<"\n";
    vector<ll> v0;
    v0.push_back(vals[x][y]);
    v0.push_back(vals[x][y+1]);
    v0.push_back(vals[x+1][y]);
    v0.push_back(vals[x+1][y+1]);
    sort(v0.begin(),v0.end());
    assert(v0[0]<v0[1]);
    //cout << "apply add to: "<<v0[0]<<","<<(v0[1]-1)<<"\n";
    root->appl(v0[0],v0[1]-1,v);
    root->appl(v0[2],v0[3]-1,v);
}

void psq(ll x, ll y, ll v) { //center x,y
    prc(x-1,y-1,v);
    prc(x,y-1,v);
    prc(x-1,y,v);
    prc(x,y,v);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    //ll vals[H+2][W+2];
    vals = vector<vector<ll>> (H+2,vector<ll>(W+2,-1));
    for (int h=0;h<(H+2);h++) {
        for (int w=0;w<(W+2);w++) {
            vals[h][w]=H*W;
        }
    }
    //pii locs[H*W];
    N = H*W;
    locs = vector<pii>(N);
    for (ll i=0;i<N;i++) {
        locs[i]={R[i]+1,C[i]+1};
        vals[R[i]+1][C[i]+1]=i;
    }
    root = new Node(0,N-1);
    for (ll h=0;h<(H+1);h++) {
        for (ll w=0;w<(W+1);w++) {
            prc(h,w,1);
        }
    }
    //cout << (root->extr()) <<"=ival\n";
}

int swap_seats(int a, int b) {
    psq(locs[a].first,locs[a].second,-1);
    psq(locs[b].first,locs[b].second,-1);
    swap(locs[a],locs[b]);
    vals[locs[a].first][locs[a].second]=a;
    vals[locs[b].first][locs[b].second]=b;
    psq(locs[a].first,locs[a].second,1);
    psq(locs[b].first,locs[b].second,1);
    ll ans0 = (root->extr());
    // ll ans1 = 0;
    // ll xl=INF,xr=-INF,yl=INF,yr=-INF;
    // for (ll i=0;i<N;i++) {
    //     pii p0 = locs[i];
    //     xl = min(xl,p0.first);
    //     xr = max(xr,p0.first);
    //     yl = min(yl,p0.second);
    //     yr = max(yr,p0.second);
    //     if ((yr-yl+1)*(xr-xl+1)==(i+1)) {
    //         ans1++;
    //     }
    // }
    // if (ans0!=ans1) {
    //     cout << "ans0="<<ans0<<"\n";
    //     cout << "ans1="<<ans1<<"\n";
    //     cout << "failure\n"; 
    //     exit(0);
    // }
    return ans0;
}

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