Submission #317613

#	Time	Username	Problem	Language	Result	Execution time	Memory
317613		tar_palantir	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	396 ms	23288 KiB

fortune_telling2

#include<bits/stdc++.h>
#define allof(a)        a.begin(),a.end()
#define int             long long
#define fi              first
#define se              second
#define pb              push_back
#define F(i,a,b)        for(int i=a;i<=b;i++)
#define D(i,a,b)        for(int i=a;i>=b;i--)
#define inf             0x3f3f3f3f3f3f3f3f
#define mn              200001
#define task            "kosaraju"
using namespace std;
const int mod=          1e9+7;
typedef pair<int,int>   ii;
typedef pair<int,ii>    ip;

int n,k;
ii a[mn],t[mn];

struct interval_tree{
    #define mid         (l+r>>1)
    #define lc          2*id,l,mid
    #define rc          2*id+1,mid+1,r

    int st[4*mn],hi[4*mn];
    void update(int id,int l,int r,int i,int val){
        if(l==r){
            st[id]=1;
            hi[id]=val;
            return;
        }
        if(i<=mid)update(lc,i,val);
        else update(rc,i,val);

        st[id]=st[2*id]+st[2*id+1];
        hi[id]=max(hi[2*id],hi[2*id+1]);
    }
    int getsum(int id,int l,int r,int u,int v){
        if(v<l || r<u)return 0;
        if(u<=l && r<=v)return st[id];
        return getsum(lc,u,v)+getsum(rc,u,v);
    }
    int getmax(int id,int l,int r,int u,int v){
        if(v<l || r<u)return -inf;
        if(u<=l && r<=v)return hi[id];
        return max(getmax(lc,u,v),getmax(rc,u,v));
    }
}st1,st2;
int32_t main()
{
    ios::sync_with_stdio(0);
    #ifdef _TPR_
        freopen("t.inp","r",stdin);
        freopen("t.out","w",stdout);
    #endif
    cin>>n>>k;
    F(i,1,n)cin>>a[i].fi>>a[i].se;
    sort(a+1,a+n+1,[](const ii& a,const ii& b)
        {return max(a.fi,a.se)>max(b.fi,b.se);});
    F(i,1,k){
        cin>>t[i].fi;t[i].se=i;
    }
    sort(t+1,t+k+1,[](const ii& a,const ii& b)
        {return a.fi<b.fi;});
    F(i,1,k)st2.update(1,1,k,i,t[i].se);

    int res=0,cur=k;
    F(i,1,n){
        while(cur && t[cur].fi>=max(a[i].fi,a[i].se)){
            st1.update(1,1,k,t[cur].se,1);
            cur--;
        }
        int l=distance(t,lower_bound(t+1,t+k+1,ii(min(a[i].fi,a[i].se),-1)));
        int r=distance(t,lower_bound(t+1,t+k+1,ii(max(a[i].fi,a[i].se),-1)));
        if(l<r){
            int pos=st2.getmax(1,1,k,l,r-1);
            if(st1.getsum(1,1,k,pos+1,k)&1)res+=min(a[i].fi,a[i].se);
            else res+=max(a[i].fi,a[i].se);
        }
        else{
            if(st1.getsum(1,1,k,1,k)&1)res+=a[i].se;
            else res+=a[i].fi;
        }
    }
    cout<<res;
} 

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void interval_tree::update(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:32:15: note: in expansion of macro 'mid'
   32 |         if(i<=mid)update(lc,i,val);
      |               ^~~
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:22:32: note: in expansion of macro 'mid'
   22 |     #define lc          2*id,l,mid
      |                                ^~~
fortune_telling2.cpp:32:26: note: in expansion of macro 'lc'
   32 |         if(i<=mid)update(lc,i,val);
      |                          ^~
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:23:32: note: in expansion of macro 'mid'
   23 |     #define rc          2*id+1,mid+1,r
      |                                ^~~
fortune_telling2.cpp:33:21: note: in expansion of macro 'rc'
   33 |         else update(rc,i,val);
      |                     ^~
fortune_telling2.cpp: In member function 'long long int interval_tree::getsum(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:22:32: note: in expansion of macro 'mid'
   22 |     #define lc          2*id,l,mid
      |                                ^~~
fortune_telling2.cpp:41:23: note: in expansion of macro 'lc'
   41 |         return getsum(lc,u,v)+getsum(rc,u,v);
      |                       ^~
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:23:32: note: in expansion of macro 'mid'
   23 |     #define rc          2*id+1,mid+1,r
      |                                ^~~
fortune_telling2.cpp:41:38: note: in expansion of macro 'rc'
   41 |         return getsum(lc,u,v)+getsum(rc,u,v);
      |                                      ^~
fortune_telling2.cpp: In member function 'long long int interval_tree::getmax(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:22:32: note: in expansion of macro 'mid'
   22 |     #define lc          2*id,l,mid
      |                                ^~~
fortune_telling2.cpp:46:27: note: in expansion of macro 'lc'
   46 |         return max(getmax(lc,u,v),getmax(rc,u,v));
      |                           ^~
fortune_telling2.cpp:21:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     #define mid         (l+r>>1)
      |                          ~^~
fortune_telling2.cpp:23:32: note: in expansion of macro 'mid'
   23 |     #define rc          2*id+1,mid+1,r
      |                                ^~~
fortune_telling2.cpp:46:42: note: in expansion of macro 'rc'
   46 |         return max(getmax(lc,u,v),getmax(rc,u,v));
      |                                          ^~

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