oj.uz

Submission #796811

# Submission time Handle Problem Language Result Execution time Memory
796811 2023-07-28T19:02:26 Z fatemetmhr Seats (IOI18_seats) C++17
100 / 100
 2082 ms 173876 KB 
// Be name khode //

#include "seats.h"
#include <bits/stdc++.h>
 
using namespace std;


 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair
 
typedef long long ll;
 
const int maxn = 1e6 + 5;
const int maxnt = 4e6 + 30;
const int lg    = 20;

std::vector<int> r;

int n, m, have = 0, sgn, av[5];
pair <int, int> a[maxn];
vector <int> ind[maxn], st[maxn];
vector <pair<int, int>> adj = {{0, 0}, {-1, 0}, {0, -1}, {-1, -1}};
vector <pair<int, int>> sq = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};

namespace seg{

    int lazy[maxnt];
    pair <int, int> mn[maxnt];

    void upd(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            mn[v].fi += val;
            return;
        }
        int mid = (l + r) >> 1;
        upd(l, mid, lq, rq, val, v * 2);
        upd(mid, r, lq, rq, val, v * 2 + 1);
        mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
        if(mn[v * 2].fi == mn[v * 2 + 1].fi)
            mn[v].se = mn[v * 2].se + mn[v * 2 + 1].se;
        mn[v].fi += lazy[v];
    }

    void build(int l, int r, int v){
        mn[v].se = r - l;
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
    }
}

bool ok(int x, int y){
    return min(x, y) >= 0 && x + 1 < n && y + 1 < m;
}

void upd(int x, int y, int val){
    if(st[x][y] == val)
        return;
    st[x][y] = val;
    int pt = 0;
    for(auto [u, v] : sq){
        //cout << x << ' ' << y << ' ' << u << ' ' << v << ' ' << x 
        int w = ind[x + u][y + v];
        av[pt++] = w;
        //cout << "ha? " << x << ' ' << y << ' ' << u << ' ' << v << ' ' << w << endl;
    }
    sort(av, av + pt);
    //cout << "upd of " << x << ' ' << y << ' ' << val << endl;
    seg::upd(0, sgn, av[0], av[1], val, 1);
    seg::upd(0, sgn, av[2], av[3], val, 1);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H;
    m = W;
    sgn = n * m;
    seg::build(0, sgn, 1);
    for(int i = 0; i < n + 2; i++){
        ind[i].resize(m + 2);
        st[i].resize(m + 2, -1);
        for(int j = 0; j < m + 2; j++)
            ind[i][j] = n * m;
    }
    for(int i = 0; i < n * m; i++){
        a[i] = {R[i] + 1, C[i] + 1}; 
        ind[R[i] + 1][C[i] + 1] = i;
    }
    n += 2;
    m += 2;
    for(int i = 0; i < n - 1; i++)
        for(int j = 0; j < m - 1; j++)
            upd(i, j, 1);
}


