제출 #207831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207831		Segtree	Strange Device (APIO19_strange_device)	C++14	100 / 100	2449 ms	38080 KiB

strange_device

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
ll gcd(ll a,ll b){
	return (b?gcd(b,a%b):a);
}
int main(){
	ll n,A,B;
	cin>>n>>A>>B;
	ll M=A/gcd(A,B+1)*B; //cerr<<M<<endl;
	vector<P> v;
	rep(i,n){
		ll l,r;
		cin>>l>>r;
		ll L=l/M,R=r/M;
		if(L+2<=R){
			v.push_back(make_pair(0,+1));
			v.push_back(make_pair(M,-1));
		}
		else if(L+1==R){
			v.push_back(make_pair(0,+1));
			v.push_back(make_pair(r%M+1,-1));
			v.push_back(make_pair(l%M,+1));
			v.push_back(make_pair(M,-1));
		}
		else{
			v.push_back(make_pair(l%M,+1));
			v.push_back(make_pair(r%M+1,-1));
		}
	}
	sort(all(v));
	ll ans=0,rui=0,bef=0;
	for(auto e:v){
		ll t=e.first,di=e.second;
		//cout<<"#"<<t<<" "<<di<<endl;
		ans+=(rui>0)*(t-bef);
		rui+=di;
		bef=t;
	}
	cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30