Submission #748393

#	Time	Username	Problem	Language	Result	Execution time	Memory
748393		Sharky	Strange Device (APIO19_strange_device)	C++17	100 / 100	655 ms	84848 KiB

strange_device

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

#define int long long

int co[2000010], d[2000010];

void update(int l, int r) {
    // cout << "updating: " << l << " " << r << "\n";
    d[l]++;
    d[r]--;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, A, B, ans = 0;
    cin >> n >> A >> B;
    map<int, bool> mp;
    int g = gcd(A, B + 1);
    int mul = (A + g - 1) / g;
    if (3E18 / mul < B) mul = 3E18;
    else mul = (A / g) * B;
    // cout << mul << endl;
    vector<pair<int, int>> ends;
    vector<int> sorted;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        if (r - l + 1 >= mul) {
            cout << mul << endl;
            return 0;
        }
        l %= mul, r %= mul;
        // cout << l << ' ' << r << '\n';
        ends.emplace_back(l, r + 1);
        sorted.push_back(l);
        sorted.push_back(r + 1);
    }
    sorted.push_back(0);
    sorted.push_back(mul);
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    for (int i = 0; i < sorted.size(); i++) co[i+1] = sorted[i];
    int mx = 0;
    for (int i = 0; i < ends.size(); i++) {
        ends[i].first = lower_bound(sorted.begin(), sorted.end(), ends[i].first) - sorted.begin() + 1;
        ends[i].second = lower_bound(sorted.begin(), sorted.end(), ends[i].second) - sorted.begin() + 1;
        if (ends[i].first > ends[i].second) {
            update(ends[i].first, sorted.size());
            update(1, ends[i].second);
        } else update(ends[i].first, ends[i].second);
    }
    for (int i = 1; i <= sorted.size(); i++) d[i] += d[i-1];
    for (int i = 1; i < sorted.size(); i++) {
        // cout << co[i] << ' ' << co[i+1] << ' ' << d[i] << '\n';
        if (d[i] > 0) ans += co[i+1] - co[i];
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < sorted.size(); i++) co[i+1] = sorted[i];
      |                     ~~^~~~~~~~~~~~~~~
strange_device.cpp:45:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < ends.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
strange_device.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 1; i <= sorted.size(); i++) d[i] += d[i-1];
      |                     ~~^~~~~~~~~~~~~~~~
strange_device.cpp:54:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 1; i < sorted.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
strange_device.cpp:44:9: warning: unused variable 'mx' [-Wunused-variable]
   44 |     int mx = 0;
      |         ^~

• 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