제출 #659560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659560		raysh07	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	28 ms	57268 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
const int maxn = 2e5 + 5;
int a[maxn][2];
set <int> st[4*maxn];
int quer[maxn];
vector <int> v[4*maxn];

void Build(int l, int r, int pos)
{
    if (l==r)
    {
        st[pos].insert(quer[l]);
        v[pos].push_back(quer[l]);
        return;
    }
    int mid = (l+r)/2;
    Build (l, mid, pos*2);
    Build (mid + 1, r, pos*2 + 1);
    
    set_union(begin(st[pos*2]), end(st[pos* 2]), 
        begin(st[pos*2 + 1]), end(st[pos* 2 + 1]), 
        inserter(st[pos], st[pos].begin()));
        
    for (auto x: st[pos])
    {
        v[pos].push_back(x);
    }
}

bool Respond(int pos, int qa, int qb)
{
    if (qa>qb)
    {
        swap(qa, qb);
    }
    
    int l = 0;
    int r = v[pos].size() - 1;
    
    while (r-l>1)
    {
        int mid = (l+r)/2;
        if (v[pos][mid]>=qa && v[pos][mid]<qb)
        return true;
        if (v[pos][mid]<qa)
        l = mid;
        else r = mid;
    }
    if (v[pos][l]>=qa && v[pos][l]<qb)
    return true;
    if (v[pos][r]>=qa && v[pos][r]<qb)
    return true;
    return false;
}

int FindSelectiveLast(int l, int r, int pos, int qa, int qb)
{
    if (l==r)
    return l;
    int mid = (l+r)/2;
    if (Respond(pos*2 + 1, qa, qb))
    return FindSelectiveLast(mid + 1, r, pos*2 + 1, qa, qb);
    else return FindSelectiveLast(l, mid, pos*2, qa, qb);
}

int Count(int pos, int x)
{
    //cout<<"\nCounting "<<pos<<" "<<x<<"\n";
    int tot = v[pos].size();
   // for (auto y : v[pos])
  // // cout<<y<< ' ';
   // cout<<"\n";
    int l = 0;
    int r = tot-1;
    while (r-l>1)
    {
        
        int mid = (l+r)/2;//cout<<mid<<" "<<v[pos][mid]<<" ";
        
        if (v[pos][mid]>=x){
           // cout<<" r updated ";
        r = mid;
        }
        else {
            //cout<<" l updated ";
            l = mid;
        }
        //cout<<"\n";
    }
   // cout<<l <<" "<<r<<"\n";
    if (v[pos][l]>=x)
    return tot - l;
    else return tot - r;
}

int Query(int l, int r, int pos, int ql, int x)
{
   // cout<<"positioning "<<l<<" "<<r<<" "<<x<<" ";
    int mid = (l+r)/2;
    if (ql>r){
    //cout<<"NOOB RANGE\n";
    return 0;
    }
    
    if (l>=ql)
    {
        //cout<<Count(pos, x)<<"\n";
        return Count(pos, x);
    }
    else 
    {
        //cout<<"Went to child\n";
        return Query(l, mid, pos*2, ql, x) + Query(mid + 1, r, pos*2 + 1, ql, x);
    }
}

void Solve() 
{
    cin>>n>>q;
    
    for (int i=1; i<=n; i++)
    cin>>a[i][0]>>a[i][1];
    
    for (int i=1; i<=q; i++)
    {
        int x;
        cin>>x;
        quer[i] = x;
    }
    
    Build(1, q, 1);
    
    int sum = 0;
    
    for (int i=1; i<=n; i++)
    {
        int sel = 0;
        if (Respond(1, a[i][0], a[i][1]))
        {
            sel = FindSelectiveLast(1, q, 1, a[i][0], a[i][1]);
        }
        sel++;
        
        //cout<<sel<< " ";
       // cout<<"Querying\n";
        int vals = Query(1, q, 1, sel, max(a[i][0], a[i][1]));
        
       // cout<<"\n"<<sel<<" "<<vals<<" ";
        
        int initial = 0;
        if (sel!=1 && a[i][1]>a[i][0])
        {
            initial = 1;
        }
      
        initial = (initial + vals)%2;
     
        sum += a[i][initial];
       // cout<<a[i][initial]<<"\n";
    }
    cout<<sum;
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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