oj.uz

Submission #793057

# Submission time Handle Problem Language Result Execution time Memory
793057 2023-07-25T13:10:58 Z 1bin Seats (IOI18_seats) C++14
100 / 100
 1464 ms 59292 KB 
#include <bits/stdc++.h>
//#include "seats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 20;
int n, lazy[b * 2], W, v[b * 3], pfx[b];
int seg[b * 2][2];
vector<int> Y, X;
 
void upd_lazy(int ix, int l, int r){
    if(!lazy[ix]) return;
    seg[ix][0] += lazy[ix];
    if(l ^ r){
        lazy[ix * 2] += lazy[ix];
        lazy[ix * 2 + 1] += lazy[ix];
    }
    lazy[ix] = 0;
    return;
}
 
void upd(int ix, int nl, int nr, int l, int r, int v){
    upd_lazy(ix, nl, nr);
    if(nl > r || nr < l) return;
    if(nl >= l && nr <= r){
        lazy[ix] += v;
        upd_lazy(ix, nl, nr);
        return;
    }
    int m = (nl + nr) / 2;
    upd(ix * 2, nl, m, l, r, v);
    upd(ix * 2 + 1, m + 1, nr, l, r, v);
    seg[ix][0] = min(seg[ix * 2][0], seg[ix * 2 + 1][0]);
    seg[ix][1] = (seg[ix * 2][0] == seg[ix][0] ? seg[ix * 2][1] : 0) + (seg[ix * 2 + 1][0] == seg[ix][0] ? seg[ix * 2 + 1][1] : 0);
    return;
}
 
void calc(int ix, int p){
    vector<int> t;
    for(int i = -1; i <= 0; i++)
        for(int j = -1; j <= 0; j++)
            t.emplace_back(v[ix + i * (W + 2) + j]);
    sort(all(t));
    upd(1, 0, b - 1, t[0], t[1] - 1, p);
    upd(1, 0, b - 1, t[2], t[3] - 1, p);
    return;
}
 
void give_initial_chart(int H, int W_, vector<int> R, vector<int> C) {
    Y = R; X = C; W = W_;
    n = H * W;
    for(int i = 0; i <= (H + 2) * (W + 2); i++) v[i] = n;
    for(int i = 0; i < n; i++) v[++Y[i] * (W + 2) + ++X[i]] = i;
    for(int i = b; i < b * 2; i++) seg[i][0] = b;
    for(int y = 1; y <= H + 1; y++)
        for(int x = 1; x <= W + 1; x++) {
            vector<int> t;
            for(int i = -1; i <= 0; i++)
                for(int j = -1; j <= 0; j++)
                    t.emplace_back(v[(y + i) * (W + 2) + x + j]);
            sort(all(t));
            pfx[t[0]]++;
            pfx[t[1]]--;
            pfx[t[2]]++;
            pfx[t[3]]--;
        }
    int cur = 0;
    for(int i = 0; i < n; i++){
        cur += pfx[i];
        seg[b + i][0] = cur; 
        seg[b + i][1] = 1;
    }
    for(int i = b - 1; i; i--){
        seg[i][0] = min(seg[i * 2][0], seg[i * 2 + 1][0]);
        seg[i][1] = (seg[i * 2][0] == seg[i][0] ? seg[i * 2][1] : 0) + (seg[i * 2 + 1][0] == seg[i][0] ? seg[i * 2 + 1][1] : 0);
    }
    return;
}
 
