Submission #1216966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216966		perekopskad	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	56640 KiB

seats

#pragma GCC optimize ("Ofast")
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
 
#define pb push_back
#define ff first
#define ss second
#define pii pair <ll, ll>
#define el '\n'
#define popb pop_back
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
 
int const N = 1e6 + 10;
int const LOG = 20;
int const inf = 1e9 + 10;

int n, m, cur;
int x[N], y[N];

struct SegTree {
    int t[2][4 * N];

    int getmin(int i, int tl, int tr, int l, int r) {
        if(tr < l || r < tl)
            return inf;

        if(l <= tl && tr <= r)
            return t[0][i];

        int mid = (tl + tr) / 2;
        return min(getmin(i + i, tl, mid, l, r), getmin(i + i + 1, mid + 1, tr, l, r));
    }
    
    int getmax(int i, int tl, int tr, int l, int r) {
        if(tr < l || r < tl)
            return 0;

        if(l <= tl && tr <= r)
            return t[1][i];

        int mid = (tl + tr) / 2;
        return max(getmax(i + i, tl, mid, l, r), getmax(i + i + 1, mid + 1, tr, l, r));
    }

    void update(int i, int tl, int tr, int pos, int val) {
        if(tl == tr) {
            t[0][i] = val;
            t[1][i] = val;
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid)
            update(i + i, tl, mid, pos, val);
        else 
            update(i + i + 1, mid + 1, tr, pos, val);

        t[0][i] = min(t[0][i + i], t[0][i + i + 1]);
        t[1][i] = max(t[1][i + i], t[1][i + i + 1]);
    }

    void build(int i, int tl, int tr, bool flag) {
        if(tl == tr) {
            if(flag) {
                t[0][i] = x[tl];
                t[1][i] = x[tl];
            }
            else {
                t[0][i] = y[tl];
                t[1][i] = y[tl];
            }
            return;
        }
        int mid = (tl + tr) / 2;
        build(i + i, tl, mid, flag);
        build(i + i + 1, mid + 1, tr, flag);
        t[0][i] = min(t[0][i + i], t[0][i + i + 1]);
        t[1][i] = max(t[1][i + i], t[1][i + i + 1]);
    }
};

SegTree X, Y;

int check(int k) {
    int x1 = X.getmin(1, 0, n * m - 1, 0, k);
    int x2 = X.getmax(1, 0, n * m - 1, 0, k);
    int y1 = Y.getmin(1, 0, n * m - 1, 0, k);
    int y2 = Y.getmax(1, 0, n * m - 1, 0, k);

    return (x2 - x1 + 1) * (y2 - y1 + 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H, m = W;
    for(int i = 0; i < n * m; i++) {
        x[i] = R[i];
        y[i] = C[i];
    }

    X.build(1, 0, n * m - 1, 1);
    Y.build(1, 0, n * m - 1, 0);


    fr(i, 0, n * m - 1)
        cur += (check(i) == i + 1);
}

int swap_seats(int a, int b) {
    if(abs(a - b) <= n + m) {
        if(a > b) swap(a, b);
        fr(i, a, b - 1)
            cur -= (check(i) == i + 1);
        
        swap(x[a], x[b]);
        X.update(1, 0, n * m - 1, a, x[a]);
        X.update(1, 0, n * m - 1, b, x[b]);
        swap(y[a], y[b]);
        Y.update(1, 0, n * m - 1, a, y[a]);
        Y.update(1, 0, n * m - 1, b, y[b]);

        fr(i, a, b - 1)
            cur += (check(i) == i + 1);

        return cur;
    }
    swap(x[a], x[b]);
    X.update(1, 0, n * m - 1, a, x[a]);
    X.update(1, 0, n * m - 1, b, x[b]);
    swap(y[a], y[b]);
    Y.update(1, 0, n * m - 1, a, y[a]);
    Y.update(1, 0, n * m - 1, b, y[b]);

    int i = 0;
    cur = 0;
    while(i < n * m) {
        int s = check(i);
        if(s == i + 1) {
            cur++;
            i++;
        }
        else 
            i = s - 1;
    }
    return cur;
}

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