Submission #1213874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213874		minhpk	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	644 ms	169640 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int> z[1000005];
vector <int> v;
int rev[1000005];
int q[1000005];
int n;
int f[4000005];
vector<int> f1[4000005];
void update(int id,int l,int r,int pos,int val){
    if (l==r){
        f[id]=val;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,val);
    }else{
        update(id*2+1,mid+1,r,pos,val);
    }
    f[id]=max(f[id*2],f[id*2+1]);
}
int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}

void build(int id,int l,int r){
    if (l==r){
        f1[id].push_back(q[l]);
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    int x=0;
    int y=0;
    while (x<f1[id*2].size() && y<f1[id*2+1].size()){
           if (f1[id*2][x]<f1[id*2+1][y]){
               f1[id].push_back(f1[id*2][x]);
               x++;
           }else{
               f1[id].push_back(f1[id*2+1][y]);
               y++;
           }
    }
    while (x<f1[id*2].size()){
         f1[id].push_back(f1[id*2][x]);
         x++;
    }
    while (y<f1[id*2+1].size()){
         f1[id].push_back(f1[id*2+1][y]);
         y++;
    }
}

int get1(int id,int l,int r,int x,int y,int val){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        int pos=lower_bound(f1[id].begin(),f1[id].end(),val)-f1[id].begin();
        return f1[id].size()-pos;
    }
    int mid=(l+r)/2;
    return get1(id*2,l,mid,x,y,val)+get1(id*2+1,mid+1,r,x,y,val);
}

signed main()
{
  //  freopen("test.txt", "r", stdin);
  //  freopen("o2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
         v.push_back(z[i].first);
         v.push_back(z[i].second);
    }
    for (int i=1;i<=b;i++){
         cin >> q[i];
         v.push_back(q[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    n=v.size();
    for (int i=1;i<=a;i++){
         int pos=lower_bound(v.begin(),v.end(),z[i].first)-v.begin()+1;
         rev[pos]=z[i].first;
         z[i].first=pos;

         pos=lower_bound(v.begin(),v.end(),z[i].second)-v.begin()+1;
         rev[pos]=z[i].second;
         z[i].second=pos;
    }

    for (int i=1;i<=b;i++){
        int  pos=lower_bound(v.begin(),v.end(),q[i])-v.begin()+1;
         rev[pos]=q[i];
         q[i]=pos;
         update(1,1,n,q[i],i);
    }
    build(1,1,b);

    int res=0;
    for (int i=1;i<=a;i++){
         auto [x,y]=z[i];
         int orga=x;
         int orgb=y;
         if (x>y){
            swap(x,y);
         }
         int pos=get(1,1,n,x,y-1);
         // cout << pos << " ";
         int pre=get1(1,1,b,pos,b,y);
         //cout << pos << " " << pre << "\n";
         if (pre%2==1){
            if (pos==0){
                res+=rev[orgb];
            }else{
                res+=rev[x];
            }
             // cout << rev[x] << " ";
         }else{
             // cout << rev[y] << " ";
             if (pos==0){
                res+=rev[orga];
            }else{
                res+=rev[y];
            }
         }
        // cout << res << " ";
    }
    cout << res << "\n";
    return 0;
}



/*
8
01010101
10111000


8
01010101
10111000
10101010


6
110110
011101


001001


8
01010101
11000010

10101010

*/


/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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