Submission #551282

#	Time	Username	Problem	Language	Result	Execution time	Memory
551282		truc12a2cvp	Strange Device (APIO19_strange_device)	C++14	100 / 100	612 ms	69772 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> II;
const int N = 1e6 + 5, logN = 20;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n;
ll A, B, cyc, sum = 0;
vector<II> vt;
II seg[N];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> A >> B;
    for(int i = 1; i <= n; i ++) cin >> seg[i].first >> seg[i].second, sum += seg[i].second - seg[i].first + 1;
    ll k = A / __gcd(A, B + 1);
    if(k > INF / B + 1){
       cout << sum << endl;
       return 0;
    }
    cyc = k * B;
    for(int i = 1; i <= n; i ++){
       if(seg[i].second - seg[i].first + 1 >= cyc){
              cout << cyc << endl;
              return 0;
       }
       if(seg[i].first % cyc <= seg[i].second % cyc) vt.push_back(II(seg[i].first % cyc, seg[i].second % cyc));
       else vt.push_back(II(0, seg[i].second % cyc)), vt.push_back(II(seg[i].first % cyc, cyc - 1));
    }
    sort(vt.begin(), vt.end());
    ll Max = 0, ans = 0;
    for(auto x : vt){
       Max = max(Max, x.first);
       ans += max(0ll, x.second - Max + 1);
       Max = max(Max, x.second + 1);
    }
    cout << ans << endl;
    return 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