Submission #475037

#	Time	Username	Problem	Language	Result	Execution time	Memory
475037		nicolaalexandra	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	630 ms	24220 KiB

fortune_telling2

#include <bits/stdc++.h>
#define DIM 200010
using namespace std;

struct card{
    int x,y,poz;
} v[DIM];

int aint[DIM*4],aib[DIM*4],poz[DIM],sol[DIM],w[DIM*4];
vector <int> events[DIM];
pair <int,int> t[DIM];
int n,i,j,k,el;

int cautare_binara (int v[], int n, int val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] == val)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
}

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = t[st].second;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

int query (int nod, int st, int dr, int x, int y){

    if (x <= st && dr <= y)
        return aint[nod];

    int mid = (st+dr)>>1, sol_st = 0, sol_dr = 0;
    if (x <= mid)
        sol_st = query (nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);

    return max (sol_st,sol_dr);
}

inline int cmp (pair <int,int> a, pair <int,int> b){
    return a.second < b.second;
}
inline int cmp2 (card a, card b){
    return max(a.x,a.y) < max(b.x,b.y);
}

inline int cmp3 (pair <int,int> a, pair <int,int> b){
    return a.first > b.first;
}
inline int cmp4 (card a, card b){
    return a.poz < b.poz;
}


void update_aib (int p, int val){
    for (;p<=el;p+=(p&-p))
        aib[p] += val;
}

int query_aib (int p){
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].poz = i;

        w[++el] = v[i].x;
        w[++el] = v[i].y;
    }

    for (i=1;i<=k;i++){
        cin>>t[i].first;
        t[i].second = i;
        w[++el] = t[i].first;
    }

    sort (w+1,w+el+1);

    int el2 = 1;
    for (i=2;i<=el;i++)
        if (w[i] != w[i-1])
            w[++el2] = w[i];

    el = el2;



    sort (t+1,t+k+1);

    build (1,1,k);

    for (i=1;i<=n;i++){

        int st = 1, dr = k, sol_x = 0, sol_y = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (t[mid].first >= min(v[i].x,v[i].y) ){
                sol_x = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        st = 1, dr = k;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (t[mid].first < max(v[i].x,v[i].y)){
                sol_y = mid;
                st = mid+1;
            } else dr = mid-1;
        }

        if (sol_x && sol_y){
            poz[i] = query (1,1,k,sol_x,sol_y);
            events[poz[i]].push_back(i);
        }
        //cout<<poz[i]<<"\n";
    }


    sort (t+1,t+k+1,cmp);

    for (i=k;i>=0;i--){
        for (auto it : events[i]){
            int val_y = cautare_binara(w,el,max(v[it].x,v[it].y));
            sol[it] = query_aib(el) - query_aib(val_y - 1);
        }

        if (i){
            int val_t = cautare_binara(w,el,t[i].first);
            update_aib (val_t,1);
        }
    }



    long long ans = 0;
    for (i=1;i<=n;i++){

        if (!poz[i]){
            if (sol[i] % 2)
                ans += v[i].y;
            else ans += v[i].x;
        } else {

            if (sol[i] % 2 == 0)
                ans += max(v[i].x,v[i].y);
            else ans += min(v[i].x,v[i].y);
        }
    }

    cout<<ans;



    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int cautare_binara(int*, int, int)':
fortune_telling2.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

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