Submission #721626

#TimeUsernameProblemLanguageResultExecution timeMemory
721626victor_gaoStrange Device (APIO19_strange_device)C++17
10 / 100
592 ms7072 KiB
//#pragma GCC optimize("Ofast,unroll-loops,O3") //#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native") #include<bits/stdc++.h> //#include<bits/extc++.h> //#pragma pack(1) #define fast ios::sync_with_stdio(0); cin.tie(0); #define int long long #define pii pair<int,int> #define x first #define y second using namespace std; //using namespace __gnu_pbds; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset; //typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set; int n,a,b,t; int findt(){ if (a<b&&(b+1)%a==0) return b; int go=b+1,g=__gcd(go,a); // cout<<go<<" "<<a<<' '<<b<<" "<<g<<'\n'; // lcm(go,a)/go*b if ((double)(log10(a/g)+log10(b))>=18.0001) return 2e18; else return a/g*b; } set<pii>st; void add(int l,int r){ if (st.empty()){ st.insert(pii(l,r-l+1)); return; } auto it=st.insert(pii(l,r-l+1)).x; pii now={l,r-l+1}; while (it!=st.begin()){ auto it1=prev(it); pii last=*it1; if (last.x+last.y>=l){ st.erase(it1); it=st.erase(it); now.y=(now.x+now.y-1)-last.x+1; now.x=last.x; it=st.insert(now).x; } else break; } while (it!=st.end()){ auto it1=next(it); if (it1==st.end()) break; pii nxt=*it1; if (now.x+now.y>=nxt.x){ st.erase(it1); it=st.erase(it); now.y=(nxt.x+nxt.y-1)-now.x+1; it=st.insert(now).x; } else break; } } signed main(){ fast cin>>n>>a>>b; t=findt(); if (t>(int)1e18){ int ans=0; for (int i=1;i<=n;i++){ int l,r; cin>>l>>r; ans+=(r-l+1); } cout<<ans<<'\n'; } else { for (int i=1;i<=n;i++){ int l,r; cin>>l>>r; l%=t; r%=t; if (l>r){ add(l,t-1); add(0,r); } else add(l,r); } int ans=0; for (auto i:st){ ans+=i.y; // cout<<i.x<<" ~ "<<i.x+i.y-1<<'\n'; } cout<<ans<<'\n'; } }
#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...