Submission #743662

#	Time	Username	Problem	Language	Result	Execution time	Memory
743662		fanwen	Strange Device (APIO19_strange_device)	C++17	100 / 100	612 ms	45616 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()

#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK)                         \
    if (fopen(TASK ".inp", "r")) {         \
        freopen(TASK ".inp", "r", stdin);  \
        freopen(TASK ".out", "w", stdout); \
    }

template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
int N;
#define int long long
const int INF = 2e18;
long long A, B;
void process(void) {
    cin >> N >> A >> B;
    int period = A / __gcd(A, B + 1);
    if(INF / B >= period) period *= B;
    else period = INF;
    vector <pair <int, int>> events;
    while(N--) {
        int l, r; cin >> l >> r;
        if(r - l + 1 >= period) return void(cout << period);
        l %= period, r %= period;
        if(l <= r) {
            events.push_back(make_pair(l, 0));
            events.push_back(make_pair(r, 1));
        } else {
            events.push_back(make_pair(0, 0));
            events.push_back(make_pair(r, 1));
            events.push_back(make_pair(l, 0));
            events.push_back(make_pair(period - 1, 1));
        }
    }
    sort(ALL(events));
    int ans = 0, Leftmost = -1, cnt = 0;
    for (auto [x, i] : events) {
        if(i == 0) {
            cnt++;
            if(Leftmost == -1) Leftmost = x;
        } else {
            cnt--;
            if(cnt == 0) {
                ans += x - Leftmost + 1;
                Leftmost = -1;
            }
        }
    }
    cout << ans;
}
signed main() {
    file("TASK");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) {
        process();
        cout << '\n';
    }
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(TASK ".inp", "r", stdin);  \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:64:5: note: in expansion of macro 'file'
   64 |     file("TASK");
      |     ^~~~
strange_device.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(TASK ".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:64:5: note: in expansion of macro 'file'
   64 |     file("TASK");
      |     ^~~~

• 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