Submission #547437

#	Time	Username	Problem	Language	Result	Execution time	Memory
547437		krit3379	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	3097 ms	202700 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define N 200005

class node{
public:
    node *l,*r;
    int cnt;
    node(int cnt):l(NULL),r(NULL),cnt(cnt){}
    node(node *l,node *r):l(l),r(r),cnt(0){
        if(l)cnt+=l->cnt;
        if(r)cnt+=r->cnt;
    }
};
using pnode = node*;

pnode root[N];

pnode cre(int l,int r){
    if(l==r)return new node(0);
    int mid=(l+r)/2;
    return new node(cre(l,mid),cre(mid+1,r));
}

pnode update(pnode x,int l,int r,int p){
    if(l==r)return new node(x->cnt+1);
    int mid=(l+r)/2;
    if(p<=mid)return new node(update(x->l,l,mid,p),x->r);
    else return new node(x->l,update(x->r,mid+1,r,p));
}

int sol(pnode x,int l,int r,int ll,int rr){
    if(l>rr||ll>r||ll>rr)return 0;
    if(ll<=l&&r<=rr)return x->cnt;
    int mid=(l+r)/2;
    return sol(x->l,l,mid,ll,rr)+sol(x->r,mid+1,r,ll,rr);
}

int a[N],b[N],t[N],sz;
long long ans;
map<int,int> mp;

int main(){
    int n,m,i,pmi,pma,pos,l,r,mid,cnt;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        mp[a[i]];
        mp[b[i]];
    }
    for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]];
    for(auto &[x,y]:mp)y=++sz;
    root[0]=cre(1,sz);
    for(i=1;i<=m;i++){
        root[i]=update(root[i-1],1,sz,mp[t[i]]);
    }
    for(i=1;i<=n;i++){
        //search for last t that mi <= t < ma
        auto [mi,ma]=minmax(a[i],b[i]);
        pmi=mp[mi];
        pma=mp[ma];
        pos=0;
        l=1,r=m;
        while(l<=r){
            mid=(l+r)/2;
            cnt=sol(root[m],1,sz,pmi,pma-1)-sol(root[mid-1],1,sz,pmi,pma-1);
            if(cnt)pos=mid,l=mid+1;
            else r=mid-1;
        }
        if(pos){
            cnt=sol(root[m],1,sz,pma,sz)-sol(root[pos],1,sz,pma,sz);
            ans+=(cnt%2)?mi:ma;
        }
        else{
            cnt=sol(root[m],1,sz,pma,sz);
            ans+=(cnt%2)?b[i]:a[i];
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:51:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]];
      |                      ~~~~~^~~~~~~~~~~~

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