Submission #775623

#	Time	Username	Problem	Language	Result	Execution time	Memory
775623		Essa2006	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1038 ms	87404 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=20, s_p=1<<pr, e_p=(1<<(pr+1))-1;
int n, k;
vector<int>A, B, T, S_mx, S_sum;
map<int, int>mp, inv;

void pre(){
    A.clear(), B.clear(), T.clear(), mp.clear(), inv.clear(), S_mx.clear(), S_sum.clear();
    A.resize(n+1), B.resize(n+1), T.resize(k+1), S_mx.resize(1<<(pr+1), -1), S_sum.resize(1<<(pr+1));
}

void update_sum(int ind, int delta){
    S_sum[ind]+=delta;
    while(ind/=2)
        S_sum[ind]+=delta;
}
void update_mx(int ind, int new_){
    S_mx[ind]=max(S_mx[ind], new_);
    while(ind/=2)
        S_mx[ind]=max(S_mx[ind], new_);
}

int get_sum(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return 0;
    if(l>=u && r<=v)
        return S_sum[id];
    int md=(l+r)/2;
    int fir=get_sum(id*2, u, v, l, md);
    int sec=get_sum(id*2+1, u, v, md+1, r);
    return fir+sec;
}
int get_mx(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return -1;
    if(l>=u && r<=v)
        return S_mx[id];
    int md=(l+r)/2;
    int fir=get_mx(id*2, u, v, l, md);
    int sec=get_mx(id*2+1, u, v, md+1, r);
    return max(fir, sec);
}

void comp(){
    vector<int>S=T;
    for(int i=1;i<=n;i++){
        S.push_back(A[i]);
        S.push_back(B[i]);
    }
    sort(all(S));
    int cnt=1;
    for(int i=0;i<S.size();i++){
        if(!i || S[i]!=S[i-1]){
            mp[S[i]]=cnt, inv[cnt]=S[i], cnt++;
        }
    }
    for(int i=1;i<=n;i++){
        A[i]=mp[A[i]], B[i]=mp[B[i]];
    }
    for(int j=0;j<k;j++){
        T[j]=mp[T[j]];
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    pre();
    for(int i=1;i<=n;i++){
        cin>>A[i]>>B[i];
    }
    for(int j=0;j<k;j++){
        cin>>T[j];
    }
    comp();
    for(int j=0;j<k;j++){
        update_mx(T[j]+s_p, j);
    }
    vector<vector<int>>Q(k);
    ll ans=0;
    for(int i=1;i<=n;i++){
        int mn=min(A[i], B[i]), mx=max(A[i], B[i]);
        if(mn==mx){
            ans+=inv[mn];
            continue;
        }
        int mx_ind=get_mx(1, mn+s_p, mx-1+s_p, s_p, e_p);
        Q[(mx_ind>=0?mx_ind:0)].push_back((mx_ind>=0?i:-i));
    }
    
    for(int j=k-1;j>=0;j--){
        update_sum(T[j]+s_p, 1);
        for(int f=0;f<Q[j].size();f++){
            int mn=min(A[abs(Q[j][f])], B[abs(Q[j][f])]), mx=max(A[abs(Q[j][f])], B[abs(Q[j][f])]);
            int sum=get_sum(1, mx+s_p, e_p, s_p, e_p);
            if(Q[j][f]<0){
                if(sum&1)
                    ans+=inv[B[abs(Q[j][f])]];
                else
                    ans+=inv[A[abs(Q[j][f])]];
                continue;
            }
            if(sum&1)
                ans+=inv[mn];
            else
                ans+=inv[mx];
        }
    }
    cout<<ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void comp()':
fortune_telling2.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int f=0;f<Q[j].size();f++){
      |                     ~^~~~~~~~~~~~

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