Submission #668614

#	Time	Username	Problem	Language	Result	Execution time	Memory
668614		radal	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	3075 ms	8368 KiB

fortune_telling2

#include <bits/stdc++.h> 
#include <math.h> 
//in the name of god,aka allah 
//**gray sety orz** 
using namespace std; 
#define pi pair<int , int> 
#define pii pair<long long , pair<long long , long long>> 
const int maxm = 2e5 + 5; 
const long long mod = 1e9 + 7 ; 
typedef long long ll; 
ll n,m; 
bool isval(int mid){ 
    //cout << mid <<" " << mid*mid-mid <<endl; 
    if (((mid-1)*mid)/2 < m) return 0; 
    return 1; 
} 
int darage[maxm]; 
ll ss; 
bool mm; 
queue<int> q; 
bool vis[maxm] , gos[maxm]; 
pi pedaret[maxm*2]; 
int rp[maxm*2]; 
pi w[maxm]; 
ll dp[maxm]; 
//ll rw[maxm][maxm]; 
bool cmp(pi x , pi y){ 
    return max(x.first,x.second)>max(y.first,y.second); 
} 
inline void build(int v=1 , int l=1 , int r=m+1){    
    if(r-l==1){ rp[v] = 0, pedaret[v]={darage[l],l}; return; } 
    int mid = (l+r)/2; 
    build(v*2,l,mid) , build(v*2+1,mid,r); 
    rp[v]=rp[v*2]+rp[v*2+1]; 
    pedaret[v]=max(pedaret[v*2],pedaret[v*2+1]); 
} 
inline void shift(int id , int v=1 , int l=1 , int r=m+1){ 
    if(r-l==1){ rp[v] = 1 , pedaret[v] = {-1 , l}; return; } 
    int mid=(l+r)/2; 
    if(id<mid) shift(id , v*2 , l , mid); 
    else shift(id , v*2+1 , mid , r); 
    rp[v] = rp[v*2] + rp[v*2+1]; 
    pedaret[v] = max(pedaret[v*2] , pedaret[v*2+1]); 
} 
inline int upd(int x , int v=1 , int l=1 , int r=m+1){ 
    if(r-l<=1) return l; 
    int mid = (l+r)/2; 
    if(pedaret[v*2+1].first>=x) return upd(x,v*2+1,mid,r); 
    else return upd(x,v*2,l,mid); 
} 
inline int get(int lx , int rx , int v=1 , int l=1 , int r=m+1){ 
    if(r<=lx||rx<=l) return 0; 
    if(lx<=l&&r<=rx) return rp[v]; 
    int mid = (l+r)/2; 
    return get(lx,rx,v*2,l,mid)+get(lx,rx,v*2+1,mid,r); 
} 
map<ll,ll> mp; 
int main(){ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin >>n>>m; 
    for (int i=1; i<=n; i++) cin>>w[i].first>>w[i].second; 
    sort(w+1,w+n+1,cmp); 
    for (int i=1; i<=m; i++) cin>>darage[i]; 
    build(); 
    //cout<<55; 
    for (int i=1; i<=n; i++){ 
        mm = 0; 
        if (w[i].second>w[i].first) swap(w[i].first,w[i].second) , mm = 1; 
        while (pedaret[1].first>=w[i].first) shift(pedaret[1].second); 
        //cout<<<69; 
        if (pedaret[1].first>=w[i].second){//cout<<44<<endl; 
            //cout<<get(upd(w[i].second),m+1)<<endl; 
            if (get(upd(w[i].second),m+1)%2) ss+=w[i].second; 
            else ss+=w[i].first; 
        } 
        //cout<<73; 
        else{ 
            ss+=((mm)?((rp[1]%2)?w[i].first:w[i].second):(((rp[1]%2)?w[i].second:w[i].first))); 
        } 
        //cout<<i<<endl; 
    } 
    cout<<ss; 
}

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