oj.uz

Submission #809589

# Submission time Handle Problem Language Result Execution time Memory
809589 2023-08-06T02:25:36 Z becaido Seats (IOI18_seats) C++17
100 / 100
 2182 ms 165212 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 1e6 + 5;

int n, m;
int x[SIZE], y[SIZE];
vector<int> a[SIZE];
pair<int, int> d[SIZE];

pair<int, int> operator + (const pair<int, int> &l, const pair<int, int> &r) {
    return pair<int, int>(l.F + r.F, l.S + r.S);
}
pair<int, int>& operator += (pair<int, int> &l, const pair<int, int> &r) {
    return l = l + r;
}

struct Node {
    pair<int, int> mn, lazy;
    int cnt;
    Node() = default;
    Node operator + (const Node &r) const {
        Node re = Node();
        re.mn = min(mn, r.mn);
        re.cnt = (mn == re.mn ? cnt : 0) + (r.mn == re.mn ? r.cnt : 0);
        return re;
    }
} node[SIZE * 4];

void push(int pos, int l, int r) {
    node[pos].mn += node[pos].lazy;
    if (l < r) {
        node[lpos].lazy += node[pos].lazy;
        node[rpos].lazy += node[pos].lazy;
    }
    node[pos].lazy = {0, 0};
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    node[pos] = node[lpos] + node[rpos];
}

