Submission #964398

#	Time	Username	Problem	Language	Result	Execution time	Memory
964398		BestCrazyNoob	Seats (IOI18_seats)	C++17	0 / 100	4050 ms	32300 KiB

seats

#include "seats.h"
#include <cassert>
#include <map>

using namespace std;

constexpr int BLOCK = 2048; // TODO 1024
constexpr int INF = 1e9;

int n_blocks;
vector<int> v, prefMax, prefMin, suffAns;
// for each block
vector<map<int, vector<int>>> needMinFix, needMaxFix;

void compute(int block_i) {
    const int begin = block_i*BLOCK, end = begin+BLOCK;
    prefMax[begin] = v[begin];
    prefMin[begin] = v[begin];
    for (int i = begin+1; i < end; i++) {
        prefMax[i] = max(prefMax[i-1], v[i]);
        prefMin[i] = min(prefMin[i-1], v[i]);
    }
    needMinFix[block_i].clear();
    needMaxFix[block_i].clear();
    // Compute ans and need
    for (int i = begin; i < end; i++) {
        suffAns[i] = prefMax[i] - prefMin[i] == i;
        needMinFix[block_i][prefMax[i] - i].push_back(i);
        needMaxFix[block_i][prefMin[i] + i].push_back(i);
    }
    for (int i = end-2; i >= begin; i--) {
        suffAns[i] += suffAns[i+1];
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    assert(H == 1);
    n_blocks = (W + BLOCK-1) / BLOCK;
    ::v = C;
    v.resize(n_blocks*BLOCK, INF);

    prefMax.resize(n_blocks*BLOCK);
    prefMin.resize(n_blocks*BLOCK);
    suffAns.resize(n_blocks*BLOCK);
    needMinFix.resize(n_blocks);
    needMaxFix.resize(n_blocks);
    for (int i = 0; i < n_blocks; i++) compute(i);
}

int countRange(vector<int> v, int l, int r) {
    return lower_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
}

int swap_seats(int a, int b) {
    // update in O(BLOCK log BLOCK)
    swap(v[a], v[b]);
    compute(a / BLOCK);
    compute(b / BLOCK);
    // query in O(W/BLOCK log BLOCK)
    int currMX = -1, currMN = INF, ans = 0;
    for (int i = 0; i < n_blocks; i++) {
        const int start = i*BLOCK, end = start+BLOCK;
        int low, high;
        
        // nextMX
        low = start-1, high = end;
        while (low+1 < high) {
            int mid = (low+high)/2;
            if (prefMax[mid] < currMX) low = mid;
            else high = mid;
        }
        const int nextMX = low+1;
        
        // nextMN
        low = start-1, high = end;
        while (low+1 < high) {
            int mid = (low+high)/2;
            if (prefMin[mid] > currMN) low = mid;
            else high = mid;
        }
        const int nextMN = low+1;
        if (start <= currMX - currMN && currMX - currMN < min(nextMX, nextMN)) ans++;
        if (nextMX < nextMN) {
            ans += countRange(needMinFix[i][currMN], nextMX, nextMN);
        } else if (nextMN < end) {
            ans += countRange(needMaxFix[i][currMX], nextMN, nextMX);
        }
        if (max(nextMN, nextMX) < end) ans += suffAns[max(nextMN, nextMX)];
        currMN = min(currMN, prefMin[end-1]);
        currMX = max(currMX, prefMax[end-1]);
    }
    // ans++; // total match??
    return ans;
}

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