Submission #1067207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067207		Ghulam_Junaid	Seats (IOI18_seats)	C++17	5 / 100	4083 ms	74952 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
// #include "grader.cpp"

using namespace std;

const int N = 1e6 + 10;

int n, h, w;
vector<int> a[2];

struct node{
    int mn, mx;
} seg[2][4 * N];

void modify(int id, int p, int val, int v = 1, int s = 0, int e = n){
    if (e - s == 1){
        seg[id][v].mn = seg[id][v].mx = val;
        return ;
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    if (p < mid) modify(id, p, val, lc, s, mid);
    else modify(id, p, val, rc, mid, e);

    seg[id][v].mn = min(seg[id][lc].mn, seg[id][rc].mn);
    seg[id][v].mx = max(seg[id][lc].mx, seg[id][rc].mx);
}

int get_max(int id, int l, int r, int v = 1, int s = 0, int e = n){
    if (e <= l || r <= s) return -1;
    if (l <= s && e <= r) return seg[id][v].mx;

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    return max(get_max(id, l, r, lc, s, mid), get_max(id, l, r, rc, mid, e));
}

int get_min(int id, int l, int r, int v = 1, int s = 0, int e = n){
    if (e <= l || r <= s) return 1e9;
    if (l <= s && e <= r) return seg[id][v].mn;

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    return min(get_min(id, l, r, lc, s, mid), get_min(id, l, r, rc, mid, e));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h = H, w = W, a[0] = R, a[1] = C;
    n = h * w;
    for (int id = 0; id < 2; id ++)
        for (int i = 0; i < n; i ++)
            modify(id, i, a[id][i]);
}

int swap_seats(int x, int y){
    for (int id = 0; id < 2; id ++){
        swap(a[id][x], a[id][y]);
        modify(id, x, a[id][x]);
        modify(id, y, a[id][y]);
    }

    int ans = 0;
    int mnr = 1e9, mnc = 1e9, mxr = -1, mxc = -1;
    for (int i = 0; i < n; i ++){
        mnr = min(mnr, get_min(0, 0, i + 1));
        mnc = min(mnc, get_min(1, 0, i + 1));
        mxr = max(mxr, get_max(0, 0, i + 1));
        mxc = max(mxc, get_max(1, 0, i + 1));

        int ele = (mxr - mnr + 1) * (mxc - mnc + 1);
        if (ele == (i + 1))
            ans++;
        else
            i = ele - 2;
    }

    return ans;
}

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