글 읽기 - 반례를 구합니다.

p_ce1052 3년 전 0

노선도를 일직선으로 피고 노선의 구간 [a, b]에 대해 b가 a보다 작다면 b에 n을 더해서 관리한다.

1. 어떤 노선이 한 바퀴를 넘어가지 않는다면 즉 [a,b]에서 b<=n 이라면 두 가지 경우 중 하나로 어떤 노선에 포함된다.

0부터 a-1까지의 점들 중 하나가 b이상까지 뻗는 점이 있거나 똑같은 a점에서 b를 넘어서 뻗을 수 있어야 한다.

또는 한 바퀴 돌아서 나를 포함하려면 시작 위치에 관계없이 b+n 이상까지 뻗는 점이 있어야 한다.

2. 어떤 노선이 한 바퀴를 넘어 간다면 즉 [a,b]에서 b>n 이라면

0부터 a-1까지의 점들 중 하나가 b이상으로 뻗거나 a점에서 b를 넘어가는 점이 있어야 한다. 그 외 출발점이 a보다 크면서 나를 포함하는 것은 한 바퀴 이상 도는 노선은 없다는 조건 때문에 불가능.

위의 풀이를 위해 가능한 출발점을 좌표압축하고 세그트리를 사용했습니다 그리고 이미 본 노선이 다른 노선을 이후에 포함할 수 없도록 노선의 길이가 짧은 것부터 큰 노선 순으로 확인하였습니다.

출력초과가 납니다. 어디가 잘못됬나요? ㅠㅠ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
int seg[2000005];
int update(int i,int val,int node,int nleft,int nright){
	if(i<nleft || i>nright) return seg[node];
	if(i==nleft && nleft == nright) return seg[node] = max(seg[node],val);
	int mid = (nleft+nright)/2;
	return seg[node] = max(update(i,val,node*2,nleft,mid),update(i,val,node*2+1,mid+1,nright));
}
int query(int l,int r,int node,int nleft,int nright){
	if(l>r) return 0;
	if(r<nleft || l>nright) return 0;
	if(l<=nleft && nright<=r) return seg[node];
	int mid = (nleft+nright)/2;
	return max(query(l,r,node*2,nleft,mid),query(l,r,node*2+1,mid+1,nright));
}
int main(){
	ll n,m;
	cin>>n>>m;
	vector<pi>arr;
	priority_queue<pi,vector<pi>,greater<pi> >pq;
	for(int i=0; i<m; i++){
		ll a,b;
		cin>>a>>b;
		if(a>b) b+=n;
		arr.push_back(pi(a,b));		
		pq.push(pi((b-a),i));
	}
	vector<int>y;
	for(int i=0; i<m; i++) y.push_back(arr[i].first); //시작점을 좌표압축 
	y.erase(unique(y.begin(),y.end()),y.end());
	for(int i=0; i<m; i++){
		auto it = lower_bound(y.begin(),y.end(),arr[i].first);
		update((int)(it-y.begin()),arr[i].second,1,0,y.size()-1);
	}
	//시작점의 최댓값을 세그트리에 갱신하였음
    
	vector<ll>ans;
	
	while(pq.size()){
		int idx = pq.top().second;
		pq.pop();
		ll l = arr[idx].first;
		ll r = arr[idx].second;
		if(r>=n){ //한 바퀴를 넘는다면 
			auto it = lower_bound(y.begin(),y.end(),l);
			int mx = query(0,(int)(it-y.begin())-1,1,0,y.size()-1);
			if(mx>=r) continue;
			mx = query(l,l,1,0,y.size()-1);
			if(mx>r) continue;
			ans.push_back(idx);
		}
		else{
			auto it = lower_bound(y.begin(),y.end(),l);
			int mx = query(0,(int)(it-y.begin())-1,1,0,y.size()-1); //이전 점들이 날 포함하거나
			if(mx>=r) continue;
			auto tmp = (int)(it-y.begin());
			mx = query(tmp,tmp,1,0,y.size()-1); //같은 점에서 더 멀리 나가는 점이 있거나
			if(mx>r) continue;
			r+=n;
			mx = query(0,y.size()-1,1,0,y.size()-1); //한 바퀴 돌아서 날 포함하거나 
			if(mx>=r) continue;
			ans.push_back(idx);
		}
	}
	sort(ans.begin(),ans.end());
	for(int i=0; i<ans.size(); i++) cout<<ans[i]+1<<" ";
}

akwk777 3년 전 2

10

2

9 2

0 2

정답: 1

주어진 코드로 나온 답:1 2

댓글을 작성하려면 로그인해야 합니다.