Submission #218825

#	Time	Username	Problem	Language	Result	Execution time	Memory
218825		IgorI	Seats (IOI18_seats)	C++17	100 / 100	3497 ms	242420 KiB

seats

#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>

using namespace std;

const int N = 3e6 + 55;

typedef pair<long long, int> T;

int n, m, k;
vector<vector<int> > p;
int x[N], y[N];
T tree[1 << 23];
long long push[1 << 23];

void Push(int V, int L, int R, int M)
{
    tree[2 * V + 1].first += push[V];
    push[2 * V + 1] += push[V];
    tree[2 * V + 2].first += push[V];
    push[2 * V + 2] += push[V];
    push[V] = 0;
}

void add(int l, int r, long long val, int L = 0, int R = (n - 2) * (m - 2), int V = 0)
{
    if (r <= L || R <= l)
        return;
    if (l <= L && R <= r)
    {
        tree[V].first += val;
        push[V] += val;
        return;
    }
    int M = (L + R) / 2;
    Push(V, L, R, M);
    add(l, r, val, L, M, 2 * V + 1);
    add(l, r, val, M, R, 2 * V + 2);
    tree[V].first = min(tree[2 * V + 1].first, tree[2 * V + 2].first);
    tree[V].second = 0;
    if (tree[2 * V + 1].first == tree[V].first) tree[V].second += tree[2 * V + 1].second;
    if (tree[2 * V + 2].first == tree[V].first) tree[V].second += tree[2 * V + 2].second;
}

void change_tile(int i, int j, int t)
{
    int x[4] = {p[i][j], p[i + 1][j], p[i + 1][j + 1], p[i][j + 1]};
    sort(x, x + 4);
    add(x[0], x[1], t);
    add(x[2], x[3], t * n * m);
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c)
{
    T kek = {0, 1};
    fill(tree, tree + (1 << 23), kek);
    k = h * w;
    n = h + 2;
    m = w + 2;
    for (int i = 0; i < n; i++)
    {
        vector<int> e(m, k);
        p.push_back(e);
    }
    int t = h * w;
    for (int i = 0; i < t; i++)
    {
        p[r[i] + 1][c[i] + 1] = i;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            x[p[i][j]] = i;
            y[p[i][j]] = j;
        }
    }
    for (int i = 0; i + 1 < n; i++)
    {
        for (int j = 0; j + 1 < m; j++)
        {
            change_tile(i, j, 1);
        }
    }
}

int get_cur()
{
    T func = tree[0];
    if (func.first == 4) return func.second;
    return 0;
}

int swap_seats(int a, int b)
{
    int i1 = x[a], j1 = y[a];
    int i2 = x[b], j2 = y[b];
    change_tile(i1 - 1, j1 - 1, -1);
    change_tile(i1 - 1, j1, -1);
    change_tile(i1, j1 - 1, -1);
    change_tile(i1, j1, -1);
    change_tile(i2 - 1, j2 - 1, -1);
    change_tile(i2 - 1, j2, -1);
    change_tile(i2, j2 - 1, -1);
    change_tile(i2, j2, -1);
    swap(p[i1][j1], p[i2][j2]);
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    change_tile(i1 - 1, j1 - 1, 1);
    change_tile(i1 - 1, j1, 1);
    change_tile(i1, j1 - 1, 1);
    change_tile(i1, j1, 1);
    change_tile(i2 - 1, j2 - 1, 1);
    change_tile(i2 - 1, j2, 1);
    change_tile(i2, j2 - 1, 1);
    change_tile(i2, j2, 1);
    return get_cur();
}

/*int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> r(n * m), c(n * m);
    for (int i = 0; i < n * m; i++)
    {
        cin >> r[i] >> c[i];
    }
    give_initial_chart(n, m, r, c);
    cout << get_cur() << "\n";
    for (int i = 0; i < q; i++)
    {
        int x, y;
        cin >> x >> y;
        cout << swap_seats(x, y) << "\n";
    }
}*/

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