Submission #479454

#	Time	Username	Problem	Language	Result	Execution time	Memory
479454		hidden1	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	545 ms	55204 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cerr << "Line: " << __LINE__ << endl; \
    prllDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void prllDebug(const char* name, T&& arg1) { cerr << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void prllDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cerr.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    prllDebug(end, args...);
}
 
const ll MAX_N = 6e5 + 10;
ll a[MAX_N], b[MAX_N];
ll n;
ll k;
ll t[MAX_N];

ll tree[4 * MAX_N];
ll treeUnder[MAX_N];
ll treeSum[4 * MAX_N];

void build(ll curr, ll l, ll r) {
    if(l == r) {
        tree[curr] = treeUnder[l];
        return;
    }
    ll m = (l + r) / 2ll;
    build(curr * 2, l, m);
    build(curr * 2 + 1, m + 1, r);
    tree[curr] = max(tree[curr * 2], tree[curr * 2 + 1]);
}

ll query(ll curr, ll l, ll r, ll ql, ll qr) {
    if(ql <= l && r <= qr) {
        return tree[curr];
    } else if(l > qr || r < ql) {return -1;}
    ll m = (l + r) / 2ll;
    return max(query(curr * 2, l, m, ql, qr), query(curr * 2 + 1, m + 1, r, ql, qr));
}

void updSum(ll curr, ll l, ll r, ll ind, ll val) {
    if(l == r && l == ind) {
        treeSum[curr] += val;
        return;
    } else if(ind < l || r < ind) {return;}
    ll m = (l + r) / 2ll;
    updSum(curr * 2, l, m, ind, val);
    updSum(curr * 2 + 1, m + 1, r, ind, val);
    treeSum[curr] = treeSum[curr * 2] + treeSum[curr * 2 + 1];    
}

ll querySum(ll curr, ll l, ll r, ll ql, ll qr) {
    if(ql <= l && r <= qr) {
        return treeSum[curr];
    } else if(l > qr || r < ql) {return 0;}
    ll m = (l + r) / 2ll;
    int ret = querySum(curr * 2, l, m, ql, qr) + querySum(curr * 2 + 1, m + 1, r, ql, qr);
    return ret;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cerr.tie(NULL);
    fill(treeUnder, treeUnder + MAX_N, -1);
    fill(tree, tree + 4 * MAX_N, -1);

    cin >> n >> k;
    vector<ll> c;
    for(ll i = 0; i < n; i ++) {
        cin >> a[i] >> b[i];
        c.push_back(a[i]);
        c.push_back(b[i]);
    }
    for(ll i = 0; i < k; i ++) {
        cin >> t[i];
        c.push_back(t[i]);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for(ll i = 0; i < n; i ++) {
        a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
        b[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
    } 
    for(ll i = 0; i < k; i ++) {
        t[i] = lower_bound(c.begin(), c.end(), t[i]) - c.begin();
        treeUnder[t[i]] = i;
    } 

    build(1, 0, MAX_N - 1);

    vector<pair<ll, ll> > srt;
    vector<pair<ll, ll> > readyTo;
    for(ll i = 0; i < n; i ++) {
        srt.push_back({max(a[i], b[i]), i});
    }

    for(ll i = 0; i < k; i ++) {   
        readyTo.push_back({t[i], i});
    }

    sort(srt.rbegin(), srt.rend());
    sort(readyTo.rbegin(), readyTo.rend());

    ll ptr = 0, ret = 0;

    for(ll i = 0; i < n; i ++) {
        ll ind = srt[i].second;

        while(ptr < k && srt[i].first <= readyTo[ptr].first) {
            updSum(1, 0, MAX_N - 1, readyTo[ptr].second, 1);
            ptr ++;
        }

        if(a[ind] == b[ind]) {
            ret += c[a[ind]];
            continue;
        }

        ll mn = min(a[ind], b[ind]), mx = max(a[ind], b[ind]);
        ll l = query(1, 0, MAX_N - 1, mn, mx - 1);
        ll cnt = querySum(1, 0, MAX_N - 1, l + 1, MAX_N - 1);

        if(l == -1) {
            if(cnt & 1) {
                ret += c[b[ind]];
            } else {                
                ret += c[a[ind]];
            }
        } else {
            if(cnt & 1) {
                ret += c[mn];
            } else {             
                ret += c[mx];
            }            
        }
    }

    cout << ret << endl;

    return 0;
}

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