Submission #783498

#TimeUsernameProblemLanguageResultExecution timeMemory
783498makanhuliaStrange Device (APIO19_strange_device)C++17
100 / 100
368 ms19088 KiB
# include <bits/stdc++.h> # define int long long # define vi vector<int> # define pb push_back # define pii pair<int, int> # define fi first # define se second # define endl '\n' # define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n, a, b; void solve() { cin >> n >> a >> b; __int128_t t=(__int128_t)a*b; __int128_t cycle=t / __gcd(a, b+1); vector<pii> v; bool ok=1; int ya; if(cycle <= 1e18) { int tm=a*b; for(int i=1; i<=n; i++) { int l, r; cin >> l >> r; if((r-l+1) >= tm) { cout << min(r-l+1, tm) << endl; return; } l%=cycle; r%=cycle; if(r < l) { v.pb({l, cycle-1}); v.pb({0, r}); } else { v.pb({l, r}); } } } else { for(int i=1; i<=n; i++) { int l, r; cin >> l >> r; if((r-l+1) >= cycle) { cout << r-l+1 << endl; return; } l%=cycle; r%=cycle; if(r < l) { v.pb({l, cycle-1}); v.pb({0, r}); } else { v.pb({l, r}); } } } sort(v.begin(), v.end()); bool st=1; int l=0, r=1, ans=0; // for(pii i : v) cout << "l r " << i.fi << " " << i.se << endl; for(auto i : v) { if(st) { l=i.fi, r=i.se; st=0; continue; } if(i.fi>=l && i.fi<=r) { r=max(r, i.se); } else { ans+=(r-l+1); l=i.fi, r=i.se; } } ans+=(r-l+1); cout << ans << endl; } signed main() { jess; solve(); }

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:20:10: warning: unused variable 'ok' [-Wunused-variable]
   20 |     bool ok=1;
      |          ^~
strange_device.cpp:21:9: warning: unused variable 'ya' [-Wunused-variable]
   21 |     int ya;
      |         ^~
#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...