Submission #930255

#	Time	Username	Problem	Language	Result	Execution time	Memory
930255		parlimoos	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	4 ms	11864 KiB

fortune_telling2

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

ll n , q;
vector<arr(2)> a;
vector<ll> ops;
vector<ll> seg[400001];
ll seginf[400001][2];

void buildSeg(ll l = 0 , ll r = q - 1 , ll i = 1){
    seginf[i][0] = l , seginf[i][1] = r;
    if(l == r) seg[i].pb(ops[l]);
    else{
        ll c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
        seg[i].resize(r - l + 1);
        merge(seg[i << 1].bg() , seg[i << 1].end() , seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , seg[i].bg());
    }
}
ll bsSeg(ll i , ll l , ll r){
    if(i == 1){
        auto itr = lb(seg[i].bg() , seg[i].end() , l);
        if(itr == seg[i].end() or *itr > r) return seginf[i][0];
    }
    if(seginf[i][0] == seginf[i][1]) return seginf[i][1] + 1;
    auto itr = lb(seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , l);
    if(itr != seg[i].end() and *itr <= r) return bsSeg((i << 1) | 1 , l , r);
    return bsSeg(i << 1 , l , r);
}
ll cntSeg(ll l , ll r , ll i , ll val){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return (seginf[i][1] - seginf[i][0] + 1 - (1ll * int(lb(seg[i].bg() , seg[i].end() , val) - seg[i].bg())));
    if(seginf[i][1] >= l and seginf[i][0] <= r) return (cntSeg(l , r , i << 1 , val) + cntSeg(l , r , (i << 1) | 1 , val));
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(ll i = 0 ; i < n ; i++){
        ll d1 , d2;
        cin >> d1 >> d2;
        a.pb({d1 , d2});
    }
    for(ll i = 0 ; i < q ; i++){
        ll d;
        cin >> d;
        ops.pb(d);
    }
    ll o = 0;
    buildSeg();
    for(auto el : a){
        if(el[0] == el[1]) o += (1ll * el[0]);
        else if(el[0] < el[1]){
            ll inx = bsSeg(1 , el[0] , el[1] - 1);
            ll d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]);
            if(inx == 0){
                if((d & 1)) o += (1ll * el[1]);
                else o += (1ll * el[0]);
            }else{
                if((d & 1)) o += (1ll * el[0]);
                else o += (1ll * el[1]);
            }
        }else if(el[1] < el[0]){
            ll inx = bsSeg(1 , el[1] , el[0] - 1);
            ll d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[0]);
            if((d & 1)) o += (1ll * el[1]);
            else o += (1ll * el[0]);
        }
    }
    cout << o;
}

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