Submission #601768

#	Time	Username	Problem	Language	Result	Execution time	Memory
601768		elkernos	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	1 ms	340 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)
    {
        p += n;
        for(s[p] = f(s[p], 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;
    T f(T a, T b) { return a + b; }
    vector<T> s;
    int n;
    T unit = 0;
    treesum(int nn, T fil) : s(2 * nn, fil), n(nn), unit(fil) {}
    void update(int p, T v)
    {
        p += n;
        for(s[p] = f(s[p], 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);
    }
};

#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]);
    }
    vector<int> ra = a, rb = b;
    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 + 100, 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 != 0) {
            flip[i] = 1;
        }
        intervals.emplace_back(when + 1, i);
    }
    sort(intervals.begin(), intervals.end());
    treesum sum(szz + 100, 0);
    int ptr = q;
    for(int i = n - 1; i >= 0; i--) {
        while(ptr >= intervals[i].first) {
            sum.update(c[ptr], 1);
            ptr--;
        }
        flip[i] ^= (sum.query(b[i], szz + 50) % 2);
    }
    long long ans = 0;
    for(int i = 1; i <= n; ++i) {
        if(!flip[i]) {
            ans += ra[i];
        }
        else {
            ans += rb[i];
        }
    }
    cout << ans << '\n';
}

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