Submission #362077

#	Time	Username	Problem	Language	Result	Execution time	Memory
362077		denkendoemeer	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	869 ms	55288 KiB

fortune_telling2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200005],b[200005],v[200005],v2[200005];
vector<int>aint[800005];
void init(int nod,int st,int dr)
{
    int i;
    for(i=st;i<=dr;i++)
        aint[nod].push_back(v[i]);
    sort(aint[nod].begin(),aint[nod].end());
    if (st!=dr){
        int mij=(st+dr)/2;
        init(nod*2,st,mij);
        init(nod*2+1,mij+1,dr);
    }
}
int ind(vector<int>&aux,int nr)
{
    return aux.size()-(lower_bound(aux.begin(),aux.end(),nr)-aux.begin());
}
int query(int nod,int st,int dr,int l,int r)
{
    if (st==dr){
        if (l<=aint[nod][0] && aint[nod][0]<r)
            return st;
        else
            return st-1;
    }
    else{
        int mij=(st+dr)/2;
        if (ind(aint[nod*2+1],l)-ind(aint[nod*2+1],r))
            return query(nod*2+1,mij+1,dr,l,r);
        else
            return query(nod*2,st,mij,l,r);
    }
}
int query2(int nod,int st,int dr,int l,int r,int nr)
{
    if (st==l && dr==r)
        return ind(aint[nod],nr);
    int mij=(st+dr)/2;
    if (r<=mij)
        return query2(nod*2,st,mij,l,r,nr);
    else
        if (l>mij)
            return query2(nod*2+1,mij+1,dr,l,r,nr);
        else
            return query2(nod*2,st,mij,l,mij,nr)+query2(nod*2+1,mij+1,dr,mij+1,r,nr);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,k,i;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if (a[i]>b[i]){
            swap(a[i],b[i]);
            v2[i]=1;
        }
    }
    for(i=1;i<=k;i++)
        scanf("%d",&v[i]);
    init(1,1,k);
    ll ans=0;
    for(i=0;i<n;i++){
        int aux=query(1,1,k,a[i],b[i]);
        if (aux)
            v2[i]=1;
        if (aux<k)
            v2[i]+=query2(1,1,k,aux+1,k,a[i]);
        if (v2[i]&1)
            ans+=b[i];
        else
            ans+=a[i];
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d%d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~

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