void build(int pos, int l, int r) {
    if (l == r) {
        node[pos].mn = d[l];
        node[pos].cnt = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    node[pos] = node[lpos] + node[rpos];
}
void upd(int pos, int l, int r, int L, int R, pair<int, int> x) {
    if (l == L && r == R) {
        node[pos].lazy += x;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid, x);
    else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
    else {
        upd(lpos, l, mid, L, mid, x);
        upd(rpos, mid + 1, r, mid + 1, R, x);
    }
    pull(pos, L, R);
}
void upd(int l, int r, pair<int, int> x) {
    if (l > r) return;
    upd(1, l, r, 0, n * m - 1, x);
}
int que() {
    push(1, 0, n * m - 1);
    if (node[1].mn == make_pair(4, 0)) return node[1].cnt;
    return 0;
}

void add(int i, int j, int delta, bool pre = 0) {
    vector<int> t;
    FOR (di, 0, 1) FOR (dj, 0, 1) {
        if (min(i + di, j + dj) < 0 || i + di >= n || j + dj >= m) t.pb(n * m);
        else t.pb(a[i + di][j + dj]);
    }
    sort(t.begin(), t.end());
    if (pre) {
        d[t[0]] += {delta, 0};
        d[t[1]] += {-delta, 0};
        d[t[2]] += {0, delta};
        d[t[3]] += {0, -delta};
        return;
    }
    upd(t[0], t[1] - 1, {delta, 0});
    upd(t[2], t[3] - 1, {0, delta});
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = H, m = W;
    FOR (i, 0, n - 1) a[i].resize(m);
    FOR (i, 0, n * m - 1) {
        tie(x[i], y[i]) = make_pair(R[i], C[i]);
        a[x[i]][y[i]] = i;
    }
    FOR (i, -1, n - 1) FOR (j, -1, m - 1) add(i, j, 1, 1);
    FOR (i, 1, n * m - 1) d[i] += d[i - 1];
    build(1, 0, n * m - 1);
}

int swap_seats(int l, int r) {
    FOR (dx, -1, 0) FOR (dy, -1, 0) {
        add(x[l] + dx, y[l] + dy, -1);
        add(x[r] + dx, y[r] + dy, -1);
    }
    swap(a[x[l]][y[l]], a[x[r]][y[r]]);
    swap(x[l], x[r]), swap(y[l], y[r]);
    FOR (dx, -1, 0) FOR (dy, -1, 0) {
        add(x[l] + dx, y[l] + dy, 1);
        add(x[r] + dx, y[r] + dy, 1);
    }
    return que();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 102176 KB Output is correct
2 Correct 92 ms 102236 KB Output is correct
3 Correct 89 ms 102176 KB Output is correct
4 Correct 80 ms 102180 KB Output is correct
5 Correct 73 ms 102204 KB Output is correct
6 Correct 88 ms 102140 KB Output is correct
7 Correct 95 ms 102244 KB Output is correct
8 Correct 84 ms 102164 KB Output is correct
9 Correct 88 ms 102208 KB Output is correct
10 Correct 97 ms 102224 KB Output is correct
11 Correct 94 ms 102328 KB Output is correct
12 Correct 74 ms 102252 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 102176 KB Output is correct
2 Correct 92 ms 102236 KB Output is correct
3 Correct 89 ms 102176 KB Output is correct
4 Correct 80 ms 102180 KB Output is correct
5 Correct 73 ms 102204 KB Output is correct
6 Correct 88 ms 102140 KB Output is correct
7 Correct 95 ms 102244 KB Output is correct
8 Correct 84 ms 102164 KB Output is correct
9 Correct 88 ms 102208 KB Output is correct
10 Correct 97 ms 102224 KB Output is correct
11 Correct 94 ms 102328 KB Output is correct
12 Correct 74 ms 102252 KB Output is correct
13 Correct 143 ms 102640 KB Output is correct
14 Correct 162 ms 102648 KB Output is correct
15 Correct 100 ms 102572 KB Output is correct
16 Correct 96 ms 102920 KB Output is correct
17 Correct 122 ms 102644 KB Output is correct
18 Correct 133 ms 102716 KB Output is correct
19 Correct 129 ms 102648 KB Output is correct
20 Correct 114 ms 102764 KB Output is correct
21 Correct 99 ms 102680 KB Output is correct
22 Correct 95 ms 102940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 137868 KB Output is correct
2 Correct 475 ms 138276 KB Output is correct
3 Correct 436 ms 138528 KB Output is correct
4 Correct 441 ms 138264 KB Output is correct
5 Correct 446 ms 138200 KB Output is correct
6 Correct 460 ms 138340 KB Output is correct
7 Correct 459 ms 138280 KB Output is correct
8 Correct 451 ms 138256 KB Output is correct
9 Correct 433 ms 138344 KB Output is correct
10 Correct 430 ms 138188 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 102628 KB Output is correct
2 Correct 163 ms 105556 KB Output is correct
3 Correct 425 ms 137832 KB Output is correct
4 Correct 622 ms 138252 KB Output is correct
5 Correct 493 ms 138108 KB Output is correct
6 Correct 666 ms 165212 KB Output is correct
7 Correct 453 ms 137812 KB Output is correct
8 Correct 464 ms 137860 KB Output is correct
9 Correct 445 ms 138004 KB Output is correct
10 Correct 453 ms 138592 KB Output is correct
11 Correct 473 ms 149556 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 103284 KB Output is correct
2 Correct 223 ms 103304 KB Output is correct
3 Correct 320 ms 103292 KB Output is correct
4 Correct 377 ms 103332 KB Output is correct
5 Correct 532 ms 103796 KB Output is correct
6 Correct 1046 ms 137764 KB Output is correct
7 Correct 1072 ms 138216 KB Output is correct
8 Correct 1043 ms 138276 KB Output is correct
9 Correct 1347 ms 137848 KB Output is correct
10 Correct 963 ms 137864 KB Output is correct
11 Correct 982 ms 137792 KB Output is correct
12 Correct 961 ms 137796 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 102176 KB Output is correct
2 Correct 92 ms 102236 KB Output is correct
3 Correct 89 ms 102176 KB Output is correct
4 Correct 80 ms 102180 KB Output is correct
5 Correct 73 ms 102204 KB Output is correct
6 Correct 88 ms 102140 KB Output is correct
7 Correct 95 ms 102244 KB Output is correct
8 Correct 84 ms 102164 KB Output is correct
9 Correct 88 ms 102208 KB Output is correct
10 Correct 97 ms 102224 KB Output is correct
11 Correct 94 ms 102328 KB Output is correct
12 Correct 74 ms 102252 KB Output is correct
13 Correct 143 ms 102640 KB Output is correct
14 Correct 162 ms 102648 KB Output is correct
15 Correct 100 ms 102572 KB Output is correct
16 Correct 96 ms 102920 KB Output is correct
17 Correct 122 ms 102644 KB Output is correct
18 Correct 133 ms 102716 KB Output is correct
19 Correct 129 ms 102648 KB Output is correct
20 Correct 114 ms 102764 KB Output is correct
21 Correct 99 ms 102680 KB Output is correct
22 Correct 95 ms 102940 KB Output is correct
23 Correct 610 ms 137868 KB Output is correct
24 Correct 475 ms 138276 KB Output is correct
25 Correct 436 ms 138528 KB Output is correct
26 Correct 441 ms 138264 KB Output is correct
27 Correct 446 ms 138200 KB Output is correct
28 Correct 460 ms 138340 KB Output is correct
29 Correct 459 ms 138280 KB Output is correct
30 Correct 451 ms 138256 KB Output is correct
31 Correct 433 ms 138344 KB Output is correct
32 Correct 430 ms 138188 KB Output is correct
33 Correct 129 ms 102628 KB Output is correct
34 Correct 163 ms 105556 KB Output is correct
35 Correct 425 ms 137832 KB Output is correct
36 Correct 622 ms 138252 KB Output is correct
37 Correct 493 ms 138108 KB Output is correct
38 Correct 666 ms 165212 KB Output is correct
39 Correct 453 ms 137812 KB Output is correct
40 Correct 464 ms 137860 KB Output is correct
41 Correct 445 ms 138004 KB Output is correct
42 Correct 453 ms 138592 KB Output is correct
43 Correct 473 ms 149556 KB Output is correct
44 Correct 178 ms 103284 KB Output is correct
45 Correct 223 ms 103304 KB Output is correct
46 Correct 320 ms 103292 KB Output is correct
47 Correct 377 ms 103332 KB Output is correct
48 Correct 532 ms 103796 KB Output is correct
49 Correct 1046 ms 137764 KB Output is correct
50 Correct 1072 ms 138216 KB Output is correct
51 Correct 1043 ms 138276 KB Output is correct
52 Correct 1347 ms 137848 KB Output is correct
53 Correct 963 ms 137864 KB Output is correct
54 Correct 982 ms 137792 KB Output is correct
55 Correct 961 ms 137796 KB Output is correct
56 Correct 272 ms 103376 KB Output is correct
57 Correct 501 ms 103384 KB Output is correct
58 Correct 770 ms 103652 KB Output is correct
59 Correct 1498 ms 137800 KB Output is correct
60 Correct 2182 ms 137816 KB Output is correct
61 Correct 1342 ms 137756 KB Output is correct
62 Correct 1164 ms 137744 KB Output is correct
63 Correct 2039 ms 137676 KB Output is correct
64 Correct 1550 ms 137696 KB Output is correct
65 Correct 1389 ms 137680 KB Output is correct
66 Correct 1619 ms 137736 KB Output is correct
67 Correct 1562 ms 138464 KB Output is correct
68 Correct 1229 ms 144080 KB Output is correct
69 Correct 1719 ms 149424 KB Output is correct