Submission #1095036

#TimeUsernameProblemLanguageResultExecution timeMemory
1095036ro9669Strange Device (APIO19_strange_device)C++17
100 / 100
336 ms69076 KiB
#include <bits/stdc++.h> #define fi first #define se second #define all(v) v.begin() , v.end() #define sz(v) int(v.size()) #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin()); using namespace std; typedef long long ll; typedef pair<int , int> ii; typedef pair<long long , int> lli; const int maxN = int(2e6)+7; const ll inf = ll(1e18)+7; pair<ll , ll> p[maxN] , nxt_p[maxN]; void solve(){ int n; ll a , b; cin >> n >> a >> b; for (int i = 1 ; i <= n ; i++) cin >> p[i].fi >> p[i].se; a /= __gcd(a , b + 1); if (inf / a < b){ ll ans = 0; for (int i = 1 ; i <= n ; i++) ans += 1ll * (p[i].se - p[i].fi + 1); cout << ans << "\n"; } else{ ll x = a * b; int num = 0; for (int i = 1 ; i <= n ; i++){ if (p[i].fi + x - 1 <= p[i].se){ cout << x << "\n"; return; } if (p[i].fi % x <= p[i].se % x){ nxt_p[++num] = {p[i].fi % x , p[i].se % x}; } else{ nxt_p[++num] = {p[i].fi % x , x - 1}; nxt_p[++num] = {0 , p[i].se % x}; } } n = num; sort(nxt_p + 1 , nxt_p + n + 1); ll ans = 1ll * (nxt_p[1].se - nxt_p[1].fi + 1) , cur = nxt_p[1].se + 1; for (int i = 2 ; i <= n ; i++){ if (max(cur , nxt_p[i].fi) <= nxt_p[i].se){ ans += nxt_p[i].se - max(cur , nxt_p[i].fi) + 1; cur = nxt_p[i].se + 1; } } cout << ans << "\n"; } } #define name "A" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(name".INP" , "r")){ freopen(name".INP" , "r" , stdin); freopen(name".OUT" , "w" , stdout); } int t = 1; //cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...