Submission #1292351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292351		haha	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	570 ms	24044 KiB

fortune_telling2

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int INF=1e9;

int n,k,Q;
int a[maxn],b[maxn];
vector<int> nen;
int q[maxn];
int pos[maxn];
int id[maxn];
int cnt[maxn];
struct node{
    int Max,sum;
};
node tree[4*maxn];

node mergeNode(node L,node R)
{
    node res;
    res.Max=max(L.Max,R.Max);
    res.sum=L.sum+R.sum;
    return res;
}

void update(int id,int l,int r,int pos,int val,int type)
{
    if(r<pos||pos<l) return;
    if(l==r){
        if(type==1) tree[id].Max=max(tree[id].Max,val);
        else tree[id].sum+=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,pos,val,type);
    update(id*2+1,mid+1,r,pos,val,type);
    tree[id]=mergeNode(tree[id*2],tree[id*2+1]);
}

node get(int id,int l,int r,int u,int v)
{
    if(r<u||v<l) return {0,0};
    if(u<=l&&r<=v) return tree[id];
    int mid=(l+r)/2;
    return mergeNode(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main()
{
    cin>>n>>Q;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        nen.push_back(a[i]);
        nen.push_back(b[i]);
    }
    for(int i=1;i<=Q;i++){
        cin>>q[i];
        nen.push_back(q[i]);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin()+1;
        b[i]=lower_bound(nen.begin(),nen.end(),b[i])-nen.begin()+1;
    }
    for(int i=1;i<=Q;i++){
        q[i]=lower_bound(nen.begin(),nen.end(),q[i])-nen.begin()+1;
        update(1,1,nen.size(),q[i],i,1);
    }
    for(int i=1;i<=n;i++){
        if(a[i]<=b[i]){
            pos[i]=get(1,1,nen.size(),a[i],b[i]-1).Max;
        }
        else pos[i]=get(1,1,nen.size(),b[i],a[i]-1).Max;
        id[i]=i;
    }
    sort(id+1,id+n+1,[](int x,int y){
         return pos[x]<pos[y];
    });
    int j=Q;
    for(int i=n;i>=1;i--){
        while(pos[id[i]]<j&&j>=1){
            update(1,1,nen.size(),q[j],1,2);
            j--;
        }
        cnt[id[i]]=get(1,1,nen.size(),max(a[id[i]],b[id[i]]),nen.size()).sum;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        int val;
        if(pos[i]==0){
            if(cnt[i]%2==0) val=a[i];
            else val=b[i];
        }
        else{
            if(cnt[i]%2==0){
               val=max(a[i],b[i]);
            }
            else val=min(a[i],b[i]);
        }
        ans+=nen[val-1];
    }
    cout<<ans;
}

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