Submission #382903

#	Time	Username	Problem	Language	Result	Execution time	Memory
382903		danielcm585	Strange Device (APIO19_strange_device)	C++14	35 / 100	776 ms	61528 KiB

strange_device

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

#define fi first
#define se second

typedef long long ll;
typedef pair<ll,ll> ii;

const int N = 1e6;
ll n, a, b;
ll l[N+2], r[N+2];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    ll cyc = a/__gcd(a,b+1)*b;
    for (int i = 1; i <= n; i++) {
        if (r[i]-l[i]+1 >= cyc) {
            cout << cyc << '\n';
            return 0;
        }
    }
    // cout << ">> " << cyc << '\n';
    vector<ii> v;
    for (int i = 1; i <= n; i++) {
        l[i] %= cyc, r[i] %= cyc;
        // cout << l[i] << ' ' << r[i] << '\n';
        v.push_back(ii(l[i],1));
        v.push_back(ii(r[i]+1,-1));
        if (l[i] > r[i]) {
            v.push_back({0,1});
        }
    }
    v.push_back({cyc,-1});
    assert(v.size() <= 4*n);
    sort(v.begin(),v.end());
    ll ans = 0, cur = 0, ls = -1;
    for (int i = 0; i < v.size(); ) {
        ll pos = v[i].fi;
        if (cur > 0) ans += pos-ls;
        // cout << ls+1 << ' ' << pos << " -> " << cur << '\n';
        while (i < v.size() && v[i].fi == pos) {
            cur += v[i].se, i++;
        }
        ls = pos;
    }
    cout << ans << '\n';
    return 0;
}

/*
0,0 -> 1,1 -> ... -> 0,0

t%a==0
t%(b+1)==0
a*(b+1)/f(a,b+1)-k/(b+1)
= a*(b+1)/f(a,b+1)-a*(b+1)/f/(b+1)
= a*(b+1)/f(a,b+1)-a/f
= a*b/f
L R

---------
 ----------------
                     -----------------
                            ----------
-------
*/

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from strange_device.cpp:1:
strange_device.cpp: In function 'int main()':
strange_device.cpp:39:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   39 |     assert(v.size() <= 4*n);
      |            ~~~~~~~~~^~~~~~
strange_device.cpp:42: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]
   42 |     for (int i = 0; i < v.size(); ) {
      |                     ~~^~~~~~~~~~
strange_device.cpp:46:18: 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 |         while (i < v.size() && v[i].fi == pos) {
      |                ~~^~~~~~~~~~

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