Submission #967131

#	Time	Username	Problem	Language	Result	Execution time	Memory
967131		AlperenT_	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	467 ms	62584 KiB

fortune_telling2

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;
int a[maxn] , b[maxn] , u[maxn] ;
vector <int> cm ; 
vector <int> ch[maxn] ;
struct node{
    int mx , sm ;
    node(){
        mx = -inf ;sm = 0;
    }
};
node seg[12*maxn] ;

void bui(){
    int n = sz(cm) ;
    rep(i , 1 , 4*n){
        seg[i].mx = -inf ;
        seg[i].sm = 0 ;
    }
}

node operator+(node a, node b){
    node r ;
    r.sm = a.sm + b.sm ;
    r.mx = max(a.mx , b.mx) ;
    return r ;
}

void upd(int x , pii a , int p = 1, int l = 0, int r = sz(cm)-1){
    int mid = (l+r)/2 ,pl =p<<1,pr=p<<1|1;
    if(l > x || r < x)return ;
    if(l == r){
        seg[p].mx = max(seg[p].mx , a.F) ;
        seg[p].sm++;
        return ;
    }
    upd(x,a,pl,l,mid);
    upd(x,a,pr,mid+1,r);
    seg[p] = seg[pl] + seg[pr] ;
}
node que(int le ,int ri ,int p = 1 , int l = 0, int r =sz(cm)-1){
    int mid = (l+r)/2 ,pl =p<<1,pr=p<<1|1;
    if(le <= l && r <= ri)return seg[p] ;
    if(ri <= mid){
        return que(le,ri,pl,l,mid);
    }
    if(le > mid){
        return que(le,ri,pr,mid+1,r);
    }
    return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int n , k ;
    cin >> n >> k ;
    rep(i ,1 ,n){
        cin >> a[i] >> b[i] ;
        cm.pb(a[i]) ;cm.pb(b[i]) ;
    }
    rep(i ,1 ,k){
        cin >> u[i] ;
        cm.pb(u[i]); 
    }
    sort(all(cm));
    cm.resize(unique(all(cm))-cm.begin()) ;
    rep(i ,1 , n){
        a[i] = lower_bound(all(cm) , a[i]) - cm.begin() ;
        b[i] = lower_bound(all(cm) , b[i]) - cm.begin() ;
    }
    rep(i , 1 , k){
        u[i] = lower_bound(all(cm) , u[i]) - cm.begin() ;
    }
    rep(i ,1 ,k){
        upd(u[i] , {i,0}); 
    }
    rep(i , 1, n){
        if(a[i] == b[i]){
            continue ;
        }
        int x = que(min(a[i] , b[i]) , max(a[i] , b[i])-1).mx ;
        if(x==-inf){
            x =0; 
        }else{
            if(a[i] < b[i])swap(a[i] , b[i]) ;
        }
        ch[x+1].pb(i) ;
    }
    bui();
    per(i , k+1 , 1){
        if(i!=k+1){
            upd(u[i] , {0 , 1});
        }
        for(int x : ch[i]){
            if(que(max(b[x],a[x]) , sz(cm)-1).sm %2==1){
                swap(a[x] , b[x]) ;
            }
        }
    }
    int ans =0;
    rep(i , 1,n){
        ans += cm[a[i]] ;
    }
    cout << ans << '\n'; 
    return 0 ;
}
/*


*/

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