Submission #1067256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067256		Ghulam_Junaid	Seats (IOI18_seats)	C++17	31 / 100	4045 ms	57172 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){
    p += n;
    seg[id][p].mn = seg[id][p].mx = val;
    while (p > 1){
        seg[id][p / 2].mn = min(seg[id][p].mn, seg[id][p ^ 1].mn);
        seg[id][p / 2].mx = max(seg[id][p].mx, seg[id][p ^ 1].mx);
        p /= 2;
    }
}

int get_max(int id, int l, int r){
    int res = -1;
    for (l += n, r += n; l < r; l /= 2, r /= 2) { 
        if (l&1)
            res = max(res, seg[id][l++].mx); 
        if (r&1)  
            res = max(res, seg[id][--r].mx); 
    } 
    return res; 
}

int get_min(int id, int l, int r){
    int res = 1e9;
    for (l += n, r += n; l < r; l /= 2, r /= 2) { 
        if (l&1)
            res = min(res, seg[id][l++].mn); 
        if (r&1)  
            res = min(res, seg[id][--r].mn); 
    } 
    return res; 
}

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;

    int last = -1;
    for (int i = 0; i < n; i ++){
        if (last + 15 < i){
            mnr = get_min(0, 0, i + 1);
            mnc = get_min(1, 0, i + 1);
            mxr = get_max(0, 0, i + 1);
            mxc = get_max(1, 0, i + 1);
        }
        else{
            for (int j = last + 1; j <= i; j ++){
                mnr = min(mnr, a[0][j]);
                mnc = min(mnc, a[1][j]);
                mxr = max(mxr, a[0][j]);
                mxc = max(mxc, a[1][j]);
            }
        }
        last = i;

        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: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30