제출 #1172270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172270		AlgorithmWarrior	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	202 ms	5116 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const LOG=20;
int n,q;

struct valpoz{
    int val,poz;
    bool operator<(valpoz ot){
        return val<ot.val;
    }
}qry[MAX];

struct card{
    int a,b;
    bool operator<(card ot){
        return max(a,b)<max(ot.a,ot.b);
    }
}cards[MAX];

int ub(int x){
    return x&(-x);
}

struct AIB{
    int maxim[MAX],cnt[MAX];
    int n;
    void init(int n){
        this->n=n;
        int i;
        for(i=1;i<=n;++i){
            maxim[i]=0;
            cnt[i]=ub(i);
        }
    }
    int bin_search(int val){
        int poz=0;
        int i;
        for(i=LOG-1;i>=0;--i)
            if(poz+(1<<i)<=n && maxim[poz+(1<<i)]<val)
                poz+=(1<<i);
        return poz;
    }
    int sum(int poz){
        int s=0;
        while(poz){
            s+=cnt[poz];
            poz-=ub(poz);
        }
        return s;
    }
    void upd(valpoz nou){
        auto [val,poz]=nou;
        while(poz<=n){
            --cnt[poz];
            maxim[poz]=val;
            poz+=ub(poz);
        }
    }
}aib;

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i)
        cin>>cards[i].a>>cards[i].b;
    for(i=1;i<=q;++i){
        cin>>qry[i].val;
        qry[i].poz=q-i+1;
    }
    sort(cards+1,cards+n+1);
    sort(qry+1,qry+q+1);
}

long long solve(){
    long long rez=0;
    int i;
    int id=1;
    aib.init(q);
    for(i=1;i<=n;++i){
        auto [a,b]=cards[i];
        int mxm=max(a,b);
        int mnm=min(a,b);
        while(id<=q && qry[id].val<mxm){
            aib.upd(qry[id]);
            ++id;
        }
        int poz=aib.bin_search(mnm);
        int cnt=aib.sum(poz);
        if(poz==q){
            if(cnt%2==0)
                rez+=a;
            else
                rez+=b;
        }
        else{
            if(cnt%2==0)
                rez+=mxm;
            else
                rez+=mnm;
        }
    }
    return rez;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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