oj.uz

답안 #926775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926775 2024-02-13T17:27:14 Z efishel 자리 배치 (IOI18_seats) C++17
33 / 100
 1752 ms 111420 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 (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 () {
        return tree[0].cou;
    }
};

SegTree st(1);
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 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

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

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 2000 KB Output is correct
2 Correct 51 ms 2076 KB Output is correct
3 Correct 82 ms 2052 KB Output is correct
4 Correct 103 ms 1996 KB Output is correct
5 Correct 190 ms 3092 KB Output is correct
6 Correct 724 ms 111420 KB Output is correct
7 Correct 874 ms 111368 KB Output is correct
8 Correct 663 ms 111420 KB Output is correct
9 Correct 1752 ms 111368 KB Output is correct
10 Correct 658 ms 111180 KB Output is correct
11 Correct 643 ms 111184 KB Output is correct
12 Correct 641 ms 111364 KB Output is correct

Subtask #6
0 / 30.0

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