oj.uz

Submission #218825

# Submission time Handle Problem Language Result Execution time Memory
218825 2020-04-02T19:30:49 Z IgorI Seats (IOI18_seats) C++17
100 / 100
 3497 ms 242420 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 131832 KB Output is correct
2 Correct 84 ms 131832 KB Output is correct
3 Correct 93 ms 131832 KB Output is correct
4 Correct 87 ms 132088 KB Output is correct
5 Correct 77 ms 131836 KB Output is correct
6 Correct 88 ms 131832 KB Output is correct
7 Correct 92 ms 131832 KB Output is correct
8 Correct 89 ms 131832 KB Output is correct
9 Correct 98 ms 131960 KB Output is correct
10 Correct 95 ms 131832 KB Output is correct
11 Correct 90 ms 131832 KB Output is correct
12 Correct 81 ms 131832 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 131832 KB Output is correct
2 Correct 84 ms 131832 KB Output is correct
3 Correct 93 ms 131832 KB Output is correct
4 Correct 87 ms 132088 KB Output is correct
5 Correct 77 ms 131836 KB Output is correct
6 Correct 88 ms 131832 KB Output is correct
7 Correct 92 ms 131832 KB Output is correct
8 Correct 89 ms 131832 KB Output is correct
9 Correct 98 ms 131960 KB Output is correct
10 Correct 95 ms 131832 KB Output is correct
11 Correct 90 ms 131832 KB Output is correct
12 Correct 81 ms 131832 KB Output is correct
13 Correct 132 ms 132472 KB Output is correct
14 Correct 143 ms 132472 KB Output is correct
15 Correct 115 ms 132600 KB Output is correct
16 Correct 100 ms 132916 KB Output is correct
17 Correct 125 ms 132472 KB Output is correct
18 Correct 128 ms 132600 KB Output is correct
19 Correct 119 ms 132472 KB Output is correct
20 Correct 113 ms 132728 KB Output is correct
21 Correct 100 ms 132572 KB Output is correct
22 Correct 104 ms 133288 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2368 ms 175964 KB Output is correct
2 Correct 1303 ms 176112 KB Output is correct
3 Correct 1352 ms 176016 KB Output is correct
4 Correct 1129 ms 175968 KB Output is correct
5 Correct 1239 ms 176416 KB Output is correct
6 Correct 1187 ms 176540 KB Output is correct
7 Correct 1257 ms 176420 KB Output is correct
8 Correct 1376 ms 176472 KB Output is correct
9 Correct 1309 ms 176348 KB Output is correct
10 Correct 1233 ms 176404 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 132616 KB Output is correct
2 Correct 247 ms 137508 KB Output is correct
3 Correct 1145 ms 176416 KB Output is correct
4 Correct 2370 ms 176632 KB Output is correct
5 Correct 1089 ms 188080 KB Output is correct
6 Correct 2355 ms 242420 KB Output is correct
7 Correct 1163 ms 195680 KB Output is correct
8 Correct 1369 ms 191736 KB Output is correct
9 Correct 1276 ms 192052 KB Output is correct
10 Correct 1231 ms 196264 KB Output is correct
11 Correct 1210 ms 215056 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 133364 KB Output is correct
2 Correct 172 ms 133368 KB Output is correct
3 Correct 230 ms 133364 KB Output is correct
4 Correct 297 ms 133492 KB Output is correct
5 Correct 430 ms 134200 KB Output is correct
6 Correct 1588 ms 189744 KB Output is correct
7 Correct 1817 ms 187824 KB Output is correct
8 Correct 1605 ms 189616 KB Output is correct
9 Correct 3003 ms 187696 KB Output is correct
10 Correct 1499 ms 187696 KB Output is correct
11 Correct 1522 ms 187696 KB Output is correct
12 Correct 1548 ms 187824 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 131832 KB Output is correct
2 Correct 84 ms 131832 KB Output is correct
3 Correct 93 ms 131832 KB Output is correct
4 Correct 87 ms 132088 KB Output is correct
5 Correct 77 ms 131836 KB Output is correct
6 Correct 88 ms 131832 KB Output is correct
7 Correct 92 ms 131832 KB Output is correct
8 Correct 89 ms 131832 KB Output is correct
9 Correct 98 ms 131960 KB Output is correct
10 Correct 95 ms 131832 KB Output is correct
11 Correct 90 ms 131832 KB Output is correct
12 Correct 81 ms 131832 KB Output is correct
13 Correct 132 ms 132472 KB Output is correct
14 Correct 143 ms 132472 KB Output is correct
15 Correct 115 ms 132600 KB Output is correct
16 Correct 100 ms 132916 KB Output is correct
17 Correct 125 ms 132472 KB Output is correct
18 Correct 128 ms 132600 KB Output is correct
19 Correct 119 ms 132472 KB Output is correct
20 Correct 113 ms 132728 KB Output is correct
21 Correct 100 ms 132572 KB Output is correct
22 Correct 104 ms 133288 KB Output is correct
23 Correct 2368 ms 175964 KB Output is correct
24 Correct 1303 ms 176112 KB Output is correct
25 Correct 1352 ms 176016 KB Output is correct
26 Correct 1129 ms 175968 KB Output is correct
27 Correct 1239 ms 176416 KB Output is correct
28 Correct 1187 ms 176540 KB Output is correct
29 Correct 1257 ms 176420 KB Output is correct
30 Correct 1376 ms 176472 KB Output is correct
31 Correct 1309 ms 176348 KB Output is correct
32 Correct 1233 ms 176404 KB Output is correct
33 Correct 141 ms 132616 KB Output is correct
34 Correct 247 ms 137508 KB Output is correct
35 Correct 1145 ms 176416 KB Output is correct
36 Correct 2370 ms 176632 KB Output is correct
37 Correct 1089 ms 188080 KB Output is correct
38 Correct 2355 ms 242420 KB Output is correct
39 Correct 1163 ms 195680 KB Output is correct
40 Correct 1369 ms 191736 KB Output is correct
41 Correct 1276 ms 192052 KB Output is correct
42 Correct 1231 ms 196264 KB Output is correct
43 Correct 1210 ms 215056 KB Output is correct
44 Correct 124 ms 133364 KB Output is correct
45 Correct 172 ms 133368 KB Output is correct
46 Correct 230 ms 133364 KB Output is correct
47 Correct 297 ms 133492 KB Output is correct
48 Correct 430 ms 134200 KB Output is correct
49 Correct 1588 ms 189744 KB Output is correct
50 Correct 1817 ms 187824 KB Output is correct
51 Correct 1605 ms 189616 KB Output is correct
52 Correct 3003 ms 187696 KB Output is correct
53 Correct 1499 ms 187696 KB Output is correct
54 Correct 1522 ms 187696 KB Output is correct
55 Correct 1548 ms 187824 KB Output is correct
56 Correct 207 ms 133364 KB Output is correct
57 Correct 370 ms 133372 KB Output is correct
58 Correct 636 ms 134012 KB Output is correct
59 Correct 2013 ms 192632 KB Output is correct
60 Correct 3497 ms 183160 KB Output is correct
61 Correct 1990 ms 182776 KB Output is correct
62 Correct 1710 ms 188628 KB Output is correct
63 Correct 3369 ms 186720 KB Output is correct
64 Correct 2355 ms 183792 KB Output is correct
65 Correct 2013 ms 182824 KB Output is correct
66 Correct 2135 ms 182968 KB Output is correct
67 Correct 2124 ms 187428 KB Output is correct
68 Correct 1728 ms 197132 KB Output is correct
69 Correct 3179 ms 206476 KB Output is correct