oj.uz

답안 #315974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
315974 2020-10-24T15:50:16 Z JovanK26 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 15 ms 19328 KB 
#include <bits/stdc++.h>

using namespace std;
int n,k,sz;
int a[200050];
int b[200050];
int t[200050];
int bit[200050];
int comp[600150];
pair<int,int> pos[200050];
vector<int> v[800250];
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,val,i,min(j,m),l,m);
    if(j>m)insrt(2*start+1,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(pos[v[start][i]].first<0)
        {
            pos[v[start][i]].first=j;
        }
    }
    v[start].clear();
    if(r-l==1)return;
    int 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(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);
    }
    return rez;
}
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(1,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(1,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

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++)
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Incorrect 15 ms 19328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Incorrect 15 ms 19328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Incorrect 15 ms 19328 KB Output isn't correct
3 Halted 0 ms 0 KB -