Submission #940469

#	Time	Username	Problem	Language	Result	Execution time	Memory
940469		a_l_i_r_e_z_a	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	174 ms	22292 KiB

fortune_telling2

// In the name of God
// Hope is last to die
 
#include <bits/stdc++.h>
using namespace std;
 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
 
const int maxn = 2e5 + 5, lg = 19;
const int inf = 1e9 + 7;
int n, q, rmq[maxn][lg], fen[maxn];
pii a[maxn], b[maxn];

bool cmp(pii x, pii y){
    return max(x.F, x.S) > max(y.F, y.S);
}

void upd(int i){
    for(i++; i <= q; i += i & -i) fen[i]++;
}

int get_(int i){
    int res = 0;
    for(i++; i; i &= i - 1) res += fen[i];
    return res;
}

int get(int i){
    return get_(q - 1) - get_(i);
}

int get_rmq(int l, int r){
    int bit = 31 - __builtin_clz(r - l);
    return max(rmq[l][bit], rmq[r - (1ll << bit)][bit]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n ; i++) cin >> a[i].F >> a[i].S;
    sort(a, a + n, cmp);
    for(int i = 0; i < q; i++){
        cin >> b[i].F;
        b[i].S = i;
    }
    sort(b, b + q);
    for(int i = q - 1; i >= 0; i--){
        rmq[i][0] = b[i].S;
        for(int bit = 1; bit < lg; bit++){
            rmq[i][bit] = rmq[i][bit - 1];
            if(i + (1ll << (bit - 1)) < q){
                smax(rmq[i][bit], rmq[i + (1ll << (bit - 1))][bit - 1]);
            }
        }
    }
    int cur = q - 1;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        int mn = min(a[i].F, a[i].S), mx = a[i].F + a[i].S - mn;
        while(cur >= 0 && b[cur].F >= mx) upd(b[cur--].S);
        int j = lower_bound(b, b + q, mp(mn, 0)) - b;
        int k = lower_bound(b, b + q, mp(mx, 0)) - b;
        if(j == q || b[j].F >= mx){
            int x = get(-1);
            if(x % 2) ans += a[i].S;
            else ans += a[i].F;
        }
        else{
            int g = get_rmq(j, k);
            int x = get(g);
            if(x % 2) ans += mn;
            else ans += mx;
        }
    }
    cout << ans << '\n';

    return 0;
}

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