Submission #619971

#	Time	Username	Problem	Language	Result	Execution time	Memory
619971		AbdelmagedNour	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	532 ms	31072 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
struct SegTreeMax{
    int tree[1<<21];
    int sz;
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        memset(tree,-1,2*sz*sizeof(tree[0]));
    }
    void update(int l,int r,int p,int idx,int val){
        if(l==r){
            tree[p]=val;
            return;
        }
        int md=(l+r)>>1;
        if(md>=idx)update(l,md,p*2+1,idx,val);
        else update(md+1,r,p*2+2,idx,val);
        tree[p]=max(tree[p*2+1],tree[p*2+2]);
    }
    void update(int idx,int val){
        update(0,sz-1,0,idx,val);
    }
    int query(int l,int r,int p,int l_q,int r_q){
        if(l>r_q||r<l_q)return -1;
        if(l>=l_q&&r<=r_q)return tree[p];
        int md=(l+r)>>1;
        int ch1=query(l,md,p*2+1,l_q,r_q);
        int ch2=query(md+1,r,p*2+2,l_q,r_q);
        return max(ch1,ch2);
    }
    int query(int l,int r){
        return query(0,sz-1,0,l,r);
    }
}treeMax;
struct SegTreeSum{
    int tree[1<<21];
    int sz;
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        memset(tree,0,2*sz*sizeof(tree[0]));
    }
    void update(int l,int r,int p,int idx,int val){
        if(l==r){
            tree[p]+=val;
            return;
        }
        int md=(l+r)>>1;
        if(md>=idx)update(l,md,p*2+1,idx,val);
        else update(md+1,r,p*2+2,idx,val);
        tree[p]=(tree[p*2+1]+tree[p*2+2]);
    }
    void update(int idx,int val){
        update(0,sz-1,0,idx,val);
    }
    int query(int l,int r,int p,int l_q,int r_q){
        if(l>r_q||r<l_q)return 0;
        if(l>=l_q&&r<=r_q)return tree[p];
        int md=(l+r)>>1;
        int ch1=query(l,md,p*2+1,l_q,r_q);
        int ch2=query(md+1,r,p*2+2,l_q,r_q);
        return (ch1+ch2);
    }
    int query(int l,int r){
        return query(0,sz-1,0,l,r);
    }
}treeSum;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n][2],b[n][2],q[k][2],c[n];
    vector<int>V;
    for(int i=0;i<n;i++)cin>>a[i][0]>>b[i][0],V.push_back(a[i][0]),V.push_back(b[i][0]);
    for(int i=0;i<k;i++)cin>>q[i][0],V.push_back(q[i][0]);
    int id=0;
    sort(V.begin(),V.end());
    V.resize(unique(V.begin(),V.end())-V.begin());
    id=V.size();
    for(int i=0;i<n;i++){
        a[i][1]=lower_bound(V.begin(),V.end(),a[i][0])-V.begin();
        b[i][1]=lower_bound(V.begin(),V.end(),b[i][0])-V.begin();
    }
    for(int i=0;i<k;i++)q[i][1]=lower_bound(V.begin(),V.end(),q[i][0])-V.begin();
    vector<vector<int>>v(k+1);
    treeMax.init(id);
    treeSum.init(id);
    for(int i=0;i<k;i++)treeMax.update(q[i][1],i);
    for(int i=0;i<n;i++){
        int l=a[i][1],r=b[i][1];
        if(l>r)swap(l,r);
        int mx=-1;
        if(l<r)mx=treeMax.query(l,r-1);
        c[i]=mx;
        v[mx+1].push_back(i);
    }
    long long sum=0;
    for(int i=k;i>=0;i--){
        if(i<k)treeSum.update(q[i][1],1);
        for(auto&x:v[i]){
            int cnt=treeSum.query(max(a[x][1],b[x][1]),id);
            if(c[x]==-1){
                if(cnt&1)sum+=b[x][0];
                else sum+=a[x][0];
            }else{
                if(cnt&1)sum+=min(a[x][0],b[x][0]);
                else sum+=max(a[x][0],b[x][0]);
            }
        }
    }
    cout<<sum;
    return 0;
}

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