Submission #757715

#	Time	Username	Problem	Language	Result	Execution time	Memory
757715		amogususus	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	3056 ms	36436 KiB

fortune_telling2

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,bmi")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
const int maxN=2e5+69;
const int mod=1e9+7;
const int bs=448;
ll n,q,a[maxN],b[maxN],c[maxN],BIT[maxN],st[20][maxN];
ll lg2(ll x){return x?__builtin_clzll(1)-__builtin_clzll(x):-1;}
void update(ll x,ll v){for(;x<maxN;x+=x&-x)BIT[x]+=v;}
ll get(ll x){
    if(x<0)return 0;
    ll r=0;
    for(;x;x-=x&-x)r+=BIT[x];
    return r;
}
ll getmax(ll L,ll R){
    if(L>R)return -1;
    ll i = lg2(R - L + 1);
    return max(st[i][L], st[i][R - (1 << i) + 1]);
}
vector<pll> v;
vector<ll> d;
vector<ll> query[maxN];
ll ans[maxN];
void Enter(){
    cin>>n>>q;
    for(int i=0;i<n;i++)cin>>a[i]>>b[i],d.pb(a[i]),d.pb(b[i]);
    for(int i=0;i<q;i++)cin>>c[i],d.pb(c[i]);
    sort(all(d));
    d.resize(unique(all(d))-d.begin());
    for(int i=0;i<n;i++)a[i]=lower_bound(all(d),a[i])-d.begin();
    for(int i=0;i<n;i++)b[i]=lower_bound(all(d),b[i])-d.begin();
    for(int i=0;i<q;i++)c[i]=lower_bound(all(d),c[i])-d.begin();

    memset(st,-1,sizeof st);
    for(ll i=0;i<q;i++)st[0][c[i]]=max(st[0][c[i]],i);
    for(int i=1;i<20;i++)
        for(int j=0;j+(1<<i)<=n+1;j++)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for(int i=0;i<n;i++){
        ll l=min(a[i],b[i]),r=max(a[i],b[i])-1,w=getmax(l,r);
        if(w!=-1)ans[i]=a[i]<b[i];
        else w=0;
        //cout<<i<<" "<<w<<endl;
        query[w].pb(i);
    }
    ll res=0;
    for(int i=q-1;i>=0;i--){
        update(c[i],1);
        for(auto x:query[i]){
            ll r=max(a[x],b[x])-1;
            ans[x]^=(get(n*3)-get(r))%2;
            if(ans[x])res+=d[b[x]];
            else res+=d[a[x]];
        }
    }
    cout<<res;
}
//amogus
signed main(){
    //open("seq198");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
    Enter();
}

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