Submission #1362596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362596		altern23	Strange Device (APIO19_strange_device)	C++20	100 / 100	273 ms	56316 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 1e6;
const ll INF = 1e18;

ll N, A, B;
ll L[MAXN+5], R[MAXN+5];

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            cin >> N >> A >> B;
            
            for (int i = 1; i <= N; i++) {
                  cin >> L[i] >> R[i];
            }
            
            if (A/__gcd(A,B+1) > INF/B) {
                  ll ans = 0;
                  for (int i = 1; i <= N; i++) ans += R[i]-L[i]+1;
                  cout << ans << "\n";
                  return 0;
            }
            
            ll cur = A/__gcd(A,B+1)*B;
            
            vector <pair<ll, ll>> segments;

            for (int i = 1; i <= N; i++) {
                  if (R[i]-L[i]+1 >= cur) {
                        cout << cur << "\n";
                        return 0;
                  }
            }

            for (int i = 1; i <= N; i++) {
                  L[i] %= cur, R[i] %= cur;
                  if (L[i] > R[i]) {
                        segments.push_back({L[i], cur-1}), segments.push_back({0, R[i]});
                  }
                  else segments.push_back({L[i], R[i]});
            }

            sort(segments.begin(), segments.end());

            vector <pair<ll, ll>> sweep;
            
            for (auto [L, R] : segments) {
                  if (sweep.empty()) sweep.push_back({L, R});
                  else {
                        if (sweep.back().second < L) {
                              sweep.push_back({L, R});
                        }
                        else {
                              sweep.back().second = max(sweep.back().second, R);
                        }
                  }
            }

            ll ans = 0;
            for (auto [L, R] : sweep) ans += R-L+1;

            cout << ans << "\n";
      }
}

/*
X = 10, Y = 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 2 4 5 6 8 9 0 2 3 4 6 7 8 
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2

cari X dimana X > 0 dan (X+X/B)%A == 0 dan X%B == 0
B/X

X(B+1)/B % A == 0

15+5
*/

• 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