Submission #784527

#	Time	Username	Problem	Language	Result	Execution time	Memory
784527		kebine	Strange Device (APIO19_strange_device)	C++17	65 / 100	706 ms	64324 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
//*AC BERSAMA ALLAH  FORTIS FORTUNA ADIUVAT
//# nyampah
ll sz;
vector<pair<ll,bool> > lr;
vector<pair<ll,ll> > lr1;
ll n, a, b;

ll gcd(ll x, ll y){
    if(y==0) return x;
    else return gcd(y,x%y);
}

bool comp(pair<ll,bool> a, pair<ll,bool> b){
    if(a.fi==b.fi) return a.se<b.se;
    else return a.fi<b.fi;
}

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

    cin >> n >> a >> b;
    // sz = abs(szz(a,b));
    sz = (__int128_t) a * b / gcd(a,b+1);
    // cout<<sz<<'\n';

    for(int i=0;i<n;i++){
        ll l,r; cin>>l>>r;
        l%=sz; r%=sz;
        if(l>r){
            lr.pb(make_pair(0,0)); lr.pb(make_pair(r,1));
            lr.pb(make_pair(l,0)); lr.pb(make_pair(sz-1,1));
        }
        else {
            lr.pb(make_pair(l,0)); lr.pb(make_pair(r,1));
        }
    }
    sort(lr.begin(),lr.end(),comp);

    ll cnt=0, l, r;
    for(auto i : lr){
        if(i.se == 0){
            if(cnt==0) l=i.fi;
            cnt++;
        }
        else cnt--;
        
        if(cnt==0){
            r = i.fi;
            lr1.pb(make_pair(l,r));
        }
    }

    ll ans=0;
    for(auto i : lr1){
        ans+=(i.second-i.first+1);
    }
    cout<<ans<<'\n';


    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:56:33: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |             lr1.pb(make_pair(l,r));
      |                                 ^

• 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