oj.uz

Submission #759143

# Submission time Handle Problem Language Result Execution time Memory
759143 2023-06-15T19:43:09 Z drdilyor Seats (IOI18_seats) C++17
100 / 100
 1399 ms 200248 KB 
#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
 
int h, w;
std::vector<int> r, c;
vector<vector<int>> arr;
 
struct Fenwick {
    int n, m;
    vector<vector<ll>> t;
    Fenwick() = default;
    Fenwick(int n, int m) : n(n), m(m), t(n, vector<ll>(m)) {}
    ll sum(int r, int c) {
        ll s = 0;
        for (int i = r; i >= 0; i = (i&(i+1))-1)
            for (int j = c; j >= 0; j = (j&(j+1))-1)
                s += t[i][j];
        return s;
    }
    ll sum(int r1, int c1, int r2, int c2) {
        return sum(r2, c2) + sum(r1-1, c1-1) - sum(r1-1, c2) - sum(r2, c1-1);
    }
    void inc(int r, int c, int d) {
        for (; r < n; r |= r+1)
            for (int i = c; i < m; i |= i+1)
                t[r][i] += d;
    }
};
 
Fenwick ft;

int nextPower2(int n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return 1+n;
}


struct SegmentTree {
    struct node {
        int cnt = 1;
        int min = 0;
        int lz = 0;
    };
    int n;
    vector<node> t;
    SegmentTree()= default;
    void init(int n) {
        this->n = n;
        t.assign(this->n*4, {});
        build(1, 0, n-1);
    }
    void build(int v, int tl, int tr) {
        if (tl == tr) return void(t[v] = node{.cnt=1, .min=0});
        int mid = (tl+tr) / 2;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
    void apply(int v, int x) {
        t[v].lz += x;
        t[v].min += x;
    }
    void push(int v) {
        if (t[v].lz) {
            apply(v*2, t[v].lz);
            apply(v*2+1, t[v].lz);
            t[v].lz = 0;
        }
    }
    node merge(const node& a, const node&b) {
        node res{.min = min(a.min, b.min)};
        if (a.min == b.min) res.cnt = a.cnt + b.cnt;
        else if (a.min< b.min) res.cnt = a.cnt;
        else res.cnt = b.cnt;
        return res;
    }
    void update(int l, int r, int x, int v, int tl, int tr) {
        if (tl > tr) return;
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) {
            apply(v, x);
            return;
        }
        push(v);
        int mid = (tl+tr) / 2;
        update(l, r, x, v*2, tl, mid);
        update(l, r, x, v*2+1, mid+1, tr);
        t[v] = merge(t[v*2], t[v*2+1]);
    }
    void update(int l, int r, int x) {
        update(l, r, x, 1, 0, n-1);
    }
    int query() {
        return t[1].cnt;
    }
    node query(int l, int r, int v, int tl, int tr) {
        if (r < tl || tr < l) return {.cnt=0, .min=int(1e9)};
        if (l <= tl && tr <= r) return t[v];
        push(v);
        int mid = (tl+tr) / 2;
        return merge(query(l, r, v*2, tl, mid), query(l, r, v*2+1, mid+1, tr));
    }
    node query(int l, int r) {
        return query(l, r, 1, 0, n-1);
    }
};

 
SegmentTree pot;
vector<int> raw;
 
int add(int i) {
    if (i == 0) return 0;
    int cnt_1 = 0, cnt_3 = 0;
    int row = r[i], col = c[i];
    for (int ir = 0; ir < 2; ir++) {
        for (int ic = 0; ic < 2; ic++) {
            int in = 0;
            for (int iir = 0; iir < 2; iir++) {
                for (int iic = 0; iic < 2; iic++) {
                    int nrow = row - ir + iir;
                    int ncol = col - ic + iic;
                    if (clamp(nrow,0, h-1) == nrow && clamp(ncol, 0, w-1) == ncol)
                        if (arr[nrow][ncol] < i) in++;
                }
            }
            if (in == 0) cnt_1++;
            if (in == 1) cnt_1--;
            if (in == 2) cnt_3++;
            if (in == 3) cnt_3--;
        }
    }
    return cnt_1 + cnt_3;
};

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h = H;
    w = W;
    r = R;
    c = C;
    arr = vector(H, vector<int>(W, 0));
    ft = Fenwick(H, W);
    for (int i = 0; i < H * W; i++) {
        arr[r[i]][c[i]] = i;
        ft.inc(r[i], c[i], i);
    }
    raw.assign(h*w, 0);
    pot.init(h*w);

    for (int i = 0; i < h*w; i++) {
        int x = add(i);
        pot.update(i, h*w-1, x - raw[i]);
        raw[i] = x;
    }

}

int swap_seats(int a, int b) {
    ft.inc(r[a], c[a], -a +b);
    ft.inc(r[b], c[b], -b +a);
    swap(arr[r[a]][c[a]], arr[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);

    auto update = [&](int i, int j) {
        if (clamp(i, 0,h-1) != i || clamp(j, 0, w-1) != j)return;
        int num = arr[i][j];
        int x = add(num);
        pot.update(num, h*w - 1, x - raw[num]);
        raw[num] = x;
    };
    for (int di = -1; di <= 1; di++) {
        for (int dj = -1; dj <= 1; dj++) {
            update(r[a] + di, c[a] + dj);
            update(r[b] + di, c[b] + dj);
        }
    }

#ifdef ONPC
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            cout << arr[i][j] << " \n"[j == w-1];
    for (int i : raw) cout << i << ' '; cout << endl;
#endif

    int ans = pot.query();
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 432 KB Output is correct
2 Correct 14 ms 420 KB Output is correct
3 Correct 18 ms 428 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 7 ms 392 KB Output is correct
6 Correct 18 ms 408 KB Output is correct
7 Correct 17 ms 468 KB Output is correct
8 Correct 16 ms 396 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 21 ms 452 KB Output is correct
11 Correct 18 ms 432 KB Output is correct
12 Correct 6 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 432 KB Output is correct
2 Correct 14 ms 420 KB Output is correct
3 Correct 18 ms 428 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 7 ms 392 KB Output is correct
6 Correct 18 ms 408 KB Output is correct
7 Correct 17 ms 468 KB Output is correct
8 Correct 16 ms 396 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 21 ms 452 KB Output is correct
11 Correct 18 ms 432 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 34 ms 1364 KB Output is correct
14 Correct 36 ms 1392 KB Output is correct
15 Correct 21 ms 1464 KB Output is correct
16 Correct 14 ms 2376 KB Output is correct
17 Correct 25 ms 1324 KB Output is correct
18 Correct 43 ms 1340 KB Output is correct
19 Correct 40 ms 1364 KB Output is correct
20 Correct 22 ms 1844 KB Output is correct
21 Correct 13 ms 1364 KB Output is correct
22 Correct 17 ms 2372 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 86664 KB Output is correct
2 Correct 579 ms 102432 KB Output is correct
3 Correct 516 ms 102492 KB Output is correct
4 Correct 535 ms 102484 KB Output is correct
5 Correct 534 ms 102476 KB Output is correct
6 Correct 490 ms 102456 KB Output is correct
7 Correct 498 ms 102440 KB Output is correct
8 Correct 513 ms 102492 KB Output is correct
9 Correct 543 ms 102568 KB Output is correct
10 Correct 516 ms 102452 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1352 KB Output is correct
2 Correct 92 ms 9308 KB Output is correct
3 Correct 519 ms 102484 KB Output is correct
4 Correct 646 ms 102460 KB Output is correct
5 Correct 438 ms 102472 KB Output is correct
6 Correct 1004 ms 200248 KB Output is correct
7 Correct 527 ms 102492 KB Output is correct
8 Correct 527 ms 102520 KB Output is correct
9 Correct 516 ms 103076 KB Output is correct
10 Correct 538 ms 109388 KB Output is correct
11 Correct 517 ms 145336 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1460 KB Output is correct
2 Correct 40 ms 1472 KB Output is correct
3 Correct 58 ms 1564 KB Output is correct
4 Correct 76 ms 1568 KB Output is correct
5 Correct 101 ms 2376 KB Output is correct
6 Correct 614 ms 86896 KB Output is correct
7 Correct 681 ms 86772 KB Output is correct
8 Correct 605 ms 86828 KB Output is correct
9 Correct 735 ms 86820 KB Output is correct
10 Correct 578 ms 86824 KB Output is correct
11 Correct 583 ms 86904 KB Output is correct
12 Correct 560 ms 86764 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 432 KB Output is correct
2 Correct 14 ms 420 KB Output is correct
3 Correct 18 ms 428 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 7 ms 392 KB Output is correct
6 Correct 18 ms 408 KB Output is correct
7 Correct 17 ms 468 KB Output is correct
8 Correct 16 ms 396 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 21 ms 452 KB Output is correct
11 Correct 18 ms 432 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 34 ms 1364 KB Output is correct
14 Correct 36 ms 1392 KB Output is correct
15 Correct 21 ms 1464 KB Output is correct
16 Correct 14 ms 2376 KB Output is correct
17 Correct 25 ms 1324 KB Output is correct
18 Correct 43 ms 1340 KB Output is correct
19 Correct 40 ms 1364 KB Output is correct
20 Correct 22 ms 1844 KB Output is correct
21 Correct 13 ms 1364 KB Output is correct
22 Correct 17 ms 2372 KB Output is correct
23 Correct 690 ms 86664 KB Output is correct
24 Correct 579 ms 102432 KB Output is correct
25 Correct 516 ms 102492 KB Output is correct
26 Correct 535 ms 102484 KB Output is correct
27 Correct 534 ms 102476 KB Output is correct
28 Correct 490 ms 102456 KB Output is correct
29 Correct 498 ms 102440 KB Output is correct
30 Correct 513 ms 102492 KB Output is correct
31 Correct 543 ms 102568 KB Output is correct
32 Correct 516 ms 102452 KB Output is correct
33 Correct 32 ms 1352 KB Output is correct
34 Correct 92 ms 9308 KB Output is correct
35 Correct 519 ms 102484 KB Output is correct
36 Correct 646 ms 102460 KB Output is correct
37 Correct 438 ms 102472 KB Output is correct
38 Correct 1004 ms 200248 KB Output is correct
39 Correct 527 ms 102492 KB Output is correct
40 Correct 527 ms 102520 KB Output is correct
41 Correct 516 ms 103076 KB Output is correct
42 Correct 538 ms 109388 KB Output is correct
43 Correct 517 ms 145336 KB Output is correct
44 Correct 24 ms 1460 KB Output is correct
45 Correct 40 ms 1472 KB Output is correct
46 Correct 58 ms 1564 KB Output is correct
47 Correct 76 ms 1568 KB Output is correct
48 Correct 101 ms 2376 KB Output is correct
49 Correct 614 ms 86896 KB Output is correct
50 Correct 681 ms 86772 KB Output is correct
51 Correct 605 ms 86828 KB Output is correct
52 Correct 735 ms 86820 KB Output is correct
53 Correct 578 ms 86824 KB Output is correct
54 Correct 583 ms 86904 KB Output is correct
55 Correct 560 ms 86764 KB Output is correct
56 Correct 82 ms 1996 KB Output is correct
57 Correct 172 ms 1992 KB Output is correct
58 Correct 279 ms 2932 KB Output is correct
59 Correct 1016 ms 103468 KB Output is correct
60 Correct 1313 ms 103488 KB Output is correct
61 Correct 880 ms 103480 KB Output is correct
62 Correct 714 ms 103516 KB Output is correct
63 Correct 1088 ms 103532 KB Output is correct
64 Correct 1008 ms 103592 KB Output is correct
65 Correct 908 ms 103496 KB Output is correct
66 Correct 1032 ms 104180 KB Output is correct
67 Correct 967 ms 110440 KB Output is correct
68 Correct 818 ms 128172 KB Output is correct
69 Correct 1399 ms 146512 KB Output is correct