Submission #601790

#	Time	Username	Problem	Language	Result	Execution time	Memory
601790		elkernos	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	331 ms	22332 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

struct treemax {
    typedef int T;
    T f(T a, T b) { return max(a, b); }
    vector<T> s;
    int n;
    T unit = 0;
    treemax(int nn, T fil) : s(2 * nn, fil), n(nn), unit(fil) {}
    void update(int p, T v)
    {
        for(s[p += n] = v; p /= 2;) {
            s[p] = f(s[2 * p], s[2 * p + 1]);
        }
    }
    T query(int a, int b)
    {
        T ra = unit, rb = unit;
        for(a += n, b += n + 1; a < b; a /= 2, b /= 2) {
            if(a % 2) ra = f(ra, s[a++]);
            if(b % 2) rb = f(rb, s[--b]);
        }
        return f(ra, rb);
    }
};
struct treesum {
    typedef int T;
    vector<T> s;
    treesum(int n) : s(n) {}
    void update(int pos, T dif)
    {
        for(; pos < (int)s.size(); pos |= pos + 1) {
            s[pos] += dif;
        }
    }
    T query(int pos)
    {
        T res = 0;
        for(pos++; pos >= 1; pos &= pos - 1) {
            res += s[pos - 1];
        }
        return res;
    }
};
#define make_unique(v) sort((v).begin(), (v).end()), (v).erase(unique((v).begin(), (v).end()), (v).end())
struct scaler {
    vector<int> all;
    void insert(int x) { all.emplace_back(x); }
    void init() { make_unique(all); }
    int get(int x) { return lower_bound(all.begin(), all.end(), x) - all.begin(); }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> flip(n + 1);
    vector<int> a(n + 1), b(n + 1), c(q + 1);
    scaler s;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) {
            swap(a[i], b[i]);
            flip[i] = 1;
        }
        s.insert(a[i]), s.insert(b[i]);
    }
    for(int i = 1; i <= q; i++) {
        cin >> c[i];
        s.insert(c[i]);
    }
    s.insert(-1);
    s.init();
    int szz = (int)s.all.size();
    treemax rmq(szz + 123, 0);
    for(int i = 1; i <= q; i++) {
        c[i] = s.get(c[i]);
        rmq.update(c[i], i);
    }
    vector<pair<int, int>> intervals;
    for(int i = 1; i <= n; i++) {
        a[i] = s.get(a[i]), b[i] = s.get(b[i]);
        int when = rmq.query(a[i], b[i] - 1);
        if(when) {
            flip[i] = 1;
        }
        intervals.emplace_back(when + 1, i);
    }
    sort(intervals.begin(), intervals.end());
    treesum sum(szz + 123);
    int ptr = q;
    for(int i = n - 1; i >= 0; i--) {
        while(ptr >= intervals[i].first) {
            sum.update(c[ptr], 1);
            ptr--;
        }
        flip[intervals[i].second] ^= ((q - ptr - sum.query(b[intervals[i].second] - 1)) % 2);
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!flip[i]) {
            ans += s.all[a[i]];
        }
        else {
            ans += s.all[b[i]];
        }
    }
    cout << ans << '\n';
}

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