Submission #1293031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293031		torment	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	2 ms	580 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
/// https://codeforces.com/blog/entry/12781?#comment-175184
bool cmp(array<int, 2>a, array<int, 2>b){
    return max(a[0], a[1]) < max(b[0], b[1]);
}
struct SegmentTree{
    vector<int>sTree;
    SegmentTree(int n){
        sTree.resize(4 * n);
    }
    void Build(int node, int l, int r, vector<int>&v){
        if(l == r){
            sTree[node] = v[l];
        }
        else{
            int mid = (l + r) / 2;
            Build(node * 2, l, mid, v);
            Build(node * 2 + 1, mid + 1, r, v);
            sTree[node] = max(sTree[node * 2], sTree[node * 2 + 1]);
        }
    }

    int Query(int node, int l, int r, int ql, int qr){
        if(ql > r || l > qr){
            return 0;
        }
        if(ql <= l && r <= qr){
            return sTree[node];
        }
        int mid = (l + r) / 2;
        int lc = Query(node * 2, l, mid, ql, qr);
        int rc = Query(node * 2 + 1, mid + 1, r, ql, qr);
        return max(lc, rc);
    }
};
struct BIT{
    vector<int>fen;
    int sz;
    BIT(int n){
        fen.resize(n + 1);
        sz = n;
    }
    void Update(int pos, int val){
        while(pos <= sz){
            fen[pos] += val;
            pos += (pos & -pos);
        }
    }
    int Sum(int pos){
        int s = 0;
        while(pos > 0){
            s += fen[pos];
            pos -= (pos & -pos);
        }
        return s;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>>v(n), ev;
    vector<int>t(q + 1), compress = {-1};
    vector<int>pos(2 * n + q);
    for(int i = 0;i < n;++i){
        cin >> v[i][0] >> v[i][1];
        compress.push_back(v[i][0]);
        compress.push_back(v[i][1]);
    }
    for(int i = 1;i <= q;++i){
        cin >> t[i];
        compress.push_back(t[i]);
    }
    sort(compress.begin(), compress.end());
    compress.erase(unique(compress.begin(), compress.end()), compress.end());
    for(int i = 0;i < n;++i){
        int p = lower_bound(compress.begin(), compress.end(), v[i][0]) - compress.begin();
        v[i][0] = p;
        p = lower_bound(compress.begin(), compress.end(), v[i][1]) - compress.begin();
        v[i][1] = p;
    }
    for(int i = 1;i <= q;++i){
        int p = lower_bound(compress.begin(), compress.end(), t[i]) - compress.begin();
        t[i] = p;
        pos[t[i]] = max(pos[t[i]], i);
        ev.push_back({t[i], i});
    }
    sort(ev.begin(), ev.end());
    sort(v.begin(), v.end(), cmp);
    SegmentTree tree(2 * n + q);
    tree.Build(1, 1, 2 * n + q, pos);
    BIT cnt(q);
    int p = (int)ev.size() - 1;
    long long res = 0;
    for(int i = n - 1;i >= 0;--i){
        while(p >= 1 && max(v[i][0], v[i][1]) <= ev[p][0]){
            cnt.Update(ev[p][1], 1);
            p--;
        }
        int indx = tree.Query(1, 1, 2 * n + q, min(v[i][0], v[i][1]), max(v[i][0], v[i][1]) - 1);
        int f = cnt.Sum(q) - cnt.Sum(indx);
        if(indx && v[i][0] < v[i][1])f++;
        f %= 2;
        res += compress[v[i][f]];
    }
    cout << res << '\n';
}

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