Submission #268709

#	Time	Username	Problem	Language	Result	Execution time	Memory
268709		evpipis	Strange Device (APIO19_strange_device)	C++11	100 / 100	621 ms	77868 KiB

strange_device

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pll;

const ll mx = 1e18;
vector<pll> vec, help;

ll gcd(ll a, ll b){
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

ll find_fir(ll a, ll b){
    ll ans = a/gcd(a, b+1);
    if (ans <= mx/b)
        ans = ans*b;
    else
        ans = mx+1;
    return ans;
}

ll solve(ll m){
    for (int i = 0; i < vec.size(); i++){
        pll cur = vec[i];
        if (cur.se-cur.fi+1 >= m)
            return m;

        cur.fi %= m;
        cur.se %= m;

        if (cur.fi <= cur.se)
            help.pb(cur);
        else
            help.pb(mp(0, cur.se)), help.pb(mp(cur.fi, m-1));
    }

    vec.clear();
    sort(help.begin(), help.end());
    for (int i = 0; i < help.size(); i++){
        pll cur = help[i];
        while (!vec.empty() && cur.fi == vec.back().fi)
            vec.pop_back();
        if (vec.empty() || cur.se > vec.back().se)
            vec.pb(cur);
    }

    ll ans = 0;
    for (int i = 0; i < vec.size(); i++){
        pll cur = vec[i];
        if (i+1 < vec.size() && vec[i+1].fi-1 < cur.se)
            ans += vec[i+1].fi-cur.fi;
        else
            ans += cur.se-cur.fi+1;
    }

    return ans;
}

int main(){
    int n;
    ll a, b;
    scanf("%d %lld %lld", &n, &a, &b);

    ll m = find_fir(a, b);

    for (int i = 0; i < n; i++){
        ll l, r;
        scanf("%lld %lld", &l, &r);
        vec.pb(mp(l, r));
    }

    printf("%lld\n", solve(m));
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'll solve(ll)':
strange_device.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < vec.size(); i++){
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < help.size(); i++){
      |                     ~~^~~~~~~~~~~~~
strange_device.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < vec.size(); i++){
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if (i+1 < vec.size() && vec[i+1].fi-1 < cur.se)
      |             ~~~~^~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d %lld %lld", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         scanf("%lld %lld", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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