Submission #316035

#	Time	Username	Problem	Language	Result	Execution time	Memory
316035		JovanK26	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	178 ms	31284 KiB

fortune_telling2

 #include <bits/stdc++.h>

using namespace std;
long long n,k,sz;
long long a[200050];
long long b[200050];
long long t[200050];
long long bit[200050];
long long comp[600150];
pair<long long,long long> pos[200050];
vector<long long> v[800250];
void insrt(long long start,long long val,long long i,long long j,long long l,long long r)
{
    if(r<i || l>j)return;
    if(l>=i && r<=j)
    {
        v[start].push_back(val);
        return;
    }
    long long m=(l+r)/2;
    insrt(2*start+1,val,i,j,l,m);
    insrt(2*start+2,val,i,j,m+1,r);
}
void check(long long start,long long j,long long tt,long long l,long long r)
{
    for(long long i=0;i<v[start].size();i++)
    {
        if(pos[v[start][i]].first<0)
        {
            pos[v[start][i]].first=j;
        }
    }
    v[start].clear();
    if(r-l==0)return;
    long long m=(l+r)/2;
    if(tt<=m)check(2*start+1,j,tt,l,m);
    else
    {
       check(2*start+2,j,tt,m+1,r);
    }
    return;
}
void update(long long x)
{
    while(x<=sz)
    {
        bit[x]++;
        x+=(x & -x);
    }
}
long long sum(long long x)
{
    long long ss=0;
    while(x>0)
    {
        ss+=bit[x];
        x-=(x & -x);
    }
    return ss;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //ifstream fin("03-01.txt");
    //ofstream fout("01out.txt");
    cin >> n >> k;
    long long ind=0;
    for(long long i=0;i<n;i++)
    {
        cin >> a[i] >> b[i];
        comp[ind++]=a[i];
        comp[ind++]=b[i];
    }
    for(long long i=0;i<k;i++)
    {
        cin >> t[i];
        comp[ind++]=t[i];
    }
    sort(comp,comp+ind);
    sz=unique(comp,comp+ind)-comp;
    for(long long i=0;i<n;i++)
    {
        a[i]=lower_bound(comp,comp+sz,a[i])-comp;
        b[i]=lower_bound(comp,comp+sz,b[i])-comp;
        pos[i]=make_pair(-1,i);
        insrt(0,i,min(a[i],b[i]),max(a[i],b[i])-1,0,sz-1);
    }
    for(long long i=k-1;i>=0;i--)
    {
        t[i]=lower_bound(comp,comp+sz,t[i])-comp;
        check(0,i,t[i],0,sz-1);
    }
    sort(pos,pos+n);
    reverse(pos,pos+n);
    long long cur=k-1;
    long long br=0;
    long long rez=0;
    for(long long i=0;i<n;i++)
    {
        while(cur>pos[i].first)
        {
           update(t[cur--]+1);
           br++;
        }
        long long p=pos[i].second;
        long long num=(br-sum(max(a[p],b[p])))%2;
        long long st=cur>=0 ? (a[p]<b[p] ? 1 : 0) : 0;
        long long fin;
        if((num+st)%2==0)
        {
            fin=a[p];
        }
        else
        {
            fin=b[p];
        }
        rez+=comp[fin];
    }
    cout << rez;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void check(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:26:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(long long i=0;i<v[start].size();i++)
      |                       ~^~~~~~~~~~~~~~~~

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