제출 #1271022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271022		banhcuon14	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	컴파일 에러	0 ms	0 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;
int a[N], b[N];

struct SegmentTree {
    vector<int> t;

    SegmentTree(int n) {
        t.resize(4 * n + 1);
    }

    void up(int id, int l, int r, int pos, int val) {
        if (l == r) {
            t[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos, val);
        else update(id << 1 | 1, mid + 1, r, pos, val);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        if (l > v || r < u || u > v) return 0;
        if (l >= u && r <= v) return t[id];
        int mid = (l + r) >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
};

struct BinaryIndexedTree {
    vector<int> bit;
    int size;

    BinaryIndexedTree(int n) : size(n){
        bit.resize(n + 1);
    }

    void up(int id) {
        for (; id; id -= id & -id) ++bit[id];
    }
    
    int get(int id) {
        int res = 0;
        for (; id <= size; id += id & -id) res += bit[id];
        return res;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    #ifdef LOCAL_MACHINE
        if (fopen("task.inp", "r")) {
            freopen("task.inp", "r", stdin);
            freopen("task.out", "w", stdout);
        }
    #endif

    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    vector<pair<int, int>> q;
    for (int i = 1; i <= k; ++i) {
        int x; cin >> x;
        q.emplace_back(x, i);
    }
    vector<int> comp;
    for (int i = 1; i <= n; ++i) {
        comp.push_back(a[i]);
        comp.push_back(b[i]);
    }
    for (int i = 1; i <= k; ++i) comp.push_back(q[i - 1].first);

    sort(all(comp));
    comp.resize(unique(all(comp)) - comp.begin());

    int m = comp.size();
    // find last card a <= t < b
    SegmentTree it(m);

    for (auto &[x, id] : q) {
        int p = upper_bound(all(comp), x) - comp.begin();
        it.up(1, 1, m, p, id);
    }

    vector<tuple<int, int, int>> qr;
    for (int i = 1; i <= n; ++i) {
        int l = upper_bound(all(comp), a[i]) - comp.begin();
        int r = upper_bound(all(comp), b[i]) - comp.begin();

        if (l > r) swap(l, r);
        qr.emplace_back(it.get(1, 1, m, l, r - 1), max(a[i], b[i]), i);
    }

    // count number of cards after last >= b
    sort(all(qr)); 
    reverse(all(q));
    BinaryIndexedTree bit(m);

    for (auto &[x, id] : q) {
        int p = upper_bound(all(comp), x) - comp.begin();
        bit.up(p);

        while (qr.size() && get<0>(qr.back()) == id) {
            auto [_, val, i] = qr.back(); qr.pop_back();
            int pos = upper_bound(all(comp), val) - comp.begin();
            int cnt = bit.get(pos);

            if (cnt & 1) {
                if (a[i] > b[i]) swap(a[i], b[i]);
            }
            else {
                if (a[i] < b[i]) swap(a[i], b[i]);
            }
        }
    }

    while (qr.size()) {
        auto [_, val, i] = qr.back(); qr.pop_back();
        int pos = upper_bound(all(comp), val) - comp.begin();
        int cnt = bit.get(pos);

        if (cnt & 1) swap(a[i], b[i]);
    }

    ll res = 0;
    for (int i = 1; i <= n; ++i) res += a[i];

    cout << res << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In member function 'void SegmentTree::up(int, int, int, int, int)':
fortune_telling2.cpp:27:25: error: 'update' was not declared in this scope
   27 |         if (pos <= mid) update(id << 1, l, mid, pos, val);
      |                         ^~~~~~
fortune_telling2.cpp:28:14: error: 'update' was not declared in this scope
   28 |         else update(id << 1 | 1, mid + 1, r, pos, val);
      |              ^~~~~~