oj.uz

답안 #926768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926768 2024-02-13T17:16:07 Z efishel 자리 배치 (IOI18_seats) C++17
0 / 100
 207 ms 262144 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()) {}

    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 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);
    }

    void tour (ll l, ll r, ll id) {
        push(l, r, id);
        if (l == r) {
            cerr << l << ": " << tree[id].minN << '\n';
            return;
        }
        tour(l, mid, id+1);
        tour(mid+1, r, id+off);
    }

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

SegTree st(0);
ll n;
vll ve2;
vll ve;

void give_initial_chart (int _, int n, vector <int> ve2, vector <int> __) {
    ::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;
    st.update(ve[0], n-1, 1, 0, n-1, 0);
    for (ll i = 1; i < n; i++) {
        ll l = min(ve[i-1], ve[i]);
        ll r = max(ve[i-1], ve[i])-1;
        st.update(l, r, 1, 0, n-1, 0);
    }
    st.update(ve[n-1], n-1, 1, 0, n-1, 0);
}

ll 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());
}

Compilation message

seats.cpp: In function 'll change(ll, ll)':
seats.cpp:107:1: warning: no return statement in function returning non-void [-Wreturn-type]
  107 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 30.0

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