이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 9999999999999999LL
using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
struct thing{
int A,B,C,D;
};
ll ans=MAX;
int N,M;
/*
set<pl> lmap;
set<pl> rmap;
*/
ll ltree[1200000];
ll rtree[1200000];
vector<pair<int,pi> > vect;
thing things[110000];
void init(ll *tree,int l,int r,int idx){
tree[idx]=MAX;
if(l==r) return ;
int m=(l+r)>>1;
init(tree,l,m,idx*2);
init(tree,m+1,r,idx*2+1);
}
ll range(ll *tree,int l,int r,int idx,int s,int e){
if(r<s||e<l) return MAX;
if(s<=l&&r<=e) return tree[idx];
int m=(l+r)>>1;
return min(range(tree,l,m,idx*2,s,e),range(tree,m+1,r,idx*2+1,s,e));
}
ll update(ll *tree,int l,int r,int idx,int pos,ll val){
if(r<pos||pos<l) return tree[idx];
if(l==r){
return tree[idx]=min(tree[idx],val);
}
int m=(l+r)>>1;
return tree[idx]=min(update(tree,l,m,idx*2,pos,val),update(tree,m+1,r,idx*2+1,pos,val));
}
int main(){
scanf("%d %d",&M,&N);
for(int i=0;i<M;i++){
scanf("%d %d %d %d",&things[i].A,&things[i].C,&things[i].B,&things[i].D);
vect.push_back(make_pair(things[i].A,pi(i,1)));
vect.push_back(make_pair(things[i].B,pi(i,2)));
vect.push_back(make_pair(things[i].C,pi(i,3)));
}
vect.push_back(make_pair(N,pi(0,0)));
vect.push_back(make_pair(1,pi(0,0)));
int x=1;
sort(vect.begin(),vect.end());
for(int i=0;i<vect.size();){
int j;
for(j=i;j<vect.size()&&vect[i].first==vect[j].first;j++){
if(vect[j].second.second==0){
}
else if(vect[j].second.second==1){
things[vect[j].second.first].A=x;
}
else if(vect[j].second.second==2){
things[vect[j].second.first].B=x;
}
else{
things[vect[j].second.first].C=x;
}
}
x++;
i=j;
}
x--;
init(ltree,1,x,1);
init(rtree,1,x,1);
update(ltree,1,x,1,1,0);
update(rtree,1,x,1,x,0);
for(int i=0;i<M;i++){
ans=min(ans,range(ltree,1,x,1,things[i].A,x)+range(rtree,1,x,1,1,things[i].C)+things[i].D);
ll val;
val=range(ltree,1,x,1,things[i].A,x)+things[i].D;
update(ltree,1,x,1,things[i].B,val);
val=range(rtree,1,x,1,1,things[i].C)+things[i].D;
update(rtree,1,x,1,things[i].B,val);
//printf("%d %d %d %d %d\n",things[i].A,things[i].B,things[i].C,things[i].D,x);
}
/*
rmap.insert(pl(x-1,0));
lmap.insert(pl(1,0));
set<pl>::iterator lit;
set<pl>::iterator rit;
set<pl>::iterator temp;
set<pl>::iterator ttemp;
for(int i=0;i<M;i++){
int l=things[i].A;
int r=things[i].C;
int m=things[i].B;
lit=lmap.lower_bound(pl(l,-1));
rit=rmap.upper_bound(pl(r,-1));
if(lit!=lmap.end()&&rit!=rmap.begin()){
--rit;
ans=min((*lit).second+(*rit).second+things[i].D,ans);
rit++;
}
if(lit!=lmap.end()){
ll tval=(*lit).second+things[i].D;
temp=lmap.lower_bound(pl(m,0));
if(temp==lmap.end()||(*temp).second>tval){
lmap.insert(pl(m,tval));
temp=lmap.lower_bound(pl(m,0));
temp--;
while(temp!=lmap.begin()&&temp->second>=tval){
ttemp=temp--;
temp++;
lmap.erase(temp);
temp=ttemp;
}
}
}
if(rit!=rmap.begin()){
--rit;
ll tval=(*rit).second+things[i].D;
temp=rmap.upper_bound(pl(m,0));
if(temp==rmap.begin()){
}
}
}
*/
if(ans==MAX) printf("-1\n");
else printf("%lld\n",ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
pinball.cpp: In function 'int main()':
pinball.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vect.size();){
~^~~~~~~~~~~~
pinball.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<vect.size()&&vect[i].first==vect[j].first;j++){
~^~~~~~~~~~~~
pinball.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&M,&N);
~~~~~^~~~~~~~~~~~~~~
pinball.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&things[i].A,&things[i].C,&things[i].B,&things[i].D);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |