oj.uz

Submission #928528

# Submission time Handle Problem Language Result Execution time Memory
928528 2024-02-16T14:58:08 Z GrindMachine Seats (IOI18_seats) C++17
100 / 100
 3017 ms 119568 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
http://www.algonotes.com/en/solutions-ioi2018/

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "seats.h"

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        int mn,mn_cnt;
    };

    struct lazy {
        int a;
    };

    data d_neutral = {inf1,0};
    lazy l_neutral = {0};

    void merge(data &curr, data &left, data &right) {
        if(left.mn <= right.mn) curr = left;
        else curr = right;
        if(left.mn == right.mn) curr.mn_cnt += right.mn_cnt;
    }

    void create(int x, int lx, int rx, T v) {
        tr[x].mn = 0;
        tr[x].mn_cnt = 1;
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].a = v;
    }

    void propagate(int x, int lx, int rx) {
        int v = lz[x].a;
        if(!v) return;

        tr[x].mn += v;

        if(rx-lx > 1){
            lz[2*x+1].a += v;
            lz[2*x+2].a += v;
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, 0);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(n, 2 * x + 1, lx, mid);
        build(n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(int n) {
        build(n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

vector<vector<int>> a;
vector<pii> pos;
lazysegtree<int> st;
int n,m;

void upd(int i, int j, int add){
    // update the subsquare with corners (i,j),(i+1,j+1)
    vector<int> vals;
    for(int r = i; r <= i+1; ++r){
        for(int c = j; c <= j+1; ++c){
            vals.pb(a[r][c]);
        }
    }

    sort(all(vals));

    {
        int l = vals[0], r = vals[1]-1;
        st.rupd(l,r,add);
    }

    {
        int l = vals[2], r = vals[3]-1;
        if(l != inf1){
            st.rupd(l,r,add);
        }
    }
}

void give_initial_chart(int n_, int m_, std::vector<int> R, std::vector<int> C) {
    n = n_, m = m_;
    a = vector<vector<int>>(n+5,vector<int>(m+5,inf1));
    rep(i,n*m){
        int r = R[i]+1, c = C[i]+1;
        a[r][c] = i;
    }
    rep(i,n*m) pos.pb({R[i]+1,C[i]+1});

    st = lazysegtree<int>(n*m);
    st.build(n*m);

    rep(i,n+1){
        rep(j,m+1){
            upd(i,j,1);
        }
    }
}

int swap_seats(int x, int y) {
    auto [r1,c1] = pos[x];
    auto [r2,c2] = pos[y];
    set<pii> sqs;
    for(int i = r1-1; i <= r1; ++i){
        for(int j = c1-1; j <= c1; ++j){
            sqs.insert({i,j});
        }
    }
    for(int i = r2-1; i <= r2; ++i){
        for(int j = c2-1; j <= c2; ++j){
            sqs.insert({i,j});
        }
    }

    for(auto [i,j] : sqs){
        upd(i,j,-1);
    }

    swap(pos[x],pos[y]);
    swap(a[r1][c1],a[r2][c2]);

    for(auto [i,j] : sqs){
        upd(i,j,1);
    }

    auto [mn,mn_cnt] = st.query(0,n*m-1);
    assert(mn == 4);

    int ans = mn_cnt;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 596 KB Output is correct
2 Correct 26 ms 560 KB Output is correct
3 Correct 44 ms 576 KB Output is correct
4 Correct 26 ms 592 KB Output is correct
5 Correct 22 ms 588 KB Output is correct
6 Correct 35 ms 592 KB Output is correct
7 Correct 36 ms 552 KB Output is correct
8 Correct 32 ms 596 KB Output is correct
9 Correct 32 ms 596 KB Output is correct
10 Correct 36 ms 604 KB Output is correct
11 Correct 46 ms 584 KB Output is correct
12 Correct 23 ms 592 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 596 KB Output is correct
2 Correct 26 ms 560 KB Output is correct
3 Correct 44 ms 576 KB Output is correct
4 Correct 26 ms 592 KB Output is correct
5 Correct 22 ms 588 KB Output is correct
6 Correct 35 ms 592 KB Output is correct
7 Correct 36 ms 552 KB Output is correct
8 Correct 32 ms 596 KB Output is correct
9 Correct 32 ms 596 KB Output is correct
10 Correct 36 ms 604 KB Output is correct
11 Correct 46 ms 584 KB Output is correct
12 Correct 23 ms 592 KB Output is correct
13 Correct 76 ms 1372 KB Output is correct
14 Correct 95 ms 1448 KB Output is correct
15 Correct 77 ms 1640 KB Output is correct
16 Correct 43 ms 1944 KB Output is correct
17 Correct 80 ms 1424 KB Output is correct
18 Correct 58 ms 1372 KB Output is correct
19 Correct 65 ms 1376 KB Output is correct
20 Correct 48 ms 1628 KB Output is correct
21 Correct 48 ms 1628 KB Output is correct
22 Correct 41 ms 1880 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 68908 KB Output is correct
2 Correct 981 ms 68880 KB Output is correct
3 Correct 903 ms 68696 KB Output is correct
4 Correct 819 ms 68792 KB Output is correct
5 Correct 845 ms 68696 KB Output is correct
6 Correct 784 ms 68540 KB Output is correct
7 Correct 849 ms 68540 KB Output is correct
8 Correct 890 ms 68540 KB Output is correct
9 Correct 890 ms 68780 KB Output is correct
10 Correct 861 ms 68752 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1368 KB Output is correct
2 Correct 152 ms 7476 KB Output is correct
3 Correct 847 ms 68784 KB Output is correct
4 Correct 1790 ms 68700 KB Output is correct
5 Correct 828 ms 92428 KB Output is correct
6 Correct 1787 ms 119568 KB Output is correct
7 Correct 856 ms 77088 KB Output is correct
8 Correct 940 ms 69328 KB Output is correct
9 Correct 867 ms 69428 KB Output is correct
10 Correct 917 ms 74932 KB Output is correct
11 Correct 846 ms 99976 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 2004 KB Output is correct
2 Correct 165 ms 2160 KB Output is correct
3 Correct 218 ms 2080 KB Output is correct
4 Correct 269 ms 1996 KB Output is correct
5 Correct 425 ms 3020 KB Output is correct
6 Correct 1311 ms 93196 KB Output is correct
7 Correct 1589 ms 93460 KB Output is correct
8 Correct 1341 ms 93428 KB Output is correct
9 Correct 2532 ms 93148 KB Output is correct
10 Correct 1314 ms 92948 KB Output is correct
11 Correct 1280 ms 93168 KB Output is correct
12 Correct 1231 ms 93196 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 596 KB Output is correct
2 Correct 26 ms 560 KB Output is correct
3 Correct 44 ms 576 KB Output is correct
4 Correct 26 ms 592 KB Output is correct
5 Correct 22 ms 588 KB Output is correct
6 Correct 35 ms 592 KB Output is correct
7 Correct 36 ms 552 KB Output is correct
8 Correct 32 ms 596 KB Output is correct
9 Correct 32 ms 596 KB Output is correct
10 Correct 36 ms 604 KB Output is correct
11 Correct 46 ms 584 KB Output is correct
12 Correct 23 ms 592 KB Output is correct
13 Correct 76 ms 1372 KB Output is correct
14 Correct 95 ms 1448 KB Output is correct
15 Correct 77 ms 1640 KB Output is correct
16 Correct 43 ms 1944 KB Output is correct
17 Correct 80 ms 1424 KB Output is correct
18 Correct 58 ms 1372 KB Output is correct
19 Correct 65 ms 1376 KB Output is correct
20 Correct 48 ms 1628 KB Output is correct
21 Correct 48 ms 1628 KB Output is correct
22 Correct 41 ms 1880 KB Output is correct
23 Correct 1836 ms 68908 KB Output is correct
24 Correct 981 ms 68880 KB Output is correct
25 Correct 903 ms 68696 KB Output is correct
26 Correct 819 ms 68792 KB Output is correct
27 Correct 845 ms 68696 KB Output is correct
28 Correct 784 ms 68540 KB Output is correct
29 Correct 849 ms 68540 KB Output is correct
30 Correct 890 ms 68540 KB Output is correct
31 Correct 890 ms 68780 KB Output is correct
32 Correct 861 ms 68752 KB Output is correct
33 Correct 71 ms 1368 KB Output is correct
34 Correct 152 ms 7476 KB Output is correct
35 Correct 847 ms 68784 KB Output is correct
36 Correct 1790 ms 68700 KB Output is correct
37 Correct 828 ms 92428 KB Output is correct
38 Correct 1787 ms 119568 KB Output is correct
39 Correct 856 ms 77088 KB Output is correct
40 Correct 940 ms 69328 KB Output is correct
41 Correct 867 ms 69428 KB Output is correct
42 Correct 917 ms 74932 KB Output is correct
43 Correct 846 ms 99976 KB Output is correct
44 Correct 112 ms 2004 KB Output is correct
45 Correct 165 ms 2160 KB Output is correct
46 Correct 218 ms 2080 KB Output is correct
47 Correct 269 ms 1996 KB Output is correct
48 Correct 425 ms 3020 KB Output is correct
49 Correct 1311 ms 93196 KB Output is correct
50 Correct 1589 ms 93460 KB Output is correct
51 Correct 1341 ms 93428 KB Output is correct
52 Correct 2532 ms 93148 KB Output is correct
53 Correct 1314 ms 92948 KB Output is correct
54 Correct 1280 ms 93168 KB Output is correct
55 Correct 1231 ms 93196 KB Output is correct
56 Correct 180 ms 1940 KB Output is correct
57 Correct 377 ms 2028 KB Output is correct
58 Correct 538 ms 2840 KB Output is correct
59 Correct 1680 ms 69816 KB Output is correct
60 Correct 3017 ms 69664 KB Output is correct
61 Correct 1556 ms 69724 KB Output is correct
62 Correct 1384 ms 81052 KB Output is correct
63 Correct 2801 ms 78056 KB Output is correct
64 Correct 1789 ms 72116 KB Output is correct
65 Correct 1518 ms 69800 KB Output is correct
66 Correct 1689 ms 70072 KB Output is correct
67 Correct 1753 ms 75956 KB Output is correct
68 Correct 1424 ms 89264 KB Output is correct
69 Correct 2602 ms 101032 KB Output is correct