Submission #916719

#	Time	Username	Problem	Language	Result	Execution time	Memory
916719		Dec0Dedd	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	2193 ms	112332 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pp;

const int N = 2e5+10;
const int X = 3*N;

int x[N], y[N], a[N], b[N], t[N], n, k;

struct segtree {
    vector<int> t;

    void init(int sz) {
        t.resize(4*sz+1);
    }

    void upd(int v, int l, int r, int p, int vl) {
        if (l == r) {
            t[v]=max(vl, t[v]);
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, vl);
        else upd(2*v+1, m+1, r, p, vl);
        t[v]=max(t[2*v], t[2*v+1]);
    }

    int que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

struct fenwick {
    vector<int> bit;
    int n;

    void init(int sz) {
        n=sz+10;
        bit.assign(n, 0);
    }

    int sum(int r) {
        int res=0;
        for (;r>=0; r=(r&(r+1))-1) res+=bit[r];
        return res;
    }

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

    void upd(int x, int d) {
        for (; x<n; x=x|(x+1)) bit[x]+=d;
    }
};

void solve() {
    cin>>n>>k;

    map<int, int> sc, resc;
    set<int> st;
    for (int i=1; i<=n; ++i) {
        cin>>x[i]>>y[i];
        st.insert(x[i]), st.insert(y[i]);
    }

    for (int i=1; i<=k; ++i) {
        cin>>t[i];
        st.insert(t[i]);
    }

    int i=1;
    for (auto u : st) sc[u]=i, resc[i++]=u;
    for (int i=1; i<=n; ++i) {
        x[i]=sc[x[i]], y[i]=sc[y[i]];
        a[i]=min(x[i], y[i]), b[i]=max(x[i], y[i]);
    }

    segtree tr; tr.init(X+10);
    for (int i=1; i<=k; ++i) t[i]=sc[t[i]], tr.upd(1, 1, X, t[i], i);

    vector<pp> v;
    for (int i=1; i<=n; ++i) {
        int j=tr.que(1, 1, X, a[i], b[i]-1);
        v.push_back({b[i], {-(j+1), i}});
    }

    for (int i=1; i<=k; ++i) v.push_back({t[i], {i, 0}});
    sort(v.begin(), v.end(), greater<pp>());

    fenwick fw; fw.init(X);
    ll ans=0;
    for (auto u : v) {
        if (u.second.first < 0) {
            int j=-u.second.first;
            int vv=fw.que(j, k);

            int vl;
            if (j == 1) {
                if (vv%2) vl=y[u.second.second];
                else vl=x[u.second.second];
            } else {
                if (vv%2) vl=a[u.second.second];
                else vl=b[u.second.second];
            } ans+=resc[vl];
        } else {
            fw.upd(u.second.first, 1);
        }
    } cout<<ans<<"\n";
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

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