Submission #91298

#	Time	Username	Problem	Language	Result	Execution time	Memory
91298		Retro3014	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	4 ms	2880 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;
#define MAX_N 200000
#define INF 1000000000

struct S{
    int x, y;
    bool b=false;
    bool operator <(const S &a)const{
        return x<a.x;
    }
};

int N, K;
S arr[MAX_N+1];
int Q[MAX_N+1];
int two=1;
int seg[MAX_N*4+1], seg2[MAX_N*4+1];

void update(int x, int y){
    x+=two;
    seg[x]=y;
    x/=2;
    while(x){
        seg[x]=min(seg[x*2], seg[x*2+1]); x/=2;
    }
    return;
}

void update2(int x){
    x+=two;
    while(x){
        seg2[x]++; x/=2;
    }
    return;
}

int sum(int x, int y){
    int ret=0;
    x+=two; y+=two;
    while(x<=y){
        if(x==y){
            return ret+seg2[x];
        }
        if(x%2==1){
            ret+=seg2[x++];
        }
        if(y%2==0){
            ret+=seg2[y--];
        }
        x/=2; y/=2;
    }
    return ret;
}

struct S2{
    int x, y;
    bool operator <(const S2 &a)const{
        return x<a.x;
    }
};

int calc(int x, int y){
    x+=two; y+=two;
    int ret=INF;
    while(x<=y){
        if(x==y){
            return min(ret, seg[x]);
        }
        if(x%2==1){
            ret=min(ret, seg[x]);
            x++;
        }
        if(y%2==0){
            ret=min(ret, seg[y]);
            y--;
        }
        x/=2;   y/=2;
    }
    return ret;
}

deque<S2> dq;

long long ans=0;

int main(){
    scanf("%d%d", &N, &K);
    while(two<=K || two<=N)   two*=2;
    for(int i=1; i<two*2; i++){
        seg[i]=INF;
    }
    for(int i=0; i<N; i++){
        scanf("%d%d", &arr[i].x, &arr[i].y);
        if(arr[i].x>arr[i].y){
            arr[i].b=true;
            int tmp=arr[i].x; arr[i].x=arr[i].y; arr[i].y=tmp;
        }
    }
    sort(arr, arr+N);
    for(int i=0; i<K; i++){
        scanf("%d", &Q[i]);
        update(i, Q[i]);
        dq.push_back((S2){Q[i], i});
    }
    sort(dq.begin(), dq.end());
    for(int i=0; i<N; i++){
        S now = arr[i];
        while(!dq.empty() && dq.front().x < now.x){
            update(dq.front().y, INF);
            update2(dq.front().y);
            dq.pop_front();
        }
        if(calc(0, K-1) < now.y){
            now.b = true;
        }
        int s=0, e=K-1, mid;
        while(s<e){
            mid=(s+e)/2;
            if(calc(mid, K-1)<now.y){
                s=mid+1;
            }else{
                e=mid;
            }
        }
        mid=K-s-sum(s, K-1);
        now.b=((int)now.b+mid)%2;
        if(now.b){
            ans+=(long long)now.y;
        }else{
            ans+=(long long)now.x;
        }
    }
    printf("%lld", ans);
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &arr[i].x, &arr[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Q[i]);
         ~~~~~^~~~~~~~~~~~~

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