제출 #580819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580819		definitelynotmee	자리 배치 (IOI18_seats)	C++17	50 / 100	4054 ms	87876 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

vector<pii> v;
int resp = 0;
vector<pii> mini, maxi;
vector<int> isgood;
int n;

struct SegTree{
    struct seg{
        int sum, min, minct;
    };
    vector<seg> tree;
    int q, val, sz;
    SegTree(int n = 0){
        tree = vector<seg>(4*n+1);
        sz = n;
    }
    seg merge(seg a, seg b){
        b.min+=a.sum;
        if(b.min == a.min){
            a.minct+=b.minct;
        }
        if(b.min < a.min){
            a.min = b.min;
            a.minct = b.minct;
        }
        a.sum+=b.sum;
        return a;
    }
    void upd(int id, int l, int r){
        if(l > q || r < q)
            return;
        if(l == q && r == q){
            tree[id] = {val,val,1};
            return;
        }
        int e = id*2+1, d = id*2+2, m = (l+r)>>1;
        upd(e,l,m);
        upd(d,m+1,r);
        tree[id] = merge(tree[e],tree[d]);
    }

    void makeupd(int id, int x){
        val = x;
        q = id;
        upd(0,0,sz-1);
    }
} st;

vector<int> x;
vector<int> arr;
bool flag = 0;

void calc(int id, pii nmin, pii nmax){
    resp-=isgood[id];
    isgood[id] = (nmax.ff-nmin.ff+1)*(nmax.ss-nmin.ss+1) == id+1;
    resp+=isgood[id];
    mini[id] = nmin;
    maxi[id] = nmax;
}

void comp(int id){
    if(id == 1e9)
        return;
    int cur = x[id];
    int dif = 1 - (int)(arr[cur-1] < id) - (int)(arr[cur+1] < id);
    st.makeupd(id,dif);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H*W;
    if(H!=1){
        resp = 0;
        flag = 0;
        v = vector<pii>(n);
        mini = vector<pii>(n);
        maxi = vector<pii>(n);
        isgood = vector<int>(n);
        for(int i = 0; i < n; i++){
            v[i] = {R[i], C[i]};
        }
    
        calc(0,v[0],v[0]);
        for(int i = 1; i < n; i++){
            pii nmin = mini[i-1], nmax = maxi[i-1];
            nmin.ff = min(nmin.ff,v[i].ff);
            nmin.ss = min(nmin.ss,v[i].ss);
            nmax.ff = max(nmax.ff,v[i].ff);
            nmax.ss = max(nmax.ss,v[i].ss);
            calc(i,nmin,nmax);
        }
        return;
    }

    flag = 1;

    st = SegTree(n);
    x = vector<int>(n);
    arr = vector<int>(n+2);
    arr[0] = 1e9;
    arr.back() = 1e9;

    for(int i = 0; i < n; i++){
        x[i] = C[i]+1;
        arr[x[i]] = i;
    }

    for(int i = 0; i < n; i++){
        comp(i);
    }
    ///cout << st.tree[0].minct << ' ' << st.tree[0].min << endl;
}

int swap_seats(int a, int b) {
    if(flag){
        //cout << "->" << a << ' ' << b << endl;
        swap(x[a],x[b]);
        swap(arr[x[a]],arr[x[b]]);
        assert(arr[x[a]] == a);
        assert(arr[x[b]] == b);
        for(int i = -1; i <= 1; i++){
            comp(arr[x[a]+i]);
            comp(arr[x[b]+i]);
        }
        if(st.tree[0].min == 1)
            return st.tree[0].minct;
        assert(1 == 2);
    }
    if(a > b)
        swap(a,b);
    
    swap(v[a],v[b]);
    if(a == 0){
        mini[a] = v[a];
        maxi[a] = v[a];
        a++;
    }
    for(int i = a; i <= b; i++){
        pii nmin = mini[i-1], nmax = maxi[i-1];
        nmin.ff = min(nmin.ff,v[i].ff);
        nmin.ss = min(nmin.ss,v[i].ss);
        nmax.ff = max(nmax.ff,v[i].ff);
        nmax.ss = max(nmax.ss,v[i].ss);
        calc(i,nmin,nmax);
    }
    return resp;
}

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