Submission #926594

#	Time	Username	Problem	Language	Result	Execution time	Memory
926594		TAhmed33	Strange Device (APIO19_strange_device)	C++98	100 / 100	1175 ms	118676 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ll2;
int main () {
    ll n, a, b; cin >> n >> a >> b;
    ll2 u = a; u *= b; u /= __gcd(a, b + 1);
    vector <pair <ll, ll>> arr(n); 
    bool flag = 0;
    for (auto &[x, y] : arr) {
        cin >> x >> y;
        flag |= y - x + 1 >= u;
    }
    if (flag) {
        cout << (ll)u << '\n';
        return 0;
    }
    vector <pair <ll2, ll2>> intervals;
    for (auto [x, y] : arr) {
        ll2 g = x % u, h = y % u;
        if (g <= h) {
            intervals.push_back({g, h});
        } else {
            intervals.push_back({g, u - 1});
            intervals.push_back({0, h});
        }
    }
    sort(intervals.begin(), intervals.end(), [] (pair <ll2, ll2> &x, pair <ll2, ll2> &y) {
        return x.first == y.first ? x.second > y.second : x.first < y.first;
    });
    stack <pair <ll2, ll2>> dd;
    for (auto &[x, y] : intervals) {
        while (!dd.empty() && !(dd.top().first > y || dd.top().second < x)) {
            x = min(x, dd.top().first); y = max(y, dd.top().second);
            dd.pop(); 
        }
        dd.push({x, y});
    }
    ll2 sum = 0;
    while (!dd.empty()) {
        auto k = dd.top(); dd.pop();
        sum += k.second - k.first + 1;
    }
    cout << ll(sum) << '\n';
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:10:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for (auto &[x, y] : arr) {
      |                ^
strange_device.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [x, y] : arr) {
      |               ^
strange_device.cpp:32:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto &[x, y] : intervals) {
      |                ^

• 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