Submission #564181

# Submission time Handle Problem Language Result Execution time Memory
564181 2022-05-18T16:45:00 Z hoanghq2004 Strange Device (APIO19_strange_device) C++14
0 / 100
237 ms 66224 KB
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int n;
    long long A, B;
    vector <pair <long long, int> > events;
    cin >> n >> A >> B;
    long long T = A / __gcd(A, B + 1) * B;
    for (int i = 0; i < n; ++i) {
        int L, R;
        cin >> L >> R;
        if (R - L + 1 >= T) {
            cout << T << '\n';
            exit(0);
        }
        L %= T, R %= T;
        if (L <= R) {
            events.push_back({L, 1});
            events.push_back({R + 1, -1});
        } else {
            events.push_back({L, 1});
            events.push_back({T, -1});
            events.push_back({0, 1});
            events.push_back({R + 1, -1});
        }
    }

    sort(events.begin(), events.end());
    int cur = 0;
    long long ans = 0;
    for (int i = 0; i + 1 < events.size(); ++i) {
        cur += events[i].second;
        if (cur != 0) ans += events[i + 1].first - events[i].first;
    }
    cout << ans;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:42:27: 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]
   42 |     for (int i = 0; i + 1 < events.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 237 ms 66224 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 237 ms 66224 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 237 ms 66224 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Incorrect 23 ms 8648 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -