oj.uz

Submission #852387

# Submission time Handle Problem Language Result Execution time Memory
852387 2023-09-21T17:54:26 Z jerzyk Seats (IOI18_seats) C++17
100 / 100
 2161 ms 120704 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "seats.h"

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<20;
int n, val = 4, m, nm;
int drz[2 * N], il[2 * N], laz[2 * N];
vector<int> tab[N];
pair<int, int> wh[N];

void Change(int v, int p, int k, int pz, int kz, int x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz[v] += x; laz[v] += x;
        return;
    }
    int m = (p + k) / 2;
    Change(v * 2, p, m, pz, kz, x);
    Change(v * 2 + 1, m + 1, k, pz, kz, x);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]); il[v] = 0;
    if(drz[v] == drz[v * 2]) il[v] += il[v * 2];
    if(drz[v] == drz[v * 2 + 1]) il[v] += il[v * 2 + 1];
    drz[v] += laz[v];
}

inline void CH(int a, int b, int x)
{if(a <= b) Change(1, 0, N - 1, a, b, x);}

inline void HN(vector<vector<int>> v, int x)
{
    if(v[0][0] > v[1][1]) swap(v[0][0], v[1][1]);
    if(v[0][1] > v[1][0]) swap(v[0][1], v[1][0]);
    if(v[0][1] < v[0][0])
        {swap(v[0][0], v[0][1]); swap(v[1][0], v[1][1]);}
    //cout << "\n" << v[0][0] << " " << v[0][1] << "\n";
    //cout << v[1][0] << " " << v[1][1] << "\n";
    CH(v[0][0], min(v[0][1], v[1][1]) - 1, x);
    CH(min(v[1][1], v[1][0]), max(v[1][1], v[1][0]) - 1, x * 5);
}

inline void HLP(int i, int j, int d)
{
    vector<int> x(2, 0); vector<vector<int>> v(2, x);
    v[0][0] = tab[i][j]; v[0][1] = tab[i][j + 1]; v[1][0] = tab[i + 1][j]; v[1][1] = tab[i + 1][j + 1];
    HN(v, d);
}

void Query(int a, int b)
{
    ++a; ++b;
    pair<int, int> x = wh[a], y = wh[b];
    vector<pair<int, int>> pos;
    for(int i = x.st - 1; i <= x.st; ++i) for(int j = x.nd - 1; j <= x.nd; ++j) pos.pb(make_pair(i, j));
    for(int i = y.st - 1; i <= y.st; ++i) for(int j = y.nd - 1; j <= y.nd; ++j) pos.pb(make_pair(i, j));
    sort(pos.begin(), pos.end());
    for(int i = 0; i < (int)pos.size(); ++i)
        if(i == 0 || pos[i] != pos[i - 1]) HLP(pos[i].st, pos[i].nd, -1);
    swap(tab[x.st][x.nd], tab[y.st][y.nd]);
    wh[a] = y; wh[b] = x;
    for(int i = 0; i < (int)pos.size(); ++i)
        if(i == 0 || pos[i] != pos[i - 1]) HLP(pos[i].st, pos[i].nd, 1);
}

int Ans()
{
    int ans = 0;
    if(drz[1] == val) ans += il[1];
    return ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
    n = H; m = W; nm = n * m; vector<int> p1(m + 5, 0), p2(m + 5, nm + 10);
    p1[0] = nm + 10; p1[m + 1] = nm + 10; tab[0] = p2; tab[n + 1] = p2;
    for(int i = 1; i <= n; ++i) tab[i] = p1;
    for(int i = N; i < 2 * N; ++i) il[i] = 1;
    drz[N] = N; for(int i = N + nm + 1; i < 2 * N; ++i) drz[i] = N;
    for(int v = N - 1; v > 0; --v)
    {
        drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
        if(drz[v] == drz[v * 2]) il[v] += il[v * 2];
        if(drz[v] == drz[v * 2 + 1]) il[v] += il[v * 2 + 1];
    }
    for(int i = 1; i <= nm; ++i)
    {
        tab[R[i - 1] + 1][C[i - 1] + 1] = i;
        wh[i] = make_pair(R[i - 1] + 1, C[i - 1] + 1);
    }
    vector<int> x(2, 0); vector<vector<int>> v(2, x);
    for(int i = 0; i <= n; ++i)
    {
        for(int j = 0; j <= m; ++j)
        {
            v[0][0] = tab[i][j]; v[0][1] = tab[i][j + 1]; v[1][0] = tab[i + 1][j]; v[1][1] = tab[i + 1][j + 1];
            HN(v, 1);
        }
    }
    //cout << "XD " << Ans() << "\n";
}

