Submission #315965

#	Time	Username	Problem	Language	Result	Execution time	Memory
315965		JovanK26	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	3036 ms	19200 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
int n,k,sz;
int a[200005];
int b[200005];
int t[200005];
int bit[200005];
int comp[600005];
pair<int,int> pos[200005];
vector<int> v[800005];
void insrt(int start,int val,int i,int j,int l,int r)
{
    if(i==l && j==r)
    {
        v[start].push_back(val);
        return;
    }
    int m=(l+r)/2;
    if(i<m)insrt(2*start+1,val,i,min(j,m),l,m);
    if(j>m)insrt(2*start+2,val,max(i,m),j,m,r);
}
void check(int start,int j,int tt,int l,int r)
{
    for(int i=0;i<v[start].size();i++)
    {
        if(v[start][i]<0)
        {
            v[start][i]=j;
        }
    }
    v[start].clear();
    if(r-l==1)return;
    int m=(l+r)/2;
    if(tt<m)check(2*start+1,j,tt,l,m);
    else
    {
       check(2*start+2,j,tt,m,r);
    }
}
void update(int x)
{
    while(x<=sz)
    {
        bit[x]++;
        x+=x&(-x);
    }
}
int sum(int x)
{
    int rez=0;
    while(x>0)
    {
        rez+=bit[x];
        x-=x&(-x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    int ind=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i] >> b[i];
        comp[ind++]=a[i];
        comp[ind++]=b[i];
    }
    for(int i=0;i<k;i++)
    {
        cin >> t[i];
        comp[ind++]=t[i];
    }
    sort(comp,comp+ind);
    sz=unique(comp,comp+ind)-comp;
    for(int 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]),0,sz);
    }
    for(int i=k-1;i>=0;i--)
    {
        t[i]=lower_bound(comp,comp+sz,t[i])-comp;
        check(0,i,t[i],0,sz);
    }
    sort(pos,pos+n);
    reverse(pos,pos+n);
    int cur=k-1;
    int br=0;
    long long rez=0;
    for(int i=0;i<n;i++)
    {
        while(cur>pos[i].first)
        {
           update(t[cur--]+1);
           br++;
        }
        int p=pos[i].second;
        int num=(br-sum(max(b[p],a[p])))%2;
        int beg=1;
        if(cur<0)beg=0;
        int fin;
        if((num+beg)%2)
        {
            fin=max(a[p],b[p]);
        }
        else
        {
            fin=min(a[p],b[p]);
        }
        rez+=comp[fin];
    }
    cout << rez;
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void check(int, int, int, int, int)':
fortune_telling2.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<v[start].size();i++)
      |                 ~^~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int sum(int)':
fortune_telling2.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^

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