Submission #466168

#	Time	Username	Problem	Language	Result	Execution time	Memory
466168		Tenis0206	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	471 ms	31884 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
int n,k,a[200005],b[200005],t[200005];
vector<int> v;
int rez[200005],cnt[200005];
int auxa[200005],auxb[200005];
vector<pair<int,int>> Q[200005];
class arbore_de_intervale
{
    int ai[2500005];
public:
    void update(int poz, int val, int nod, int a, int b)
    {
        if(a==b)
        {
            ai[nod] = max(ai[nod],val);
            return;
        }
        int mij = (a+b)>>1;
        if(poz<=mij)
        {
            update(poz,val,nod*2,a,mij);
        }
        else
        {
            update(poz,val,nod*2+1,mij+1,b);
        }
        ai[nod] = max(ai[nod*2],ai[nod*2+1]);
    }
    int query(int qa, int qb, int nod, int a, int b)
    {
        if(qa<=a && qb>=b)
        {
            return ai[nod];
        }
        int mij = (a+b)>>1;
        int rez1 = 0, rez2 = 0;
        if(qa<=mij)
        {
            rez1 = query(qa,qb,nod*2,a,mij);
        }
        if(qb>mij)
        {
            rez2 = query(qa,qb,nod*2+1,mij+1,b);
        }
        return max(rez1,rez2);
    }
} ai;
class arbore_indexat_binar
{
    int aib[600005];
private:
    int ub(int x)
    {
        return (x&(-x));
    }
public:
    void update(int poz, int val)
    {
        for(int i=poz; i<=v.size(); i+=ub(i))
        {
            aib[i]+=val;
        }
    }
    int query(int qa, int qb)
    {
        int rez = 0;
        for(int i=qb; i>=1; i-=ub(i))
        {
            rez+=aib[i];
        }
        for(int i=qa-1; i>=1; i-=ub(i))
        {
            rez-=aib[i];
        }
        return rez;
    }
} aib;
int get_poz(int val)
{
    int st = 1;
    int dr = v.size();
    int poz = 0;
    while(st<=dr)
    {
        int mij = (st+dr)>>1;
        if(v[mij-1]>=val)
        {
            poz = mij;
            dr = mij-1;
        }
        else
        {
            st = mij+1;
        }
    }
    return poz;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i]>>b[i];
        auxa[i] = a[i];
        auxb[i] = b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for(int i=1; i<=k; i++)
    {
        cin>>t[i];
        v.push_back(t[i]);
    }
    sort(v.begin(),v.end());
    for(int i=1; i<=n; i++)
    {
        a[i] = get_poz(a[i]);
        b[i] = get_poz(b[i]);
    }
    for(int i=1; i<=k; i++)
    {
        t[i] = get_poz(t[i]);
        ai.update(t[i],i,1,1,v.size());
    }
    for(int i=1; i<=n; i++)
    {
        if(a[i]==b[i])
        {
            continue;
        }
        int poz = ai.query(min(a[i],b[i]),max(a[i],b[i])-1,1,1,v.size());
        if(poz)
        {
            rez[i] = max(a[i],b[i]);
        }
        else
        {
            rez[i] = a[i];
        }
        Q[poz+1].push_back({max(a[i],b[i]),i});
    }
    for(int i=k; i>=1; i--)
    {
        aib.update(t[i],+1);
        for(auto it : Q[i])
        {
            cnt[it.second] = aib.query(it.first,v.size());
        }
    }
    long long sum = 0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]==b[i])
        {
            sum+=auxa[i];
            continue;
        }
        if(cnt[i]%2==1)
        {
            if(rez[i]==a[i])
            {
                rez[i] = b[i];
            }
            else
            {
                rez[i] = a[i];
            }
        }
        if(rez[i]==a[i])
        {
            sum+=auxa[i];
        }
        else
        {
            sum+=auxb[i];
        }
    }
    cout<<sum<<'\n';
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void arbore_indexat_binar::update(int, int)':
fortune_telling2.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i=poz; i<=v.size(); i+=ub(i))
      |                        ~^~~~~~~~~~

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