제출 #474652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474652		nicolaalexandra	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	2 ms	332 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],poz[DIM],w[DIM*3],swapped[DIM],sol[DIM];
vector <pair<int,int> > events;
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 a.y < 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<=n;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;
        if (v[i].x > v[i].y){
            swap (v[i].x,v[i].y);
            swapped[i] = 1;
        }
        v[i].poz = i;
        w[++el] = v[i].x;
        w[++el] = v[i].y;
    }

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

    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;

    /*
    for (i=1;i<=n;i++){
        v[i].x = cautare_binara (w,el,v[i].x);
        v[i].y = cautare_binara (w,el,v[i].y);
    }

    for (i=1;i<=k;i++)
        t[i].first = cautare_binara (w,el,t[i].first);
*/

    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 >= v[i].x){
                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 < 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);

    }

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

    sort (v+1,v+n+1,cmp2);

    for (i=1;i<=n;i++)
        events.push_back(make_pair(poz[v[i].poz],i));

    sort (events.begin(),events.end(),cmp3);
    int idx = 0;

    for (i=k;i>=0;i--){

        int val = t[i].first;
        int st = 1, dr = n, sol_poz = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (v[mid].y <= val){
                st = mid+1;
                sol_poz = mid;
            } else dr = mid-1;
        }

        if (sol_poz){
            update_aib (1,1);
            update_aib (sol_poz+1,-1);
        }


        while (idx < events.size() && events[idx].first == t[i].second){

            sol[v[events[idx].second].poz] = query_aib (events[idx].second);

            idx++;
        }

    }


    sort (v+1,v+n+1,cmp4);

    long long ans = 0;
    for (i=1;i<=n;i++){
        if (swapped[i])
            sol[i]++;
        if (sol[i] % 2)
            ans += v[i].y;
        else ans += v[i].x;
    }

    cout<<ans;



    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:179:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         while (idx < events.size() && events[idx].first == t[i].second){
      |                ~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int cautare_binara(int*, int, int)':
fortune_telling2.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^

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