제출 #77719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
77719		nxteru	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	1451 ms	153204 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct e{
    ll c,a,s;
    bool operator <(const e&q)const{
        if(c!=q.c)return c<q.c;
        return s<q.s;
    }
    bool operator >(const e&q)const{
        if(c!=q.c)return c>q.c;
        return s>q.s;
    }
};
ll n,q,k,seg[1<<21],v[200005],u[200005],t[200005],BIT[200005],ans;
vector<ll>cm;
vector<e>w;
map<ll,ll>pr;
void ini(void){
    for(int i=0;i<1<<21;i++)seg[i]=-1;
}
void up(int a,ll x){
    a+=(1<<20)-1;
    seg[a]=max(seg[a],x);
    while(a>0){
        a=(a-1)/2;
        seg[a]=max(seg[a*2+1],seg[a*2+2]);
    }
}
ll que(int a,int b,int l,int r,int o){
    if(r<a||b<l)return -1;
    if(a<=l&&r<=b)return seg[o];
    return max(que(a,b,l,(l+r-1)/2,o*2+1),que(a,b,(l+r+1)/2,r,o*2+2));
}
void add(int a,ll x){
    a++;
    while(a<=q){
        BIT[a]+=x;
        a+=(a&-a);
    }
}
ll sum(int a){
    a++;
    ll res=0;
    while(a>0){
        res+=BIT[a];
        a-=(a&-a);
    }
    return res;
}
int main(void){
    scanf("%lld%lld",&n,&q);
    ini();
    for(int i=0;i<n;i++){
        scanf("%lld%lld",v+i,u+i);
        cm.PB(v[i]);
        cm.PB(u[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%lld",t+i);
        cm.PB(t[i]);
    }
    sort(cm.begin(),cm.end());
    cm.erase(unique(cm.begin(),cm.end()),cm.end());
    k=cm.size();
    for(int i=0;i<k;i++)pr[cm[i]]=i;
    for(int i=0;i<n;i++){
        v[i]=pr[v[i]];
        u[i]=pr[u[i]];
        w.PB(e{max(v[i],u[i]),i,0});
    }
    for(int i=0;i<q;i++){
        t[i]=pr[t[i]];
        up(t[i],i);
        w.PB(e{t[i],i,1});
    }
    sort(w.begin(),w.end(),greater<e>());
    for(int i=0;i<w.size();i++){
        if(w[i].s==1){
            add(w[i].a,1);
        }else{
            int p=w[i].a;
            int a=v[p],b=u[p],x=min(a,b),y=max(a,b);
            if(a==b){
                ans+=cm[a];
                continue;
            }
            int c=que(x,y-1,0,(1<<20)-1,0);
            if(c==-1){
                int s=sum(q-1);
                if(s%2==0)ans+=cm[a];
                else ans+=cm[b];
            }else{
                int s=sum(q-1)-sum(c);
                if(s%2==0)ans+=cm[y];
                else ans+=cm[x];
            }
        }
    }
    printf("%lld\n",ans);
}

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w.size();i++){
                 ~^~~~~~~~~
fortune_telling2.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",v+i,u+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",t+i);
         ~~~~~^~~~~~~~~~~~

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