Submission #997870

#	Time	Username	Problem	Language	Result	Execution time	Memory
997870		irmuun	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	351 ms	58252 KiB

fortune_telling2

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pll pair<ll,ll>

struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=max(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(L>R||r<L||R<l) return 0;
        if(L<=l&&r<=R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll pos,ll val){
        if(l>pos||r<pos) return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,pos,val);
        update(node*2+1,mid+1,r,pos,val);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

typedef tree<
pll,
null_type,
less<pll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll a[n+5],b[n+5];
    for(ll i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    ll ts[k+5];
    pair<ll,ll>t[k+5];
    for(ll i=1;i<=k;i++){
        cin>>t[i].ff;
        t[i].ss=i;
        ts[i]=t[i].ff;
    }
    sort(t+1,t+k+1);
    ll T[k+5];
    for(ll i=1;i<=k;i++){
        T[i]=t[i].ff;
    }
    segtree sg(k);
    for(ll i=1;i<=k;i++){
        sg.update(1,1,k,i,t[i].ss);
    }
    ordered_set st;
    ll ans=0,last[n+5];
    vector<array<ll,2>>que[k+5];
    for(ll i=1;i<=n;i++){
        ll l,r;
        l=lower_bound(T+1,T+k+1,min(a[i],b[i]))-T;
        r=lower_bound(T+1,T+k+1,max(a[i],b[i]))-T;
        r--;
        last[i]=0;
        if(l<=r){
            last[i]=sg.query(1,1,k,l,r);
        }
        que[last[i]].pb({min(a[i],b[i]),i});
    }
    ll c[n+5];
    map<ll,ll>cnt;
    for(ll i=k;i>=0;i--){
        for(auto [x,j]:que[i]){
            c[j]=st.size()-st.order_of_key({x,0});
        }
        if(i>0){
            st.insert({ts[i],++cnt[ts[i]]});
        }
    }
    for(ll i=1;i<=n;i++){
        ll pos=0;
        if(last[i]>0){
            if(a[i]<b[i]) pos=1;
        }
        pos=(pos+c[i])%2;
        if(pos==0) ans+=a[i];
        else ans+=b[i];
    }
    cout<<ans;
}

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