Submission #1290734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290734		Math4Life2020	Seats (IOI18_seats)	C++20	0 / 100	4096 ms	39964 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;

// 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();

vector<ll> vf;

void appl(ll a, ll b, ll v) {
    for (ll x=a;x<=b;x++) {
        vf[x]+=v;
    }
}

ll extr() {
    ll ans = 0;
    for (ll x: vf) {
        assert(x>=4);
        if (x==4) {
            ans++;
        }
    }
    return ans;
}

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);
    appl(v0[0],v0[1]-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];
    ll 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);
    vf = vector<ll>(N,0);
    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);
    //return (root->extr());
    return extr();
}

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