Submission #1067228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067228		Ghulam_Junaid	Seats (IOI18_seats)	C++17	25 / 100	4091 ms	73812 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;
    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: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30