oj.uz

Submission #908052

# Submission time Handle Problem Language Result Execution time Memory
908052 2024-01-16T07:32:09 Z Warinchai Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1133 ms 120272 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N=6e5+1;
struct segtree{
    int info[2400005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=val);
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    int fmax(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return max(fmax(st,m,i*2,l,r),fmax(m+1,en,i*2+1,l,r));
    }
}str;
struct fenwick{
    int info[600005];
    void upd(int x,int val){
        for(int i=x;i<=600000;i+=(i&-i)){
            info[i]+=val;
        }
    }
    int fsum(int x){
        int sum=0;
        for(int i=x;i>0;i-=(i&-i)){
            sum+=info[i];
        }
        return sum;
    }
}ftr;
int ca[600005];
int cb[600005];
int cca[600005];
int ccb[600005];
vector<int>v;
vector<int>q;
vector<int>nq;
map<int,int>mp;
vector<pair<int,int> >qr[600005];
int side[600005];
int val[600005];
int ans[600005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>ca[i]>>cb[i];
        if(!mp[ca[i]])mp[ca[i]]++,v.push_back(ca[i]);
        if(!mp[cb[i]])mp[cb[i]]++,v.push_back(cb[i]);
    }
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        q.push_back(x);
        if(!mp[x])mp[x]++,v.push_back(x);
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=k;i++){
        int id=lower_bound(v.begin(),v.end(),q[i-1])-v.begin()+1;
        //cerr<<q[i-1]<<":"<<id<<"\n";
        nq.push_back(id);
        str.upd(1,N,1,id,i);
        //cerr<<str.fmax(1,N,1,id,id)<<":"<<id<<"\n";
    }
    for(int i=0;i<n;i++){
        int id=lower_bound(v.begin(),v.end(),ca[i])-v.begin()+1;
        cca[i]=id;
        id=lower_bound(v.begin(),v.end(),cb[i])-v.begin()+1;
        ccb[i]=id;
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(ca[i]<cb[i]){
            int l=str.fmax(1,N,1,cca[i],ccb[i]-1);
            qr[l].push_back({i,ccb[i]});
            //cerr<<"L:"<<l<<" "<<ccb[i]<<"\n";
            side[i]=1;
            if(l==0)side[i]=0;
        }else if(ca[i]>cb[i]){
            int l=str.fmax(1,N,1,ccb[i],cca[i]-1);
            qr[l].push_back({i,cca[i]});
            //cerr<<"L:"<<l<<" "<<cca[i]<<"\n";
            side[i]=0;
        }else{
            side[i]=0;
            sum+=ca[i];
        }
    }
    /*for(int i=0;i<n;i++){
        cerr<<cca[i]<<" "<<ccb[i]<<"\n";
    }
    for(int i=1;i<=8;i++){
        //cerr<<str.fmax(1,N,1,i,i)<<" ";
    }cerr<<endl;*/
    int cur=6e5;
    for(int i=k;i>=1;i--){
        //cerr<<i<<"?"<<nq[i-1]<<"\n";
        while(cur>i){
            //cerr<<"cur:"<<cur<<"\n";
            for(auto x:qr[cur]){
                int id=x.second;
                int am=ftr.fsum(6e5)-ftr.fsum(id-1);
                //cerr<<x.first<<" "<<ftr.fsum(2e5)<<"-"<<ftr.fsum(id-1)<<"\n";
                if(am%2==1)side[x.first]^=1;
                ans[x.first]=side[x.first];
                sum+=ans[x.first]==0?ca[x.first]:cb[x.first];
                //cerr<<am<<" ans"<<x.first<<" "<<(ans[x.first]==0?ca[x.first]:cb[x.first])<<"\n";
            }
            cur--;
        }
        //cerr<<"work\n";
        ftr.upd(nq[i-1],1);
        //cerr<<"work\n";
    }
    while(cur>=0){
        for(auto x:qr[cur]){
            int id=x.second;
            int am=ftr.fsum(6e5)-ftr.fsum(id-1);
            if(am%2==1)side[x.first]^=1;
            ans[x.first]=side[x.first];
            sum+=ans[x.first]==0?ca[x.first]:cb[x.first];
            //cerr<<am<<" ans"<<x.first<<" "<<(ans[x.first]==0?ca[x.first]:cb[x.first])<<"\n";
        }
        cur--;
    }
    cout<<sum;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 39512 KB Output is correct
