Submission #1069553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069553		onbert	Seats (IOI18_seats)	C++17	25 / 100	1534 ms	52820 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
    short xmn, xmx, ymn, ymx;
    bool operator == (const node &b) const {
        return (xmn==b.xmn && xmx==b.xmx && ymn==b.ymn && ymx==b.ymx);
    }
};
const int maxN = 1e6 + 5, INF = 2000;
int N, n, m;
pair<short, short> pos[maxN];

node seg[maxN*4];
void build(int id, int l, int r) {
    if (l==r) {
        seg[id] = {pos[l].first, pos[l].first, pos[l].second, pos[l].second};
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
    seg[id] = {min(seg[id*2].xmn, seg[id*2+1].xmn), max(seg[id*2].xmx, seg[id*2+1].xmx), min(seg[id*2].ymn, seg[id*2+1].ymn), max(seg[id*2].ymx, seg[id*2+1].ymx)};
}
void update(int id, int l, int r, int target) {
    if (r<target || target<l) return;
    if (l==r) {
        seg[id] = {pos[l].first, pos[l].first, pos[l].second, pos[l].second};
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target); update(id*2+1, mid+1, r, target);
    seg[id] = {min(seg[id*2].xmn, seg[id*2+1].xmn), max(seg[id*2].xmx, seg[id*2+1].xmx), min(seg[id*2].ymn, seg[id*2+1].ymn), max(seg[id*2].ymx, seg[id*2+1].ymx)};
}
node qry(int id, int l, int r, int findl, int findr) {
    if (r<findl || findr<l) return {INF, -INF, INF, -INF};
    if (findl<=l && r<=findr) return seg[id];
    int mid = (l+r)/2;
    node x = qry(id*2, l, mid, findl, findr);
    node y = qry(id*2+1, mid+1, r, findl, findr);
    return {min(x.xmn, y.xmn), max(x.xmx, y.xmx), min(x.ymn, y.ymn), max(x.ymx, y.ymx)};
}

void give_initial_chart(int nn, int mm, vector<int> R, vector<int> C) {
    n = nn, m = mm, N = n * m;
    for (int i=0;i<N;i++) pos[i] = {R[i], C[i]};
    build(1, 0, N-1);
}

int swap_seats(int u, int v) {
    if (n+m >= 2005) return 69;
    swap(pos[u], pos[v]);
    update(1, 0, N-1, u); update(1, 0, N-1, v);
    int ans = 0;
    node cur = {pos[0].first, pos[0].first, pos[0].second, pos[0].second};
    while (true) {
        int k = (cur.xmx - cur.xmn + 1) * (cur.ymx - cur.ymn + 1) - 1;
        // cout << cur.xmx << " " << cur.xmn << " " << cur.ymn << " " << cur.ymx << endl;
        // cout << k << endl;
        node thing = qry(1, 0, N-1, 0, k);
        if (thing == cur) {
            ans++;
            if (k==N-1) break;
            cur = {min(pos[k+1].first, thing.xmn), max(pos[k+1].first, thing.xmx), min(pos[k+1].second, thing.ymn), max(pos[k+1].second, thing.ymx)};
        } else {
            cur = thing;
        }
    }
    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