int swap_seats(int a, int b) 
{
    Query(a, b);
    return Ans();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47504 KB Output is correct
2 Correct 167 ms 47812 KB Output is correct
3 Correct 160 ms 47584 KB Output is correct
4 Correct 103 ms 47452 KB Output is correct
5 Correct 90 ms 47452 KB Output is correct
6 Correct 166 ms 49624 KB Output is correct
7 Correct 186 ms 49496 KB Output is correct
8 Correct 181 ms 49608 KB Output is correct
9 Correct 156 ms 47580 KB Output is correct
10 Correct 140 ms 47452 KB Output is correct
11 Correct 165 ms 49588 KB Output is correct
12 Correct 93 ms 47624 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47504 KB Output is correct
2 Correct 167 ms 47812 KB Output is correct
3 Correct 160 ms 47584 KB Output is correct
4 Correct 103 ms 47452 KB Output is correct
5 Correct 90 ms 47452 KB Output is correct
6 Correct 166 ms 49624 KB Output is correct
7 Correct 186 ms 49496 KB Output is correct
8 Correct 181 ms 49608 KB Output is correct
9 Correct 156 ms 47580 KB Output is correct
10 Correct 140 ms 47452 KB Output is correct
11 Correct 165 ms 49588 KB Output is correct
12 Correct 93 ms 47624 KB Output is correct
13 Correct 82 ms 48012 KB Output is correct
14 Correct 94 ms 49988 KB Output is correct
15 Correct 63 ms 50012 KB Output is correct
16 Correct 51 ms 48248 KB Output is correct
17 Correct 78 ms 48212 KB Output is correct
18 Correct 69 ms 47996 KB Output is correct
19 Correct 68 ms 50020 KB Output is correct
20 Correct 62 ms 48208 KB Output is correct
21 Correct 51 ms 48132 KB Output is correct
22 Correct 53 ms 50268 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 77372 KB Output is correct
2 Correct 732 ms 77400 KB Output is correct
3 Correct 711 ms 77392 KB Output is correct
4 Correct 617 ms 77160 KB Output is correct
5 Correct 672 ms 77188 KB Output is correct
6 Correct 592 ms 77396 KB Output is correct
7 Correct 662 ms 77448 KB Output is correct
8 Correct 729 ms 77196 KB Output is correct
9 Correct 731 ms 77396 KB Output is correct
10 Correct 687 ms 77440 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 47960 KB Output is correct
2 Correct 134 ms 53852 KB Output is correct
3 Correct 654 ms 93288 KB Output is correct
4 Correct 1366 ms 93432 KB Output is correct
5 Correct 609 ms 109184 KB Output is correct
6 Correct 1346 ms 120704 KB Output is correct
7 Correct 677 ms 97808 KB Output is correct
8 Correct 718 ms 93872 KB Output is correct
9 Correct 725 ms 91592 KB Output is correct
10 Correct 686 ms 97300 KB Output is correct
11 Correct 657 ms 111896 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 48772 KB Output is correct
2 Correct 1136 ms 48380 KB Output is correct
3 Correct 823 ms 48552 KB Output is correct
4 Correct 508 ms 48308 KB Output is correct
5 Correct 436 ms 50780 KB Output is correct
6 Correct 1008 ms 91396 KB Output is correct
7 Correct 1232 ms 93520 KB Output is correct
8 Correct 1004 ms 93508 KB Output is correct
9 Correct 1952 ms 93564 KB Output is correct
10 Correct 1026 ms 93528 KB Output is correct
11 Correct 1020 ms 92628 KB Output is correct
12 Correct 973 ms 91260 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47504 KB Output is correct
2 Correct 167 ms 47812 KB Output is correct
3 Correct 160 ms 47584 KB Output is correct
4 Correct 103 ms 47452 KB Output is correct
5 Correct 90 ms 47452 KB Output is correct
6 Correct 166 ms 49624 KB Output is correct
7 Correct 186 ms 49496 KB Output is correct
8 Correct 181 ms 49608 KB Output is correct
9 Correct 156 ms 47580 KB Output is correct
10 Correct 140 ms 47452 KB Output is correct
11 Correct 165 ms 49588 KB Output is correct
12 Correct 93 ms 47624 KB Output is correct
13 Correct 82 ms 48012 KB Output is correct
14 Correct 94 ms 49988 KB Output is correct
15 Correct 63 ms 50012 KB Output is correct
16 Correct 51 ms 48248 KB Output is correct
17 Correct 78 ms 48212 KB Output is correct
18 Correct 69 ms 47996 KB Output is correct
19 Correct 68 ms 50020 KB Output is correct
20 Correct 62 ms 48208 KB Output is correct
21 Correct 51 ms 48132 KB Output is correct
22 Correct 53 ms 50268 KB Output is correct
23 Correct 1321 ms 77372 KB Output is correct
24 Correct 732 ms 77400 KB Output is correct
25 Correct 711 ms 77392 KB Output is correct
26 Correct 617 ms 77160 KB Output is correct
27 Correct 672 ms 77188 KB Output is correct
28 Correct 592 ms 77396 KB Output is correct
29 Correct 662 ms 77448 KB Output is correct
30 Correct 729 ms 77196 KB Output is correct
31 Correct 731 ms 77396 KB Output is correct
32 Correct 687 ms 77440 KB Output is correct
33 Correct 94 ms 47960 KB Output is correct
34 Correct 134 ms 53852 KB Output is correct
35 Correct 654 ms 93288 KB Output is correct
36 Correct 1366 ms 93432 KB Output is correct
37 Correct 609 ms 109184 KB Output is correct
38 Correct 1346 ms 120704 KB Output is correct
39 Correct 677 ms 97808 KB Output is correct
40 Correct 718 ms 93872 KB Output is correct
41 Correct 725 ms 91592 KB Output is correct
42 Correct 686 ms 97300 KB Output is correct
43 Correct 657 ms 111896 KB Output is correct
44 Correct 1087 ms 48772 KB Output is correct
45 Correct 1136 ms 48380 KB Output is correct
46 Correct 823 ms 48552 KB Output is correct
47 Correct 508 ms 48308 KB Output is correct
48 Correct 436 ms 50780 KB Output is correct
49 Correct 1008 ms 91396 KB Output is correct
50 Correct 1232 ms 93520 KB Output is correct
51 Correct 1004 ms 93508 KB Output is correct
52 Correct 1952 ms 93564 KB Output is correct
53 Correct 1026 ms 93528 KB Output is correct
54 Correct 1020 ms 92628 KB Output is correct
55 Correct 973 ms 91260 KB Output is correct
56 Correct 1364 ms 49056 KB Output is correct
57 Correct 1901 ms 51364 KB Output is correct
58 Correct 561 ms 49584 KB Output is correct
59 Correct 1282 ms 94308 KB Output is correct
60 Correct 2161 ms 94452 KB Output is correct
61 Correct 1229 ms 94280 KB Output is correct
62 Correct 1028 ms 102244 KB Output is correct
63 Correct 2133 ms 99468 KB Output is correct
64 Correct 1414 ms 95844 KB Output is correct
65 Correct 1201 ms 94564 KB Output is correct
66 Correct 1308 ms 94564 KB Output is correct
67 Correct 1356 ms 98156 KB Output is correct
68 Correct 1173 ms 105620 KB Output is correct
69 Correct 1998 ms 113780 KB Output is correct