Submission #798455

#	Time	Username	Problem	Language	Result	Execution time	Memory
798455		TheSahib	Seats (IOI18_seats)	C++14	11 / 100	4033 ms	262144 KiB

seats

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

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 1e6 + 5;
const int BLOCK = 500;
const int BLOCKCNT = MAX / BLOCK + 3;
const int oo = 1e9 + 9;

int n;
int h, w;
pii mp[MAX];

struct DATA{
    map<int, int> mpX, mpY;
    void add(pii a){
        mpX[a.first]++;
        mpY[a.second]++;
    }
    void remove(pii a){
        mpX[a.first]--;
        if(mpX[a.first] == 0) mpX.erase(a.first);
        mpY[a.second]--;
        if(mpY[a.second] == 0) mpY.erase(a.second);
    }
    array<int, 4> get(){
        return {mpX.begin()->first, mpY.begin()->first, prev(mpX.end())->first, prev(mpY.end())->first};
    }
};

DATA blocks[BLOCKCNT];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = R.size();
    h = H;
    w = W;
    for (int i = 0; i < n; i++)
    {
        mp[i] = {R[i], C[i]};
    }
    int p = 0;
    for (int i = 0; i < n; i++)
    {
        blocks[p].add({R[i], C[i]});
        if(i % BLOCK == 0){
            ++p;
            blocks[p].mpX = blocks[p - 1].mpX;
            blocks[p].mpY = blocks[p - 1].mpY;
        }
    }
}

int swap_seats(int a, int b) {
    if(a > b) swap(a, b);
    int aBLOCK = (a + BLOCK - 1) / BLOCK;
    int bBLOCK = (b + BLOCK - 1) / BLOCK;
    for (int i = aBLOCK; i < bBLOCK; i++)
    {
        blocks[i].remove(mp[a]);
        blocks[i].add(mp[b]);
    }
    swap(mp[a], mp[b]);
    
    int mnR = oo, mxR = -oo, mnC = oo, mxC = -oo;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if(i % BLOCK == 0){
            array<int, 4> a = blocks[i / BLOCK].get();
            mxR = max(mxR, a[2]);
            mxC = max(mxC, a[3]);
            mnR = min(mnR, a[0]);
            mnC = min(mnC, a[1]);
        }
        else{
            mxR = max(mxR, mp[i].first);
            mxC = max(mxC, mp[i].second);
            mnR = min(mnR, mp[i].first);
            mnC = min(mnC, mp[i].second);
        }
        int r = mxR - mnR + 1;
        int c = mxC - mnC + 1;
        if(r * c == i + 1){
            ans++;
        }
        if(r * c - (i + 1) >= BLOCK){
            i = (i + BLOCK) / BLOCK * BLOCK - 1;
        }
    }
    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