Submission #238816

#	Time	Username	Problem	Language	Result	Execution time	Memory
238816		i_am_noob	Strange Device (APIO19_strange_device)	C++17	100 / 100	707 ms	33672 KiB

strange_device

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define eps 1e-9
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)

using namespace std;

const int maxn=1000005;
int n;
ll x,y,inf=1e18,mod=-1,minl=4e18,maxr=-1,ans=0;

struct segment{ll l,r;}seg[maxn],seg1;
bool comp(segment i, segment j){return i.l<j.l;}
vector<segment> vec;

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> x >> y;
    if(x/__gcd(y+1,x)<=inf/y) mod=x/__gcd(y+1,x)*y;
    rep(n) cin >> seg[i].l >> seg[i].r;
    rep(n){
        if(mod>=0){
            if(seg[i].r/mod==seg[i].l/mod){
                seg[i].l%=mod;
                seg[i].r%=mod;
                vec.pb(seg[i]);
            }
            else{
                seg[i].l%=mod;
                seg[i].r%=mod;
                if(seg[i].r>=seg[i].l){
                    print1(mod);
                    return 0;
                }
                seg1.l=seg[i].l,seg1.r=mod-1;
                vec.pb(seg1);
                seg1.l=0,seg1.r=seg[i].r;
                vec.pb(seg1);
            }
        }
        else{
            vec.pb(seg[i]);
        }
    }
    sort(all(vec),comp);
    for(auto seg2: vec){
        if(maxr>=0){
            if(seg2.l>maxr){
                ans+=maxr-minl+1;
                minl=seg2.l,maxr=seg2.r;
            }
        }
        minl=min(minl,seg2.l),maxr=max(maxr,seg2.r);
    }
    ans+=maxr-minl+1;
    print1(ans);
	return 0;
}

• 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