Submission #1275919

#TimeUsernameProblemLanguageResultExecution timeMemory
1275919WH8Strange Device (APIO19_strange_device)C++20
10 / 100
1071 ms16884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<int, int> #define mp make_pair #define pb push_back #define f first #define s second int n,a,b; vector<pair<int,int>> q; set<pair<int,int>> s; void upd(int l, int r){ //~ printf("updating %lld to %lld\n", l, r); auto it=prev(s.lower_bound({l, LLONG_MIN})); if((*it).s >= l-1){ l=(*it).f; r=max((*it).s, r); s.erase(it); } it=s.lower_bound({l, LLONG_MIN}); while((*it).f <= r+1){ r=max((*it).s, r); s.erase(it); it=s.lower_bound({l, LLONG_MIN}); } s.insert({l, r}); //~ for(auto [a,b]:s){ //~ printf("(%lld, %lld) ",a,b); //~ } //~ cout<<endl; } signed main(){ cin>>n>>a>>b; if(a > 1e18/b){ int ans=0; for(int i=0;i<n;i++){ int l,r;cin>>l>>r; ans+=r-l+1; } cout<<ans; return 0; } int m=a*b; s.insert({-5,-5}); s.insert({1e18+5,1e18+5}); for(int i=0;i<n;i++){ int l,r;cin>>l>>r; q.pb({l,r}); if(r-l >= m){ cout<<m; return 0; } if(r % m < l % m){ upd(l%m, m-1); upd(0, r%m); } else { upd(l%m, r%m); } } int ans=0; for(auto it:s){ ans+=it.s-it.f+1; } cout<<ans-2; }
#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...