Submission #703046

#	Time	Username	Problem	Language	Result	Execution time	Memory
703046		Elvin_Fritl	Strange Device (APIO19_strange_device)	C++17	65 / 100	1502 ms	39736 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define big 1e18
 
ll n, a, b, l, r, res;
vector<pair<ll,ll>> v;
 
ll gcd(ll c1, ll c2) {
    if (!c2) return c1;
    return gcd(c2, c1%c2);
}
 
int main() {
    cin >> n >> a >> b;
    a = a/gcd(a, b+1);
    if ((double)a > (double)big+1/b){
        res = big+1;
    }
    else {
        res = a*b;
    }
    while (n--) {
        cin >> l >> r;
        l%=res;
        r%=res;
        if (l>r) v.push_back({0, r}), v.push_back({l, res-1});
        else v.push_back({l, r});
    }
    sort(v.begin(), v.end());
    ll fi=0, se=INT_MIN;
    for (ll i=0;i<v.size();i++){
        ll d1=v[i].first;
        ll d2=v[i].second;
        if(se<d1){
            fi+=d2-d1+1;
        }
        else{
            fi+=max((ll)0, d2-se);
        }
        se=max(se, d2);
    }
    cout << fi <<endl;;
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:32:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (ll i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

• 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