oj.uz

답안 #928748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928748 2024-02-17T04:00:55 Z GrindMachine 자리 배치 (IOI18_seats) C++17
100 / 100
 2998 ms 119464 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/

key idea:
look at 2x2 squares of the grid

for a connected component, the #of 2x2 squares with exactly 1 black cell is at least 4
#of connected components in a a rectangle = 1, so #of 2x2 squares with exactly 1 black cell is exactly 4
each endpoint of the rect contributes +1 to this value, so +4 in total

is this condition sufficient?

there should also be no "outward" angles
so there is no 2x2 square with #of black cells = 3

it turns out that these 2 conditions are sufficient (can understand why these conditions are necessary, but dont understand why they are sufficient)

if a time t is good, (#of 2x2 squares with 1 black cell) + (#of 2x2 squares with 3 black cells) = 4
count #of such good indices using a lazy segtree that supports range add and (range_min, min_cnt)

*/

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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 604 KB Output is correct
2 Correct 26 ms 536 KB Output is correct
3 Correct 38 ms 548 KB Output is correct
4 Correct 26 ms 604 KB Output is correct
5 Correct 22 ms 604 KB Output is correct
6 Correct 33 ms 596 KB Output is correct
7 Correct 43 ms 592 KB Output is correct
8 Correct 32 ms 612 KB Output is correct
9 Correct 32 ms 548 KB Output is correct
10 Correct 35 ms 592 KB Output is correct
11 Correct 38 ms 596 KB Output is correct
12 Correct 22 ms 592 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 604 KB Output is correct
2 Correct 26 ms 536 KB Output is correct
3 Correct 38 ms 548 KB Output is correct
4 Correct 26 ms 604 KB Output is correct
5 Correct 22 ms 604 KB Output is correct
6 Correct 33 ms 596 KB Output is correct
7 Correct 43 ms 592 KB Output is correct
8 Correct 32 ms 612 KB Output is correct
9 Correct 32 ms 548 KB Output is correct
10 Correct 35 ms 592 KB Output is correct
11 Correct 38 ms 596 KB Output is correct
12 Correct 22 ms 592 KB Output is correct
13 Correct 76 ms 1372 KB Output is correct
14 Correct 91 ms 1448 KB Output is correct
15 Correct 59 ms 1640 KB Output is correct
16 Correct 39 ms 1884 KB Output is correct
17 Correct 63 ms 1368 KB Output is correct
18 Correct 59 ms 1368 KB Output is correct
19 Correct 56 ms 1372 KB Output is correct
20 Correct 48 ms 1628 KB Output is correct
21 Correct 39 ms 1624 KB Output is correct
22 Correct 40 ms 1884 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1835 ms 68748 KB Output is correct
2 Correct 1010 ms 68632 KB Output is correct
3 Correct 972 ms 68756 KB Output is correct
4 Correct 807 ms 68660 KB Output is correct
5 Correct 863 ms 68624 KB Output is correct
6 Correct 790 ms 68624 KB Output is correct
7 Correct 858 ms 68660 KB Output is correct
8 Correct 901 ms 68784 KB Output is correct
9 Correct 903 ms 68876 KB Output is correct
10 Correct 886 ms 68656 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 1476 KB Output is correct
2 Correct 155 ms 7472 KB Output is correct
3 Correct 841 ms 68932 KB Output is correct
4 Correct 1817 ms 69136 KB Output is correct
5 Correct 824 ms 92024 KB Output is correct
6 Correct 1796 ms 119464 KB Output is correct
7 Correct 844 ms 77104 KB Output is correct
8 Correct 931 ms 69032 KB Output is correct
9 Correct 869 ms 69208 KB Output is correct
10 Correct 899 ms 74912 KB Output is correct
11 Correct 839 ms 100108 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 2000 KB Output is correct
2 Correct 166 ms 2088 KB Output is correct
3 Correct 219 ms 2012 KB Output is correct
4 Correct 280 ms 2004 KB Output is correct
5 Correct 413 ms 3020 KB Output is correct
6 Correct 1303 ms 93164 KB Output is correct
7 Correct 1530 ms 92920 KB Output is correct
8 Correct 1269 ms 92936 KB Output is correct
9 Correct 2462 ms 93120 KB Output is correct
10 Correct 1242 ms 93108 KB Output is correct
11 Correct 1286 ms 93192 KB Output is correct
12 Correct 1218 ms 93100 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 604 KB Output is correct
2 Correct 26 ms 536 KB Output is correct
3 Correct 38 ms 548 KB Output is correct
4 Correct 26 ms 604 KB Output is correct
5 Correct 22 ms 604 KB Output is correct
6 Correct 33 ms 596 KB Output is correct
7 Correct 43 ms 592 KB Output is correct
8 Correct 32 ms 612 KB Output is correct
9 Correct 32 ms 548 KB Output is correct
10 Correct 35 ms 592 KB Output is correct
11 Correct 38 ms 596 KB Output is correct
12 Correct 22 ms 592 KB Output is correct
13 Correct 76 ms 1372 KB Output is correct
14 Correct 91 ms 1448 KB Output is correct
15 Correct 59 ms 1640 KB Output is correct
16 Correct 39 ms 1884 KB Output is correct
17 Correct 63 ms 1368 KB Output is correct
18 Correct 59 ms 1368 KB Output is correct
19 Correct 56 ms 1372 KB Output is correct
20 Correct 48 ms 1628 KB Output is correct
21 Correct 39 ms 1624 KB Output is correct
22 Correct 40 ms 1884 KB Output is correct
23 Correct 1835 ms 68748 KB Output is correct
24 Correct 1010 ms 68632 KB Output is correct
25 Correct 972 ms 68756 KB Output is correct
26 Correct 807 ms 68660 KB Output is correct
27 Correct 863 ms 68624 KB Output is correct
28 Correct 790 ms 68624 KB Output is correct
29 Correct 858 ms 68660 KB Output is correct
30 Correct 901 ms 68784 KB Output is correct
31 Correct 903 ms 68876 KB Output is correct
32 Correct 886 ms 68656 KB Output is correct
33 Correct 75 ms 1476 KB Output is correct
34 Correct 155 ms 7472 KB Output is correct
35 Correct 841 ms 68932 KB Output is correct
36 Correct 1817 ms 69136 KB Output is correct
37 Correct 824 ms 92024 KB Output is correct
38 Correct 1796 ms 119464 KB Output is correct
39 Correct 844 ms 77104 KB Output is correct
40 Correct 931 ms 69032 KB Output is correct
41 Correct 869 ms 69208 KB Output is correct
42 Correct 899 ms 74912 KB Output is correct
43 Correct 839 ms 100108 KB Output is correct
44 Correct 111 ms 2000 KB Output is correct
45 Correct 166 ms 2088 KB Output is correct
46 Correct 219 ms 2012 KB Output is correct
47 Correct 280 ms 2004 KB Output is correct
48 Correct 413 ms 3020 KB Output is correct
49 Correct 1303 ms 93164 KB Output is correct
50 Correct 1530 ms 92920 KB Output is correct
51 Correct 1269 ms 92936 KB Output is correct
52 Correct 2462 ms 93120 KB Output is correct
53 Correct 1242 ms 93108 KB Output is correct
54 Correct 1286 ms 93192 KB Output is correct
55 Correct 1218 ms 93100 KB Output is correct
56 Correct 180 ms 2000 KB Output is correct
57 Correct 376 ms 2296 KB Output is correct
58 Correct 542 ms 2736 KB Output is correct
59 Correct 1633 ms 69392 KB Output is correct
60 Correct 2998 ms 69616 KB Output is correct
61 Correct 1573 ms 69628 KB Output is correct
62 Correct 1313 ms 81316 KB Output is correct
63 Correct 2808 ms 78012 KB Output is correct
64 Correct 1830 ms 71968 KB Output is correct
65 Correct 1515 ms 69756 KB Output is correct
66 Correct 1692 ms 70032 KB Output is correct
67 Correct 1739 ms 76060 KB Output is correct
68 Correct 1419 ms 89116 KB Output is correct
69 Correct 2761 ms 100860 KB Output is correct