Submission #1086475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086475		vladilius	Seats (IOI18_seats)	C++17	37 / 100	4101 ms	119160 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);
    }
    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 v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl) return -1;
        if (l <= tl && tr <= r){
            return (t[v].ss > x) ? fn1(v, tl, tr, x) : -1;
        }
        int tm = (tl + tr) / 2, vv = 2 * v, j = find1(vv, tl, tm, l, r, x);
        return (j == -1) ? (find1(vv + 1, tm + 1, tr, l, r, x)) : j;
    }
    int find1(int l, int x){
        int j = find1(1, 1, n, l, n, x);
        return (j == -1) ? (n + 1) : j;
    }
    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 v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl) return -1;
        if (l <= tl && tr <= r){
            return (t[v].ff < x) ? fn2(v, tl, tr, x) : -1;
        }
        int tm = (tl + tr) / 2, vv = 2 * v, j = find2(vv, tl, tm, l, r, x);
        return (j == -1) ? (find2(vv + 1, tm + 1, tr, l, r, x)) : j;
    }
    int find2(int l, int x){
        int j = find2(1, 1, n, l, n, x);
        return (j == -1) ? (n + 1) : j;
    }
};

vector<int> x, y, m1, m2, m3, m4;
vector<bool> f;
int h, w, k, tot;
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]);
    }
    m1.resize(k + 1);
    m2.resize(k + 1);
    m3.resize(k + 1);
    m4.resize(k + 1);
    f.resize(k + 1);
    m1[0] = m3[0] = 0;
    m2[0] = m4[0] = k + 1;
    for (int i = 1; i <= k; i++){
        m1[i] = max(m1[i - 1], x[i]);
        m2[i] = min(m2[i - 1], x[i]);
        m3[i] = max(m3[i - 1], y[i]);
        m4[i] = min(m4[i - 1], y[i]);
        f[i] = ((m1[i] - m2[i] + 1) * (m3[i] - m4[i] + 1) == i);
        tot += f[i];
    }
}

int swap_seats(int a, int b){
    a++; b++;
    if (a > b) swap(a, b);
    if (h <= 1000 && w <= 1000){
        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]);
        
        int i = 1, m1 = x[1], m2 = x[1], m3 = y[1], m4 = y[1], out = 0;
        vector<int> t(4);
        while (true){
            if (!t[0]) t[0] = T1.find1(i, m1);
            if (!t[1]) t[1] = T1.find2(i, m2);
            if (!t[2]) t[2] = T2.find1(i, m3);
            if (!t[3]) t[3] = T2.find2(i, m4);
            int j = min({t[0], t[1], t[2], t[3]});
            
            int pr = (m1 - m2 + 1) * (m3 - m4 + 1);
            out += (i <= pr && pr < j);
            if (j > k) break;
            if (t[0] == j){
                m1 = x[j];
                t[0] = 0;
            }
            if (t[1] == j){
                m2 = x[j];
                t[1] = 0;
            }
            if (t[2] == j){
                m3 = y[j];
                t[2] = 0;
            }
            if (t[3] == j){
                m4 = y[j];
                t[3] = 0;
            }
            i = j;
        }
        return out;
    }
    else if (abs(a - b) <= 1e4){
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        for (int i = a; i < b; i++){
            m1[i] = max(m1[i - 1], x[i]);
            m2[i] = min(m2[i - 1], x[i]);
            m3[i] = max(m3[i - 1], y[i]);
            m4[i] = min(m4[i - 1], y[i]);
            tot -= f[i];
            f[i] = ((m1[i] - m2[i] + 1) * (m3[i] - m4[i] + 1) == i);
            tot += f[i];
        }
        return tot;
    }
    else {
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        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]);
            f[i] = ((m2 - m1 + 1) * (m4 - m3 + 1) == i);
            out += f[i];
        }
        tot = out;
        return out;
    }
}

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