제출 #77719

#제출 시각아이디문제언어결과실행 시간메모리
77719nxteru운세 보기 2 (JOI14_fortune_telling2)C++14
100 / 100
1451 ms153204 KiB
#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);
         ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...