제출 #972447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972447		simona1230	이상한 기계 (APIO19_strange_device)	C++17	65 / 100	346 ms	36392 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;
long long n,a,b;
map<pair<long long,long long>,long long> mp;
pair<long long,long long> p[2000001];
void solve()
{
    int cnt=n;
    long long h=1e18;
    a/=__gcd(a,b+1);
    if(1e18/a>b)h=b*a;
    //cout<<h<<endl;
    for(long long i=1;i<=n;i++)
    {
        long long l,r;
        cin>>l>>r;
        p[i]={l%(h),r%(h)};
        if(p[i].first>p[i].second)
        {
            cnt++;
            p[cnt].first=0;
            p[cnt].second=p[i].second;

            p[i].second=h-1;
        }
    }
    long long ans=0;
    sort(p+1,p+cnt+1);

    long long r=-1;
    for(long long i=1;i<=cnt;i++)
    {
        if(p[i].second>r)
        {
            if(p[i].first>r)
                ans+=p[i].second-p[i].first+1;
            else ans+=p[i].second-r;
        }

        r=max(r,p[i].second);
    }

    cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>a>>b;
	solve();
	return 0;
}

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