Submission #619301

#	Time	Username	Problem	Language	Result	Execution time	Memory
619301		AbdelmagedNour	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1230 ms	62160 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[2][n],b[2][n],q[2][k],c[n];
    map<int,int>mp;
    for(int i=0;i<n;i++)cin>>a[0][i]>>b[0][i],mp[a[0][i]]=1,mp[b[0][i]]=1;
    for(int i=0;i<k;i++)cin>>q[0][i],mp[q[0][i]]=1;
    int id=500;
    for(auto&x:mp)x.second=id++;
    for(int i=0;i<n;i++){
        a[1][i]=mp[a[0][i]];
        b[1][i]=mp[b[0][i]];
    }
    for(int i=0;i<k;i++)q[1][i]=mp[q[0][i]];
    vector<vector<int>>v(k+1);
    treeMax.init(id);
    treeSum.init(id);
    for(int i=0;i<k;i++)treeMax.update(q[1][i],i);
    for(int i=0;i<n;i++){
        int l=a[1][i],r=b[1][i];
        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[1][i],1);
        for(auto&x:v[i]){
            int cnt=treeSum.query(max(a[1][x],b[1][x]),id);
            if(c[x]==-1){
                if(cnt&1)sum+=b[0][x];
                else sum+=a[0][x];
            }else{
                if(cnt&1)sum+=min(a[0][x],b[0][x]);
                else sum+=max(a[0][x],b[0][x]);
            }
        }
    }
    cout<<sum;
    return 0;
}

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