Submission #1142856

#TimeUsernameProblemLanguageResultExecution timeMemory
1142856SSSMStrange Device (APIO19_strange_device)C++20
100 / 100
271 ms33428 KiB
#include <bits/stdc++.h> /* #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC target ("avx2") */ using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #define F first #define S second #define pb push_back #define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) #define md(a) ((a%mod+mod)%mod) #define all(a) a.begin(), a.end() #define MP make_pair #define lc id<<1 #define rc lc|1 #define mid (l+r)/2 #define kill(a) cout << a << "\n", exit(0) typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll; typedef long double ld; typedef vector<vector<ll>> matrix; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=9, sq=65; ll poww(ll a, ll b, ll mod) { if (b == 0) return 1; return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod; } ll n, a, b; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>a>>b; ll x=(a/__gcd(a, b+1)); ll y; ll l1=120, l2=120; ll q=1; for(ll i=1;i<=20;i++) { q*=10; if(q>x) { l1=i-1; break; } } q=1; for(ll i=1;i<=20;i++) { q*=10; if(q>b) { l2=i-1; break; } } if((l1+l2)<18) y=x*b; else y=1000000000000000000+10; ll ans=0; vector<pll> v; bool g=0; //cout<<y<<"\n"; for(ll i=1;i<=n;i++) { ll l,r; cin>>l>>r; if(r-l+1>=y) g=1; else { ll a=l%y; if(a==0) a=y; ll b=r%y; if(b==0) b=y; if(a<=b) { v.pb({a, b}); } else { v.pb({a, y}); v.pb({1, b}); } } } if(g) kill(y); if(y!=-1) { sort(all(v)); ll mx=0; for(auto [a, b]:v) { // cout<<a<<" "<<b<<" "<<mx<<"+++\n"; if(a>mx) { ans+=(b-a+1); } else { if(b>mx) ans+=(b-mx); } mx=max(mx, b); } } cout<<ans<<"\n"; return 0; }
#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...