Submission #443838

#	Time	Username	Problem	Language	Result	Execution time	Memory
443838		prvocislo	Strange Device (APIO19_strange_device)	C++17	100 / 100	785 ms	68988 KiB

strange_device

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

int n;
ll mod, a, b;
const ll inf = 2e18;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> a >> b;
    a /= __gcd(a, b+1);
    if (inf/a <= b) mod = inf;
    else mod = a*b;
    vector<pair<ll, int> > v;
    for (int i = 0; i < n; i++)
    {
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= mod)
        {
            v.push_back({0, 1});
            v.push_back({mod, -1});
        }
        else
        {
            l %= mod, r %= mod;
            if (l <= r) 
            {
                v.push_back({l, 1}), v.push_back({r+1, -1});
            }
            else
            {
                v.push_back({0, 1}), v.push_back({r+1, -1});
                v.push_back({l, 1}), v.push_back({mod, -1});
            } 
        }
    }
    //cout << "===========\n" << mod << "\n";
    sort(v.begin(), v.end());
    ll ans = 0; int sum = 0;
    for (int i = 0; i < v.size() - 1; i++)
    {
        //cout << v[i].first << " " << v[i].second << "\n";
        sum += v[i].second;
        if (sum) ans += v[i+1].first-v[i].first;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < v.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~

• 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