Submission #145362

#	Time	Username	Problem	Language	Result	Execution time	Memory
145362		dolphingarlic	Strange Device (APIO19_strange_device)	C++14	100 / 100	727 ms	41496 KiB

strange_device

#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, a, b;
    cin >> n >> a >> b;

    vector<pair<ll, ll>> segs;

    ll s = 0;

    FOR(i, 1, n + 1) {
        ll l, r;
        cin >> l >> r;

        segs.push_back({l, r});

        s += r - l + 1;
    }

    ll l = segs[0].first;
    ll r = segs[0].second;

    ll k = a / __gcd(a, b + 1);

    if (log(k) + log(b) >= 18 * log(10)) {
        cout << s << '\n';
    } else {
        k *= b;

        vector<pair<ll, ll>> intervals;

        for (auto seg : segs) {
            if (seg.second - seg.first + 1 >= k) {
                cout << k << endl;
                return 0;
            }

            if (seg.first % k > seg.second % k) {
                intervals.push_back({0, seg.second % k});
                intervals.push_back({seg.first % k, k - 1});
            }

            else {
                intervals.push_back({seg.first % k, seg.second % k});
            }
        }

        sort(intervals.begin(), intervals.end());

        ll cur_start = intervals[0].first;
        ll cur_end = intervals[0].second;

        ll ans = 0;

        FOR(i, 1, intervals.size()) {
            if (intervals[i].first > cur_end + 1) {
                ans += cur_end - cur_start + 1;
                cur_start = intervals[i].first;
                cur_end = intervals[i].second;
            }

            else {
                cur_end = max(cur_end, intervals[i].second);
            }
        }

        ans += cur_end - cur_start + 1;

        cout << ans << '\n';
    }

    return 0;
}

Compilation message (stderr)

strange_device.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
strange_device.cpp: In function 'int main()':
strange_device.cpp:3:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
strange_device.cpp:63:13:
         FOR(i, 1, intervals.size()) {
             ~~~~~~~~~~~~~~~~~~~~~~      
strange_device.cpp:63:9: note: in expansion of macro 'FOR'
         FOR(i, 1, intervals.size()) {
         ^~~
strange_device.cpp:28:8: warning: unused variable 'l' [-Wunused-variable]
     ll l = segs[0].first;
        ^
strange_device.cpp:29:8: warning: unused variable 'r' [-Wunused-variable]
     ll r = segs[0].second;
        ^

• 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