제출 #1274753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274753		k12_khoi	Strange Device (APIO19_strange_device)	C++17	100 / 100	510 ms	35936 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second

const int N=1e6+5;
const ll oo=1e18+1;

int request; ll A,B,l,r,x,y,z,temp;

namespace subfull
{
    int h; ll res;
    int f[2*N]; ll l[N],r[N];
    vector <ll> ve;

    void solve()
    {
        y=B+1;
        temp=__gcd(A,y);
        y=B;

        if (oo/A<y/temp) z=oo;
        else z=A/temp*y;

        for (int i=1;i<=request;i++)
        {
            cin >> l[i] >> r[i];
            if (r[i]-l[i]+1>=z)
            {
                cout << z;
                return;
            }

            r[i]++;
            if (l[i]/z==r[i]/z)
            {
                ve.push_back(l[i]%z);
                ve.push_back(r[i]%z);
            }
            else
            {
                ve.push_back(l[i]%z);
                ve.push_back(z);
                ve.push_back(0);
                ve.push_back(r[i]%z);
            }
        }
        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        h=ve.size();
        f[0]=0;


        for (int i=1;i<=request;i++)
        {
            if (l[i]/z==r[i]/z)
            {
                x=lower_bound(ve.begin(),ve.end(),l[i]%z)-ve.begin()+1;
                y=lower_bound(ve.begin(),ve.end(),r[i]%z)-ve.begin()+1;
                f[x]++;
                f[y]--;
            }
            else
            {
                x=lower_bound(ve.begin(),ve.end(),l[i]%z)-ve.begin()+1;
                y=lower_bound(ve.begin(),ve.end(),z)-ve.begin()+1;;
                f[x]++;
                f[y]--;

                x=lower_bound(ve.begin(),ve.end(),0)-ve.begin()+1;
                y=lower_bound(ve.begin(),ve.end(),r[i]%z)-ve.begin()+1;
                f[x]++;
                f[y]--;
            }
        }

        res=0;
        for (int i=1;i<h;i++)
        {
            f[i]+=f[i-1];
            if (f[i]) res+=ve[i]-ve[i-1];
        }

        cout << res;
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> request >> A >> B;

    subfull::solve();
}

• 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