이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |