oj.uz

답안 #926778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926778 2024-02-13T17:31:23 Z efishel 자리 배치 (IOI18_seats) C++17
33 / 100
 1780 ms 94888 KB 
// #include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll minN;
        ll cou;
        bool hasL;
        ll lazy;

        Node (): minN(0), cou(1), hasL(false), lazy(0) {} // idem. lazy init

        Node operator+ (const Node& o) {
            Node ans;
            ans.minN = min(minN, o.minN);
            if (minN == o.minN) ans.cou = cou + o.cou;
            else if (minN < o.minN) ans.cou = cou;
            else ans.cou = o.cou;
            return ans;
        }
    };

    vector <Node> tree;

    SegTree () {}
    SegTree (ll n): tree(2*n, Node()) { build(0, n-1, 0); }

    void push (ll l, ll r, ll id) {
        if (!tree[id].hasL) return;
        tree[id].minN += tree[id].lazy;
        if (l < r) {
            tree[id+1].lazy += tree[id].lazy;
            tree[id+1].hasL = true;
            tree[id+off].lazy += tree[id].lazy;
            tree[id+off].hasL = true;
        }
        tree[id].hasL = false;
        tree[id].lazy = 0; // 0 is idem.
    }

    void pull (ll l, ll r, ll id) {
        tree[id] = tree[id+1] + tree[id+off];
    }

    void build (ll l, ll r, ll id) {
        if (l >= r) return;
        build(l, mid, id+1);
        build(mid+1, r, id+off);
        pull(l, r, id);
    }

    void update (ll ql, ll qr, ll val, ll l, ll r, ll id) {
        push(l, r, id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[id].lazy += val;
            tree[id].hasL = true;
            push(l, r, id);
            return;
        }
        update(ql, qr, val, l, mid, id+1);
        update(ql, qr, val, mid+1, r, id+off);
        pull(l, r, id);
    }

    ll query () {
        assert(tree[0].minN == 2);
        return tree[0].cou;
    }
};

SegTree st;
ll n;
vll ve2;
vll ve;

void change (ll i, ll val) {
    // border between ve[i-1] and ve[i]
    ll l = min(i>0 ? ve[i-1] : n, i<n ? ve[i] : n);
    ll r = max(i>0 ? ve[i-1] : n, i<n ? ve[i] : n)-1;
    st.update(l, r, val, 0, n-1, 0);
}

int swap_seats (int a, int b) {
    ll atA = ve2[a];
    ll atB = ve2[b];
    change(atA, -1);
    change(atA+1, -1);
    change(atB, -1);
    change(atB+1, -1);
    swap(ve2[a], ve2[b]);
    swap(ve[atA], ve[atB]);
    change(atA, 1);
    change(atA+1, 1);
    change(atB, 1);
    change(atB+1, 1);
    return int(st.query());
}

void give_initial_chart (int _, int n, vector <int> __, vector <int> ve2) {
    ::n = n;
    ::ve.resize(n);
    ::ve2.resize(n);
    for (ll i = 0; i < n; i++) {
        ve[ve2[i]] = i;
        ::ve2[i] = ve2[i];
    }
    st.tree = SegTree(n).tree;
    for (ll i = 0; i <= n; i++) {
        change(i, 1);
    }
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 16624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1472 KB Output is correct
2 Correct 45 ms 1456 KB Output is correct
3 Correct 74 ms 1464 KB Output is correct
4 Correct 102 ms 1424 KB Output is correct
5 Correct 196 ms 2316 KB Output is correct
6 Correct 695 ms 94888 KB Output is correct
7 Correct 867 ms 94760 KB Output is correct
8 Correct 650 ms 94764 KB Output is correct
9 Correct 1780 ms 94760 KB Output is correct
10 Correct 625 ms 94540 KB Output is correct
11 Correct 616 ms 94760 KB Output is correct
12 Correct 603 ms 94544 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -