Submission #130302

#	Time	Username	Problem	Language	Result	Execution time	Memory
130302		osaaateiasavtnl	Strange Device (APIO19_strange_device)	C++14	100 / 100	998 ms	51464 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, A, B;
    cin >> n >> A >> B;
    int D = A / __gcd(A, B + 1);
    int M = B * D;
    vector <pair <int, int> > a;
    while (n--) {
        int l, r;
        cin >> l >> r;

        if (l / M == r / M) {
            a.push_back({l % M, r % M});
            continue;
        }   

        int l1 = ((l + M - 1) / M) * M;
        int r1 = (r / M) * M - 1;
 
        int c = 0;
        if (l1 <= r1) {
            cout << M << '\n';
            exit(0);
        }   
 
        // [l % B; B - 1]
        // [0; r % B]
 
        int tl = r % M, tr = l % M;
        
        if (tl < tr) {
            a.push_back({0, tl});
            a.push_back({tr, M - 1});
        }   
        else {
            cout << M << '\n';
            exit(0);
        }   
    }   
    int ans = 0;
    vector <pair <int, int> > sc;
    for (auto e : a) {
        sc.push_back({e.first, 1});
        sc.push_back({e.second + 1, -1});
    }   
    sort(sc.begin(), sc.end());
    int b = 0;
    for (int i = 0; i + 1 < (int)sc.size(); ++i) {
        b += sc[i].second;
        if (b) ans += sc[i + 1].first - sc[i].first;            
    }   
    cout << ans << '\n';
}  

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:27:13: warning: unused variable 'c' [-Wunused-variable]
         int c = 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