Submission #1086463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086463		vladilius	Seats (IOI18_seats)	C++17	11 / 100	4097 ms	103504 KiB

seats

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct ST{
    vector<pii> t;
    int n;
    void init(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, int& x){
        if (tl == tr){
            t[v] = {x, x};
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].ff = min(t[vv].ff, t[vv + 1].ff);
        t[v].ss = max(t[vv].ss, t[vv + 1].ss);
    }
    void upd(int p, int x){
        upd(1, 1, n, p, x);
    }
    vector<arr3> all;
    void dec(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all.pb({v, tl, tr});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        dec(vv, tl, tm, l, r);
        dec(vv + 1, tm + 1, tr, l, r);
    }
    int fn1(int v, int tl, int tr, int& x){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv].ss > x){
            return fn1(vv, tl, tm, x);
        }
        return fn1(vv + 1, tm + 1, tr, x);
    }
    int find1(int l, int x){
        all.clear();
        dec(1, 1, n, l, n);
        for (auto [v, tl, tr]: all){
            if (t[v].ss > x){
                return fn1(v, tl, tr, x);
            }
        }
        return n + 1;
    }
    int fn2(int v, int tl, int tr, int& x){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[vv].ff < x){
            return fn2(vv, tl, tm, x);
        }
        return fn2(vv + 1, tm + 1, tr, x);
    }
    int find2(int l, int x){
        all.clear();
        dec(1, 1, n, l, n);
        for (auto [v, tl, tr]: all){
            if (t[v].ff < x){
                return fn2(v, tl, tr, x);
            }
        }
        return n + 1;
    }
};

vector<int> x, y;
int h, w, k;
ST T1, T2;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h = H; w = W; k = h * w;
    x.resize(k + 1);
    y.resize(k + 1);
    T1.init(k); T2.init(k);
    for (int i = 1; i <= k; i++){
        x[i] = R[i - 1] + 1;
        y[i] = C[i - 1] + 1;
        T1.upd(i, x[i]);
        T2.upd(i, y[i]);
    }
}

int swap_seats(int a, int b){
    a++; b++;
    T1.upd(a, x[b]);
    T1.upd(b, x[a]);
    swap(x[a], x[b]);
    T2.upd(a, y[b]);
    T2.upd(b, y[a]);
    swap(y[a], y[b]);
    
    if (h <= 1000 && w <= 1000){
        int i = 1, m1 = x[1], m2 = x[1], m3 = y[1], m4 = y[1], out = 0;
        while (true){
            int j1 = T1.find1(i, m1), j2 = T1.find2(i, m2), j3 = T2.find1(i, m3), j4 = T2.find2(i, m4), j = min({j1, j2, j3, j4});
            
            int pr = (m1 - m2 + 1) * (m3 - m4 + 1);
            out += (i <= pr && pr < j);
            if (j > k) break;
            if (j1 == j) m1 = x[j];
            if (j2 == j) m2 = x[j];
            if (j3 == j) m3 = y[j];
            if (j4 == j) m4 = y[j];
            i = j;
        }
        return out;
    }
    else {
        int out = 1, m1 = x[1], m2 = x[1], m3 = y[1], m4 = y[1];
        for (int i = 2; i <= k; i++){
            m1 = min(m1, x[i]); m2 = max(m2, x[i]);
            m3 = min(m3, y[i]); m4 = max(m4, y[i]);
            out += ((m2 - m1 + 1) * (m4 - m3 + 1) == i);
        }
        return out;
    }
}

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