int swap_seats(int i1, int i2) {
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++){
            calc((Y[i1] + i) * (W + 2) + X[i1] + j, -1);
            calc((Y[i2] + i) * (W + 2) + X[i2] + j, -1);
        }
    swap(Y[i1], Y[i2]);
    swap(X[i1], X[i2]);
    swap(v[Y[i1] * (W + 2) + X[i1]], v[Y[i2] * (W + 2) + X[i2]]);
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++){
            calc((Y[i1] + i) * (W + 2) + X[i1] + j, 1);
            calc((Y[i2] + i) * (W + 2) + X[i2] + j, 1);
        }
    if(seg[1][0] == 4) return seg[1][1];
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16928 KB Output is correct
2 Correct 51 ms 16880 KB Output is correct
3 Correct 61 ms 17008 KB Output is correct
4 Correct 50 ms 16876 KB Output is correct
5 Correct 58 ms 16884 KB Output is correct
6 Correct 57 ms 16908 KB Output is correct
7 Correct 66 ms 16876 KB Output is correct
8 Correct 54 ms 16908 KB Output is correct
9 Correct 56 ms 16888 KB Output is correct
10 Correct 60 ms 16908 KB Output is correct
11 Correct 56 ms 16884 KB Output is correct
12 Correct 47 ms 16852 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16928 KB Output is correct
2 Correct 51 ms 16880 KB Output is correct
3 Correct 61 ms 17008 KB Output is correct
4 Correct 50 ms 16876 KB Output is correct
5 Correct 58 ms 16884 KB Output is correct
6 Correct 57 ms 16908 KB Output is correct
7 Correct 66 ms 16876 KB Output is correct
8 Correct 54 ms 16908 KB Output is correct
9 Correct 56 ms 16888 KB Output is correct
10 Correct 60 ms 16908 KB Output is correct
11 Correct 56 ms 16884 KB Output is correct
12 Correct 47 ms 16852 KB Output is correct
13 Correct 80 ms 17372 KB Output is correct
14 Correct 92 ms 17376 KB Output is correct
15 Correct 64 ms 17388 KB Output is correct
16 Correct 55 ms 17444 KB Output is correct
17 Correct 70 ms 17408 KB Output is correct
18 Correct 67 ms 17392 KB Output is correct
19 Correct 82 ms 17380 KB Output is correct
20 Correct 59 ms 17416 KB Output is correct
21 Correct 58 ms 17464 KB Output is correct
22 Correct 61 ms 17484 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 51056 KB Output is correct
2 Correct 340 ms 49996 KB Output is correct
3 Correct 356 ms 49800 KB Output is correct
4 Correct 330 ms 49928 KB Output is correct
5 Correct 332 ms 49860 KB Output is correct
6 Correct 353 ms 49944 KB Output is correct
7 Correct 315 ms 49904 KB Output is correct
8 Correct 320 ms 49416 KB Output is correct
9 Correct 361 ms 49468 KB Output is correct
10 Correct 307 ms 49460 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 17404 KB Output is correct
2 Correct 99 ms 20980 KB Output is correct
3 Correct 317 ms 50236 KB Output is correct
4 Correct 426 ms 50232 KB Output is correct
5 Correct 383 ms 58040 KB Output is correct
6 Correct 403 ms 58164 KB Output is correct
7 Correct 337 ms 52920 KB Output is correct
8 Correct 328 ms 50348 KB Output is correct
9 Correct 323 ms 50340 KB Output is correct
10 Correct 340 ms 51112 KB Output is correct
11 Correct 376 ms 54188 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 18380 KB Output is correct
2 Correct 401 ms 18372 KB Output is correct
3 Correct 417 ms 18404 KB Output is correct
4 Correct 418 ms 18440 KB Output is correct
5 Correct 616 ms 18940 KB Output is correct
6 Correct 905 ms 59148 KB Output is correct
7 Correct 920 ms 59196 KB Output is correct
8 Correct 941 ms 59260 KB Output is correct
9 Correct 1098 ms 59212 KB Output is correct
10 Correct 830 ms 59292 KB Output is correct
11 Correct 831 ms 59136 KB Output is correct
12 Correct 825 ms 59156 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16928 KB Output is correct
2 Correct 51 ms 16880 KB Output is correct
3 Correct 61 ms 17008 KB Output is correct
4 Correct 50 ms 16876 KB Output is correct
5 Correct 58 ms 16884 KB Output is correct
6 Correct 57 ms 16908 KB Output is correct
7 Correct 66 ms 16876 KB Output is correct
8 Correct 54 ms 16908 KB Output is correct
9 Correct 56 ms 16888 KB Output is correct
10 Correct 60 ms 16908 KB Output is correct
11 Correct 56 ms 16884 KB Output is correct
12 Correct 47 ms 16852 KB Output is correct
13 Correct 80 ms 17372 KB Output is correct
14 Correct 92 ms 17376 KB Output is correct
15 Correct 64 ms 17388 KB Output is correct
16 Correct 55 ms 17444 KB Output is correct
17 Correct 70 ms 17408 KB Output is correct
18 Correct 67 ms 17392 KB Output is correct
19 Correct 82 ms 17380 KB Output is correct
20 Correct 59 ms 17416 KB Output is correct
21 Correct 58 ms 17464 KB Output is correct
22 Correct 61 ms 17484 KB Output is correct
23 Correct 407 ms 51056 KB Output is correct
24 Correct 340 ms 49996 KB Output is correct
25 Correct 356 ms 49800 KB Output is correct
26 Correct 330 ms 49928 KB Output is correct
27 Correct 332 ms 49860 KB Output is correct
28 Correct 353 ms 49944 KB Output is correct
29 Correct 315 ms 49904 KB Output is correct
30 Correct 320 ms 49416 KB Output is correct
31 Correct 361 ms 49468 KB Output is correct
32 Correct 307 ms 49460 KB Output is correct
33 Correct 91 ms 17404 KB Output is correct
34 Correct 99 ms 20980 KB Output is correct
35 Correct 317 ms 50236 KB Output is correct
36 Correct 426 ms 50232 KB Output is correct
37 Correct 383 ms 58040 KB Output is correct
38 Correct 403 ms 58164 KB Output is correct
39 Correct 337 ms 52920 KB Output is correct
40 Correct 328 ms 50348 KB Output is correct
41 Correct 323 ms 50340 KB Output is correct
42 Correct 340 ms 51112 KB Output is correct
43 Correct 376 ms 54188 KB Output is correct
44 Correct 392 ms 18380 KB Output is correct
45 Correct 401 ms 18372 KB Output is correct
46 Correct 417 ms 18404 KB Output is correct
47 Correct 418 ms 18440 KB Output is correct
48 Correct 616 ms 18940 KB Output is correct
49 Correct 905 ms 59148 KB Output is correct
50 Correct 920 ms 59196 KB Output is correct
51 Correct 941 ms 59260 KB Output is correct
52 Correct 1098 ms 59212 KB Output is correct
53 Correct 830 ms 59292 KB Output is correct
54 Correct 831 ms 59136 KB Output is correct
55 Correct 825 ms 59156 KB Output is correct
56 Correct 427 ms 18472 KB Output is correct
57 Correct 559 ms 18528 KB Output is correct
58 Correct 602 ms 18892 KB Output is correct
59 Correct 1061 ms 51356 KB Output is correct
60 Correct 1464 ms 51340 KB Output is correct
61 Correct 897 ms 51448 KB Output is correct
62 Correct 864 ms 55236 KB Output is correct
63 Correct 1397 ms 54008 KB Output is correct
64 Correct 1048 ms 52108 KB Output is correct
65 Correct 889 ms 51388 KB Output is correct
66 Correct 1168 ms 52736 KB Output is correct
67 Correct 1034 ms 53120 KB Output is correct
68 Correct 892 ms 54076 KB Output is correct
69 Correct 1287 ms 55364 KB Output is correct