Submission #268476

#	Time	Username	Problem	Language	Result	Execution time	Memory
268476		evpipis	Strange Device (APIO19_strange_device)	C++11	0 / 100	5074 ms	524292 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 (a == 0)
        return b;
    return gcd(b%a, a);
}

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

set<ll> mys;

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;

        for (int j = cur.fi; j <= cur.se; j++)
            mys.insert(j%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));
    }

    return mys.size();

    ll ans = 0;
    /*for (int i = 0; i < m; i++){
        int fin = 0;
        for (int j = 0; j < help.size(); j++)
            if (help[j].fi <= i && i <= help[j].fi)
                fin = 1;

        ans += fin;
    }

    return ans;*/
    sort(help.begin(), help.end());
    for (int i = 0; i < help.size(); i++){
        pll cur = help[i];
        if (i+1 < help.size() && help[i+1].fi-1 < cur.se)
            ans += help[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);
    //assert(m <= mx);

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

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

Compilation message (stderr)

strange_device.cpp: In function 'll solve(ll)':
strange_device.cpp:32: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]
   32 |     for (int i = 0; i < vec.size(); i++){
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:63: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]
   63 |     for (int i = 0; i < help.size(); i++){
      |                     ~~^~~~~~~~~~~~~
strange_device.cpp:65: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]
   65 |         if (i+1 < help.size() && help[i+1].fi-1 < cur.se)
      |             ~~~~^~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d %lld %lld", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%lld %lld", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30