Submission #777236

#	Time	Username	Problem	Language	Result	Execution time	Memory
777236		GusterGoose27	Seats (IOI18_seats)	C++17	0 / 100	171 ms	35036 KiB

seats

#pragma GCC optimize("Ofast")

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef array<int, 4> ar4;

const int MAXN = 1e6+5;
const int BLOCK = 1000;

int n;
int points[MAXN];
int num_blocks;
pii rangeval[BLOCK];
pii interval[MAXN];
map<int, vector<int>> occs[BLOCK][2];

void combine(pii &a, pii &b) {
    a.first = min(a.first, b.first);
    a.second = max(a.second, b.second);
}

void expand(pii &in, int v) {
    in.first = min(in.first, v);
    in.second = max(in.second, v);
}

void make(int i) {
    occs[i][0].clear();
    occs[i][1].clear();
    pii cur_int(n, 0);
    for (int j = i*BLOCK; j < min((i+1)*BLOCK, n); j++) {
        expand(cur_int, points[j]);
        interval[j] = cur_int;
    }
    rangeval[i] = cur_int;
    for (int j = i*BLOCK; j < min((i+1)*BLOCK, n); j++) {
        occs[i][0][interval[j].second-j+1].push_back(interval[j].first);
        occs[i][1][interval[j].first+j-1].push_back(interval[j].second);
    }
}

int get_ans(pii cur_int, int i) {
    int ans = 0;
    // >= cur_int.first, r
    if (occs[i][0].find(cur_int.second) != occs[i][0].end()) {
        vector<int> &v = occs[i][0][cur_int.second];
        int mn = -1;
        int mx = v.size();
        while (mx > mn+1) {
            int cur = (mn+mx)/2;
            if (v[cur] >= cur_int.first) mx = cur;
            else mn = cur;
        }
        ans += v.size()-mx;
    } // <= second, at first
    if (occs[i][1].find(cur_int.first) != occs[i][1].end()) {
        vector<int> &v = occs[i][1][cur_int.first];
        int mn = -1;
        int mx = v.size();
        while (mx > mn+1) {
            int cur = (mn+mx)/2;
            if (v[cur] <= cur_int.second) mn = cur;
            else mx = cur;
        }
        ans += mx;
    }
    return ans;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = W;
    assert(H == 1);
    num_blocks = (n+BLOCK-1)/BLOCK;
    for (int i = 0; i < n; i++) {
        points[i] = C[i];
        assert(R[i] == 0);
    }
    for (int i = 0; i < num_blocks; i++) make(i);
}

int swap_seats(int a, int b) {
    swap(points[a], points[b]);
    make(a/BLOCK);
    if (a/BLOCK != b/BLOCK) make(b/BLOCK);
    pii vals(points[0], points[0]);
    int ans = 0;
    for (int i = 0; i < num_blocks; i++) {
        ans += get_ans(vals, i);
        combine(vals, rangeval[i]);
    }
    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