Submission #317641

#	Time	Username	Problem	Language	Result	Execution time	Memory
317641		Saacoota	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	326 ms	27516 KiB

fortune_telling2

#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair < int , int >
#define pb push_back
#define eb emplace_back

using namespace std;

int f[200010][20] , BIT[200010] , c[200010];
ii a[200010];

void upl(int x) {
    for ( ; x > 0 ; x -= (-x & x))
        BIT[x]++;
}

int dwl(int x) {
    int tmp = 0;
    for ( ; x <= 200000 ; x += (-x & x))
        tmp += BIT[x];
    return tmp;
}

int get(int l,int r) {
    if (l > r) return 0;
    int k = __lg(r - l + 1);
    return max(f[l][k] , f[r - (1 << k) + 1][k]);
}

int main() {
//    freopen("JOI14.INP","r",stdin);
//    freopen("JOI14.OUT","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n , k;
    cin >> n >> k;
    vector < int > vc;
    vector < ii > cat;
    for (int i = 1 ; i <= n ; ++i) cin >> a[i].fi >> a[i].se;
    for (int i = 1 ; i <= k ; ++i) {
        cin >> c[i];
        vc.pb(c[i]);
    }
    sort(vc.begin(),vc.end());
    for (int i = 1 ; i <= k ; ++i) {
        c[i] = lower_bound(vc.begin() , vc.end() , c[i]) - vc.begin() + 1;
        f[c[i]][0] = i;
    }
    int l = __lg(k);
    for (int j = 1 ; j <= l ; ++j)
    for (int i = 1 ; i + (1 << j) - 1 <= k ; ++i)
    f[i][j] = max(f[i][j - 1] , f[i + (1 << (j - 1))][j - 1]);
    for (int i = 1 ; i <= n ; ++i) {
        int l = lower_bound(vc.begin() , vc.end() , min(a[i].fi , a[i].se)) - vc.begin() + 1;
        int r = lower_bound(vc.begin() , vc.end() , max(a[i].fi , a[i].se)) - vc.begin();
        cat.eb(get(l , r) , i);
    }
    sort(cat.begin(),cat.end());
    int cur = 1;
    long long ans = 0;
    for (auto v : cat) {
        while (cur <= v.fi) upl(c[cur]) , cur++;
        int ma = max(a[v.se].fi , a[v.se].se);
        int res = k - (lower_bound(vc.begin() , vc.end() , ma) - vc.begin());
        ma = lower_bound(vc.begin() , vc.end() , ma) - vc.begin() + 1;
        res -= dwl(ma);
        if (v.fi) ans += ((a[v.se].fi < a[v.se].se) ^ (res & 1) ? a[v.se].se : a[v.se].fi);
        else ans += (res & 1 ? a[v.se].se : a[v.se].fi);
    }
    cout << ans;
}

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