제출 #315988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315988		JovanK26	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	191 ms	31096 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(i==l && j==r)
    {
        v[start].push_back(val);
        return;
    }
    long long m=(l+r)/2;
    if(i<m)insrt(2*start,val,i,min(j,m),l,m);
    if(j>m)insrt(2*start+1,val,max(i,m),j,m,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==1)return;
    long long m=(l+r)/2;
    if(tt<m)check(2*start,j,tt,l,m);
    else
    {
       check(2*start+1,j,tt,m,r);
    }
    return;
}
void update(long long x)
{
    while(x<=sz)
    {
        bit[x]++;
        x+=x & -x;
    }
}
long long sum(long long x)
{
    long long rez=0;
    while(x>0)
    {
        rez+=bit[x];
        x-=x & -x;
    }
    return rez;
}
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(1,i,min(a[i],b[i]),max(a[i],b[i]),0,sz);
    }
    for(long long i=k-1;i>=0;i--)
    {
        t[i]=lower_bound(comp,comp+sz,t[i])-comp;
        check(1,i,t[i],0,sz);
    }
    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(b[p]))%2;
        long long st=cur>=0 ? (a[p]<b[p] ? 1 : 0) : 0;
        rez+=comp[(st + num)%2 ? b[p] : a[p]];
    }
    cout << rez;
    return 0;
}

컴파일 시 표준 에러 (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:25: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]
   25 |     for(long long i=0;i<v[start].size();i++)
      |                       ~^~~~~~~~~~~~~~~~

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