Submission #1272699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272699		tdiv	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	2 ms	332 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define MAX 202207

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FOD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define all(x) (x).begin(), (x).end()
#define ii pair<int, int>

#define TASK ""

int trung[MAX * 3];

struct IntervalTree {

    vector<int> st;

    IntervalTree() {}
    IntervalTree(int _sz) {
        st.assign((_sz << 2) + 5, 0);
    }

    void build(int id, int l, int r) {
        if (l > r) return;

        if (l == r) {
            st[id] = trung[l];
            return;
        }

        int mid = (l + r) >> 1, _id = id << 1;
        build(_id, l, mid);
        build(_id | 1, mid + 1, r);

        st[id] = max(st[_id], st[_id | 1]);
    }

    int get(int id, int l, int r, int qL, int qR) {
        if (l > qR || r < qL) return 0;

        if (l >= qL && r <= qR) return st[id];

        int mid = (l + r) >> 1, _id = id << 1;
        return max(get(_id, l, mid, qL, qR), get(_id | 1, mid + 1, r, qL, qR));
    }

};

struct BIT {

    int n;
    vector<int> bit;

    BIT() {}
    BIT(int _n) {
        n = _n;
        bit.assign(n + 3, 0);
    }

    void update(int i, int x) {
        for (; i <= n; i += i & (-i)) {
            bit[i] += x;
        }
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & (-i)) {
            res += bit[i];
        }
        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }

};

int n, nQuery;
ii p[MAX], q[MAX];
vector<ii> bucket[MAX];
bool flip[MAX];
int query[MAX];

void waguri(void) {
    cin >> n >> nQuery;
    vector<int> comp;
    FOR(i, 1, n) {
        cin >> p[i].first >> p[i].second;
        comp.push_back(p[i].first);
        comp.push_back(p[i].second);
    }
    FOR(i, 1, nQuery) {
        cin >> query[i];
        comp.push_back(query[i]);
    }
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());

    FOR(i, 1, n) {
        int x = lower_bound(all(comp), p[i].first) - comp.begin() + 1;
        int y = lower_bound(all(comp), p[i].second) - comp.begin() + 1;
        q[i] = make_pair(x, y);
    }

    FOR(i, 1, nQuery) {
        query[i] = lower_bound(all(comp), query[i]) - comp.begin() + 1;
    }

    int m = comp.size();
    IntervalTree myIT(m);
    FOR(i, 1, m) trung[i] = 0;
    FOR(i, 1, nQuery) trung[query[i]] = i;

    myIT.build(1, 1, m);

    FOR(i, 1, n) {
        int x = min(q[i].first, q[i].second), y = max(q[i].first, q[i].second);
        int p = (x < y ? myIT.get(1, 1, m, x, y - 1) : 0);
        if (p > 0) flip[i] = true;
        bucket[p + 1].push_back(make_pair(i, y));
    }

    long long ans = 0;

    BIT myBIT(m);
    FOD(i, nQuery, 1) {
        myBIT.update(query[i], 1);

        for (auto [i, y] : bucket[i]) {
            int binh = myBIT.get(y, m);
            if (flip[i]) ans += (binh & 1 ? min(p[i].first, p[i].second) : max(p[i].first, p[i].second));
            else ans += (binh & 1 ? p[i].second : p[i].first);
        }
    }

    cout << ans << "\n";

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int tt = 1;
    waguri();

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65