int swap_seats(int x, int y) {
    for(auto [u, v] : adj){
        if(ok(a[x].fi + u, a[x].se + v))
            upd(a[x].fi + u, a[x].se + v, -1);
        if(ok(a[y].fi + u, a[y].se + v))
            upd(a[y].fi + u, a[y].se + v, -1);
    }
    swap(a[x], a[y]);
    ind[a[x].fi][a[x].se] = x;
    ind[a[y].fi][a[y].se] = y;
    for(auto [u, v] : adj){
        if(ok(a[x].fi + u, a[x].se + v))
            upd(a[x].fi + u, a[x].se + v, 1);
        if(ok(a[y].fi + u, a[y].se + v))
            upd(a[y].fi + u, a[y].se + v, 1);
    }
    assert(seg::mn[1].fi >= 4);
    //cout << "now " << x << ' ' << y << ' ' << seg::mn[1].fi << ' ' << seg::mn[1].se << endl;
    return seg::mn[1].se;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47316 KB Output is correct
2 Correct 34 ms 47348 KB Output is correct
3 Correct 43 ms 47336 KB Output is correct
4 Correct 39 ms 47360 KB Output is correct
5 Correct 33 ms 47316 KB Output is correct
6 Correct 40 ms 47344 KB Output is correct
7 Correct 41 ms 47344 KB Output is correct
8 Correct 39 ms 47356 KB Output is correct
9 Correct 38 ms 47360 KB Output is correct
10 Correct 41 ms 47364 KB Output is correct
11 Correct 40 ms 47404 KB Output is correct
12 Correct 34 ms 47400 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47316 KB Output is correct
2 Correct 34 ms 47348 KB Output is correct
3 Correct 43 ms 47336 KB Output is correct
4 Correct 39 ms 47360 KB Output is correct
5 Correct 33 ms 47316 KB Output is correct
6 Correct 40 ms 47344 KB Output is correct
7 Correct 41 ms 47344 KB Output is correct
8 Correct 39 ms 47356 KB Output is correct
9 Correct 38 ms 47360 KB Output is correct
10 Correct 41 ms 47364 KB Output is correct
11 Correct 40 ms 47404 KB Output is correct
12 Correct 34 ms 47400 KB Output is correct
13 Correct 66 ms 47956 KB Output is correct
14 Correct 75 ms 48012 KB Output is correct
15 Correct 52 ms 48084 KB Output is correct
16 Correct 54 ms 48676 KB Output is correct
17 Correct 59 ms 47996 KB Output is correct
18 Correct 59 ms 48000 KB Output is correct
19 Correct 59 ms 48056 KB Output is correct
20 Correct 53 ms 48240 KB Output is correct
21 Correct 45 ms 48168 KB Output is correct
22 Correct 45 ms 48596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1331 ms 103304 KB Output is correct
2 Correct 708 ms 119312 KB Output is correct
3 Correct 716 ms 119244 KB Output is correct
4 Correct 570 ms 119248 KB Output is correct
5 Correct 613 ms 119260 KB Output is correct
6 Correct 617 ms 119224 KB Output is correct
7 Correct 667 ms 119220 KB Output is correct
8 Correct 747 ms 119256 KB Output is correct
9 Correct 708 ms 119252 KB Output is correct
10 Correct 680 ms 119244 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 48024 KB Output is correct
2 Correct 126 ms 53184 KB Output is correct
3 Correct 613 ms 103332 KB Output is correct
4 Correct 1315 ms 119244 KB Output is correct
5 Correct 594 ms 132780 KB Output is correct
6 Correct 1285 ms 173876 KB Output is correct
7 Correct 624 ms 123984 KB Output is correct
8 Correct 699 ms 119480 KB Output is correct
9 Correct 616 ms 118732 KB Output is correct
10 Correct 637 ms 123820 KB Output is correct
11 Correct 634 ms 141664 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 48296 KB Output is correct
2 Correct 99 ms 48324 KB Output is correct
3 Correct 135 ms 48312 KB Output is correct
4 Correct 174 ms 48292 KB Output is correct
5 Correct 259 ms 49044 KB Output is correct
6 Correct 917 ms 118220 KB Output is correct
7 Correct 1029 ms 119244 KB Output is correct
8 Correct 872 ms 117224 KB Output is correct
9 Correct 1670 ms 119268 KB Output is correct
10 Correct 820 ms 118220 KB Output is correct
11 Correct 831 ms 118192 KB Output is correct
12 Correct 784 ms 117152 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47316 KB Output is correct
2 Correct 34 ms 47348 KB Output is correct
3 Correct 43 ms 47336 KB Output is correct
4 Correct 39 ms 47360 KB Output is correct
5 Correct 33 ms 47316 KB Output is correct
6 Correct 40 ms 47344 KB Output is correct
7 Correct 41 ms 47344 KB Output is correct
8 Correct 39 ms 47356 KB Output is correct
9 Correct 38 ms 47360 KB Output is correct
10 Correct 41 ms 47364 KB Output is correct
11 Correct 40 ms 47404 KB Output is correct
12 Correct 34 ms 47400 KB Output is correct
13 Correct 66 ms 47956 KB Output is correct
14 Correct 75 ms 48012 KB Output is correct
15 Correct 52 ms 48084 KB Output is correct
16 Correct 54 ms 48676 KB Output is correct
17 Correct 59 ms 47996 KB Output is correct
18 Correct 59 ms 48000 KB Output is correct
19 Correct 59 ms 48056 KB Output is correct
20 Correct 53 ms 48240 KB Output is correct
21 Correct 45 ms 48168 KB Output is correct
22 Correct 45 ms 48596 KB Output is correct
23 Correct 1331 ms 103304 KB Output is correct
24 Correct 708 ms 119312 KB Output is correct
25 Correct 716 ms 119244 KB Output is correct
26 Correct 570 ms 119248 KB Output is correct
27 Correct 613 ms 119260 KB Output is correct
28 Correct 617 ms 119224 KB Output is correct
29 Correct 667 ms 119220 KB Output is correct
30 Correct 747 ms 119256 KB Output is correct
31 Correct 708 ms 119252 KB Output is correct
32 Correct 680 ms 119244 KB Output is correct
33 Correct 66 ms 48024 KB Output is correct
34 Correct 126 ms 53184 KB Output is correct
35 Correct 613 ms 103332 KB Output is correct
36 Correct 1315 ms 119244 KB Output is correct
37 Correct 594 ms 132780 KB Output is correct
38 Correct 1285 ms 173876 KB Output is correct
39 Correct 624 ms 123984 KB Output is correct
40 Correct 699 ms 119480 KB Output is correct
41 Correct 616 ms 118732 KB Output is correct
42 Correct 637 ms 123820 KB Output is correct
43 Correct 634 ms 141664 KB Output is correct
44 Correct 55 ms 48296 KB Output is correct
45 Correct 99 ms 48324 KB Output is correct
46 Correct 135 ms 48312 KB Output is correct
47 Correct 174 ms 48292 KB Output is correct
48 Correct 259 ms 49044 KB Output is correct
49 Correct 917 ms 118220 KB Output is correct
50 Correct 1029 ms 119244 KB Output is correct
51 Correct 872 ms 117224 KB Output is correct
52 Correct 1670 ms 119268 KB Output is correct
53 Correct 820 ms 118220 KB Output is correct
54 Correct 831 ms 118192 KB Output is correct
55 Correct 784 ms 117152 KB Output is correct
56 Correct 106 ms 48912 KB Output is correct
57 Correct 233 ms 49012 KB Output is correct
58 Correct 373 ms 49752 KB Output is correct
59 Correct 1172 ms 120156 KB Output is correct
60 Correct 2082 ms 120252 KB Output is correct
61 Correct 1139 ms 120116 KB Output is correct
62 Correct 875 ms 125940 KB Output is correct
63 Correct 1932 ms 125516 KB Output is correct
64 Correct 1239 ms 121792 KB Output is correct
65 Correct 1162 ms 120280 KB Output is correct
66 Correct 1186 ms 119608 KB Output is correct
67 Correct 1212 ms 124748 KB Output is correct
68 Correct 982 ms 132652 KB Output is correct
69 Correct 1845 ms 143692 KB Output is correct