2 Correct 13 ms 39516 KB Output is correct
3 Correct 14 ms 39516 KB Output is correct
4 Correct 14 ms 39712 KB Output is correct
5 Correct 11 ms 39516 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct
7 Correct 12 ms 39516 KB Output is correct
8 Correct 12 ms 39512 KB Output is correct
9 Correct 11 ms 39516 KB Output is correct
10 Correct 11 ms 39368 KB Output is correct
11 Correct 13 ms 39516 KB Output is correct
12 Correct 12 ms 39512 KB Output is correct
13 Correct 14 ms 39612 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 39512 KB Output is correct
2 Correct 13 ms 39516 KB Output is correct
3 Correct 14 ms 39516 KB Output is correct
4 Correct 14 ms 39712 KB Output is correct
5 Correct 11 ms 39516 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct
7 Correct 12 ms 39516 KB Output is correct
8 Correct 12 ms 39512 KB Output is correct
9 Correct 11 ms 39516 KB Output is correct
10 Correct 11 ms 39368 KB Output is correct
11 Correct 13 ms 39516 KB Output is correct
12 Correct 12 ms 39512 KB Output is correct
13 Correct 14 ms 39612 KB Output is correct
14 Correct 33 ms 41932 KB Output is correct
15 Correct 65 ms 46540 KB Output is correct
16 Correct 91 ms 51036 KB Output is correct
17 Correct 121 ms 53556 KB Output is correct
18 Correct 119 ms 53852 KB Output is correct
19 Correct 118 ms 53960 KB Output is correct
20 Correct 123 ms 53704 KB Output is correct
21 Correct 115 ms 54208 KB Output is correct
22 Correct 84 ms 50712 KB Output is correct
23 Correct 74 ms 49732 KB Output is correct
24 Correct 63 ms 48336 KB Output is correct
25 Correct 87 ms 52380 KB Output is correct
26 Correct 81 ms 50144 KB Output is correct
27 Correct 101 ms 51012 KB Output is correct
28 Correct 83 ms 50888 KB Output is correct
29 Correct 102 ms 52492 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 39512 KB Output is correct
2 Correct 13 ms 39516 KB Output is correct
3 Correct 14 ms 39516 KB Output is correct
4 Correct 14 ms 39712 KB Output is correct
5 Correct 11 ms 39516 KB Output is correct
6 Correct 12 ms 39516 KB Output is correct
7 Correct 12 ms 39516 KB Output is correct
8 Correct 12 ms 39512 KB Output is correct
9 Correct 11 ms 39516 KB Output is correct
10 Correct 11 ms 39368 KB Output is correct
11 Correct 13 ms 39516 KB Output is correct
12 Correct 12 ms 39512 KB Output is correct
13 Correct 14 ms 39612 KB Output is correct
14 Correct 33 ms 41932 KB Output is correct
15 Correct 65 ms 46540 KB Output is correct
16 Correct 91 ms 51036 KB Output is correct
17 Correct 121 ms 53556 KB Output is correct
18 Correct 119 ms 53852 KB Output is correct
19 Correct 118 ms 53960 KB Output is correct
20 Correct 123 ms 53704 KB Output is correct
21 Correct 115 ms 54208 KB Output is correct
22 Correct 84 ms 50712 KB Output is correct
23 Correct 74 ms 49732 KB Output is correct
24 Correct 63 ms 48336 KB Output is correct
25 Correct 87 ms 52380 KB Output is correct
26 Correct 81 ms 50144 KB Output is correct
27 Correct 101 ms 51012 KB Output is correct
28 Correct 83 ms 50888 KB Output is correct
29 Correct 102 ms 52492 KB Output is correct
30 Correct 259 ms 60268 KB Output is correct
31 Correct 391 ms 79460 KB Output is correct
32 Correct 585 ms 87752 KB Output is correct
33 Correct 1122 ms 117724 KB Output is correct
34 Correct 214 ms 60592 KB Output is correct
35 Correct 1091 ms 116456 KB Output is correct
36 Correct 1027 ms 117680 KB Output is correct
37 Correct 1058 ms 116924 KB Output is correct
38 Correct 1133 ms 118216 KB Output is correct
39 Correct 1048 ms 117472 KB Output is correct
40 Correct 977 ms 120220 KB Output is correct
41 Correct 1008 ms 117680 KB Output is correct
42 Correct 1088 ms 115260 KB Output is correct
43 Correct 560 ms 117216 KB Output is correct
44 Correct 535 ms 120272 KB Output is correct
45 Correct 520 ms 119060 KB Output is correct
46 Correct 561 ms 89704 KB Output is correct
47 Correct 430 ms 76736 KB Output is correct
48 Correct 667 ms 97068 KB Output is correct
49 Correct 639 ms 99192 KB Output is correct