Submission #769206

#	Time	Username	Problem	Language	Result	Execution time	Memory
769206		pashka	Seats (IOI18_seats)	C++14	0 / 100	4081 ms	152840 KiB

seats

#include "seats.h"
#include <set>
#include <iostream>
using namespace std;

int n, m;
vector<int> x;
vector<int> y;

vector<set<int>> xx;
vector<set<int>> yy;

struct segtree {
    int zeroSum = 0;
    int oper(int a, int b) {
        return max(a, b);
    }
    vector<int> sums;
    int size;
    void set(int i, int x, int n, int L, int R) {
        if (R == L + 1) {
            sums[n] = x;
            return;
        }
        int M = (L + R) >> 1;
        if (i < M) {
            set(i, x, 2 * n + 1, L, M);
        } else {
            set(i, x, 2 * n + 2, M, R);
        }
        sums[n] = oper(sums[2 * n + 1], sums[2 * n + 2]);
    }

    int getmax(int l, int r, int n, int L, int R) {
        if (l >= R || L >= r) return zeroSum;
        if (L >= l && R <= r) {
            return sums[n];
        }
        int M = (L + R) >> 1;
        return oper(getmax(l, r, 2 * n + 1, L, M), getmax(l, r, 2 * n + 2, M, R));
    }

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, zeroSum);
    }

    void init(vector<int> a) {
        int n = a.size();
        init(n);
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, zeroSum);
        for (int i = 0; i < n; i++) {
            sums[size - 1 + i] = a[i];
        }
        for (int i = size - 2; i >= 0; i--) {
            sums[i] = oper(sums[2 * i + 1], sums[2 * i + 2]);
        }
    }

    void set(int i, int x) {
        set(i, x, 0, 0, size);
    }

    int getmax(int l, int r) {
        return getmax(l, r, 0, 0, size);
    }
};

segtree minx, maxx, miny, maxy;


void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    x = R;
    y = C;
    n = H;
    m = W;
    maxx.init(x);
    for (auto &i : x) i = -i;
    minx.init(x);
    for (auto &i : x) i = -i;
    maxy.init(y);
    for (auto &i : y) i = -i;
    miny.init(y);
    for (auto &i : y) i = -i;
    xx.resize(n);
    yy.resize(m);
    for (int i = 0; i < n * m; i++) {
        xx[x[i]].insert(i);
        yy[y[i]].insert(i);
    }
}


int swap_seats(int a, int b) {
    xx[x[a]].erase(a);
    xx[x[b]].erase(b);
    yy[y[a]].erase(a);
    yy[y[b]].erase(b);
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    xx[x[a]].insert(a);
    xx[x[b]].insert(b);
    yy[y[a]].insert(a);
    yy[y[b]].insert(b);
    maxx.set(a, x[a]);
    minx.set(a, -x[a]);
    maxy.set(a, y[a]);
    miny.set(a, -y[a]);
    maxx.set(b, x[b]);
    minx.set(b, -x[b]);
    maxy.set(b, y[b]);
    miny.set(b, -y[b]);
    set<int> cand;
    for (int i = 0; i < n; i++) {
        if (xx[i].empty()) continue;
        int k = *xx[i].begin();
        if (k != 0) cand.insert(k);
    }
    for (int i = 0; i < m; i++) {
        if (yy[i].empty()) continue;
        int k = *yy[i].begin();
        if (k != 0) cand.insert(k);
    }
    int res = 1;
    for (int k : cand) {
        int s = (maxx.getmax(0, k) + minx.getmax(0, k) + 1) *
                (maxy.getmax(0, k) + miny.getmax(0, k) + 1);
//        cout << "! " << k << " " << s << "\n";
        if (s == k) {
            res++;
        }
    }
    return res;
}

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