Submission #934587

#	Time	Username	Problem	Language	Result	Execution time	Memory
934587		VladaMG98	Strange Device (APIO19_strange_device)	C++17	100 / 100	1420 ms	313656 KiB

strange_device

    // Problem: A - Strange Device
    // Contest: Virtual Judge - 2024-02-27 APIO Simulation
    // URL: https://vjudge.net/contest/612540#problem/A
    // Memory Limit: 512 MB
    // Time Limit: 5000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
     
    #include <bits/stdc++.h>
    using namespace std;
     
    #define rep(i, a, b) for(int i = a; i < (b); ++i)
    #define all(x) begin(x), end(x)
    #define sz(x) (int)(x).size()
    #define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
    #define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
    #define what_is(x) cerr << #x << " is " << x << endl
    long long typedef ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef vector<int> vi;
     
    int n; ll A, B;
    const int MAXN = 1000010;
    ll L[MAXN], R[MAXN];
     
    void subtask1() {
        set<pair<ll, ll>> ans;
        for (int i = 1; i <= n; i++) {
            for (ll j = L[i]; j <= R[i]; j++) {
                ll x = (j + j / B) % A;
                ll y = j % B;
                ans.insert({x, y});
            }
        }
        cout << sz(ans) << endl;
    }
     
    void subtask4() {
        bool halved = false;
        if (A % 2 == 0) {
            A /= 2;
            halved = true;
        }
        bool full = false;
        vector<pair<ll, int>> events;
        for (int i = 1; i <= n; i++) {
            ll l = L[i] % A, r = R[i] % A;
            if (R[i] - L[i] + 1 >= A) {
                full = true;
                break;
            }
            if (l <= r) {
                events.push_back({l, -1});
                events.push_back({r + 1, 1});
            } else {
                events.push_back({0, -1});
                events.push_back({r + 1, 1});
                events.push_back({l, -1});
                events.push_back({A, 1});
            }
        }
     
        if (full) {
            cout << A << endl;
            if (halved) A *= 2;
            return;
        }
     
        ll ans = 0;
        int open = 0;
        sort(all(events));
        ll cur_time = 0;
        for (auto ev : events) {
            cout << ev.first << " " << ev.second << endl;
            ll passed = ev.first - cur_time;
            if (open > 0) ans += passed;
            open -= ev.second;
            cur_time = ev.first;
        }
        cout << ans << endl;
     
        if (halved) A *= 2;
    }
     
    bool not_taken (ll pos, const vector<ll> &begs, const vector<ll> &ends) {
        ll begs_before = lower_bound(all(begs), pos + 1) - begs.begin();
        ll ends_before = lower_bound(all(ends), pos) - ends.begin();
        return begs_before == ends_before;
    }
     
    ll process (vector<pair<ll, int>> &v) {
        sort(all(v));
        ll cur_time = 0;
        int open = 0;
        ll ans = 0;
     
        vector<ll> begs, ends;
        for (auto ev : v) {
            if (ev.second == -1) begs.push_back(ev.first);
            else ends.push_back(ev.first);
     
            ll passed = ev.first - cur_time;
            if (open > 0) ans += passed;
            open -= ev.second;
            cur_time = ev.first;
        }
        return ans;
    }
     
    void solve() {
        ll cycle_length = A / __gcd(A, B + 1);
        bool got_all = false;
     
        vector<pair<ll, int>> events;
        unordered_map<ll, vector<pair<ll, int>>> events_all;
     
        for (int i = 1; i <= n; i++) {
            ll l = L[i], r = R[i];
            ll k1 = l / B, r1 = l % B;
            ll k2 = r / B, r2 = r % B;
     
            if (k1 == k2) {
                events_all[k1 % cycle_length].emplace_back(r1, -1);
                events_all[k1 % cycle_length].emplace_back(r2 + 1, 1);
            } else {
                events_all[k1 % cycle_length].emplace_back(r1, -1);
                events_all[k1 % cycle_length].emplace_back(B, 1);
     
                events_all[k2 % cycle_length].emplace_back(0, -1);
                events_all[k2 % cycle_length].emplace_back(r2 + 1, 1);
            }
     
            ll fr = k1 + 1, tt = k2 - 1;
            if (fr > tt) continue;
            if (tt - fr + 1 >= cycle_length) {
                got_all = true;
                break;
            }
     
            fr %= cycle_length;
            tt %= cycle_length;
     
            if (fr <= tt) {
                events.push_back({fr, -1});
                events.push_back({tt + 1, 1});
            } else {
                events.push_back({0, -1});
                events.push_back({tt + 1, 1});
                events.push_back({fr, -1});
                events.push_back({cycle_length, 1});
            }
        }
     
        if (got_all) {
            cout << B * cycle_length << endl;
            return;
        }
     
        sort(all(events));
        ll cur_time = 0;
        int open = 0;
     
        vector<ll> begs, ends;
        ll whole = process(events);
     
        for (auto ev : events) {
            if (ev.second == -1) begs.push_back(ev.first);
            else ends.push_back(ev.first - 1);
        }
     
        ll ans = B * whole;
     
        for (auto [k, v] : events_all) {
            if (not_taken(k, begs, ends)) {
                ans += process(v);
            }
        }
     
        cout << ans << endl;
    }
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
        cin >> n >> A >> B;
        ll S = 0, SL = 0;
        for (int i = 1; i <= n; i++) {
            cin >> L[i] >> R[i];
            S += (R[i] - L[i] + 1);
            SL = max(SL, R[i] - L[i] + 1);
        }
        solve();
        return 0;
    }

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:161:12: warning: unused variable 'cur_time' [-Wunused-variable]
  161 |         ll cur_time = 0;
      |            ^~~~~~~~
strange_device.cpp:162:13: warning: unused variable 'open' [-Wunused-variable]
  162 |         int open = 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