Submission #777177

#	Time	Username	Problem	Language	Result	Execution time	Memory
777177		GusterGoose27	Seats (IOI18_seats)	C++17	11 / 100	4077 ms	55972 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef array<int, 4> ar4;

const int MAXN = 1e6+5;

int h, w, n;
pii points[MAXN];
int vals[4][2*MAXN];
int ans = 0;

void single(int i) {
    vals[0][i] = min(vals[0][2*i], vals[0][2*i+1]);
    vals[1][i] = max(vals[1][2*i], vals[1][2*i+1]);
    vals[2][i] = min(vals[2][2*i], vals[2][2*i+1]);
    vals[3][i] = max(vals[3][2*i], vals[3][2*i+1]);
}

void set_val(int i) {
    vals[0][i+n] = points[i].first;
    vals[1][i+n] = points[i].first;
    vals[2][i+n] = points[i].second;
    vals[3][i+n] = points[i].second;
}

void upd(int p) {
    set_val(p);
    for (p = (p+n)/2; p > 0; p /= 2) single(p);
}

void combine(ar4 &a, int i) {
    a[0] = min(a[0], vals[0][i]);
    a[1] = max(a[1], vals[1][i]);
    a[2] = min(a[2], vals[2][i]);
    a[3] = max(a[3], vals[3][i]);
}

int get(int i) {
    ar4 res({h, 0, w, 0});
    for (int l = n, r = i+1+n; r > l; r /= 2, l /= 2) {
        if (l & 1) combine(res, l++);
        if (r & 1) combine(res, --r);
    }
    return (res[1]-res[0]+1)*(res[3]-res[2]+1);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H;
    w = W;
    n = h*w;
    ar4 cur({h, 0, w, 0});
    for (int i = 0; i < n; i++) {
        points[i] = pii(R[i], C[i]);
        set_val(i);
        combine(cur, i+n);
        ans += ((cur[1]-cur[0]+1)*(cur[3]-cur[2]+1) == i+1);
    }
    for (int i = n-1; i > 0; i--) single(i);
}

int swap_seats(int a, int b) {
    for (int i = min(a, b); i <= max(a, b); i++) ans -= (get(i) == i+1);
    swap(points[a], points[b]);
    upd(a);
    upd(b);
    for (int i = min(a, b); i <= max(a, b); i++) {
        if (get(i) == i+1) {
            ans++;
            // cerr << i << '\n';
        }
        // ans += (get(i) == i+1);
    }
    // cerr << '\n';
    return ans;
}

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