Submission #930457

#	Time	Username	Problem	Language	Result	Execution time	Memory
930457		parlimoos	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	369 ms	59848 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'

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

void buildSeg(int l = 0 , int r = q - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r;
    if(l == r) seg[i].pb(ops[l]);
    else{
        int 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());
    }
}
int bsSeg(int i , int l , int 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 << 1) | 1].end() and *itr <= r) return bsSeg((i << 1) | 1 , l , r);
    return bsSeg(i << 1 , l , r);
}
int cntSeg(int l , int r , int i , int val){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return (seginf[i][1] - seginf[i][0] + 1 - 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(int i = 0 ; i < n ; i++){
        int d1 , d2;
        cin >> d1 >> d2;
        a.pb({d1 , d2});
    }
    for(int i = 0 ; i < q ; i++){
        int d;
        cin >> d;
        ops.pb(d);
    }
    ll o = 0;
    buildSeg();
    for(auto el : a){
        if(el[0] == el[1]){
            o += el[0];
        }else if(el[0] < el[1]){
            int inx = bsSeg(1 , el[0] , el[1] - 1);
            int d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]);
            if(inx == 0){
                if((d & 1)) o += el[1];
                else o += el[0];
            }else{
                if((d & 1)) o += el[0];
                else o += el[1];
            }
        }else if(el[1] < el[0]){
            int inx = bsSeg(1 , el[1] , el[0] - 1);
            int d = 0;
            if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[0]);
            if((d & 1)) o += el[1];
            else o += el[0];
        }
    }
    cout << o;
}

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