Submission #1100894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100894		lampooppp	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	876 ms	44696 KiB

fortune_telling2

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

const int N=2e5;

int st[12*N+1],n,q;

void update(int x, int low, int hi ,int i, int k)
{
    if(low==hi) {st[x]=max(st[x],k); return;}
    int mid = low+hi>>1;
    if(i<=mid) update(x*2,low,mid,i,k);
    else update(x*2+1,mid+1,hi,i,k);
    st[x]=max(st[x*2],st[x*2+1]);
}

int getmx(int x, int low ,int hi, int i, int j)
{
    if(low>hi || low >j || hi < i) return 0;
    if(low>=i && hi<=j) return st[x];
    int mid=low+hi>>1;
    return max(getmx(x*2,low,mid,i,j), getmx(x*2+1,mid+1,hi,i,j));
}

int bit[3*N+100];

void add(int x)
{
    for(; x<=2*n+q+1;x+=x&(-x))
    {
        bit[x]++;
    }
}

int get(int x)
{
    int ans=0;
    for(; x>0;x-=x&(-x))
    {
        ans+=bit[x];
    }
    return ans;
}

int a[N+1],b[N+1],t[N+1];
int ag[N+1],bg[N+1];
int last[N+1];
int id[N+1];
map<int,int> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i] >> b[i];
        ag[i]=a[i];
        bg[i]=b[i];
        mp[a[i]]=0;
        mp[b[i]]=0;
    }
    for(int i=1;i<=q;++i)
    {
        cin >> t[i];
        mp[t[i]]=0;
    }
    int z=0;
    for(auto & k : mp) k.second = ++z;
    for(int i=1;i<=q;++i)
    {
        t[i] = mp[t[i]];
        update(1,1,2*n+q,t[i],i);
       // cout << t[i] << '\n';
    }
    for(int i=1;i<=n;++i)
    {
        a[i]=mp[a[i]];
        b[i]=mp[b[i]];
        last[i]=getmx(1,1,2*n+q,min(a[i],b[i]),max(a[i],b[i])-1);
      //  cout << a[i] << " " << b[i] << '\n';
        //cout << last[i] << " ";
        id[i]=i;
    }
   // cout << '\n';
    sort(id+1,id+n+1,[] (int x, int y)
         {
             return last[x]>last[y];
         });
   // cout << "WTF";
    long long ans=0;
    int now=q;
    for(int i=1;i<=n;++i)
    {
        int j = id[i];
       // cout << j << " " << last[j] << '\n';
        while(now > 0 && now>=last[j])
        {
            add(t[now]);
           // cout << "ADD : " << t[now] << '\n';
            now--;
        }
       // cout << "GET : " << max(a[j],b[j]) << '\n';
        int k = get(2*n+q+1) - get(max(a[j],b[j])-1);
       // cout << k << '\n';
        int cc=0;
        if(a[j]>b[j])
        {
            swap(a[j],b[j]);
            swap(ag[j],bg[j]);
            cc=1;
        }
        if(last[j]>0) cc=1;
        k%=2;
        cc^=k;
        if(cc) ans+=(long long)bg[j];
        else ans+=(long long)ag[j];
    }
    cout << ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:11:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'int getmx(int, int, int, int, int)':
fortune_telling2.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid=low+hi>>1;
      |             ~~~^~~

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