Submission #1267386

#TimeUsernameProblemLanguageResultExecution timeMemory
1267386hoa208Strange Device (APIO19_strange_device)C++20
10 / 100
918 ms109960 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native") using ll = __int128; using pll = pair<ll, ll>; #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define F first #define S second #define sz(x) x.size() #define all(x) x.begin(), x.end() #define pb push_back #define minr(a, b) a = min(a, b); #define maxr(a, b) a = max(a, b); #define shit cout << "shit\n" << flush; #define tl while(1&1) continue; #define rand(l, r) uniform_ll_distribution<ll64_t>(l,r)(rng) random_device device; default_random_engine rng(device()); const ll Mod = 1e9 + 7; //998244353; const ll LG = 64; const ll SQ = 500; const ll Inf = 2e9 + 10; ll n, A, B; vector <ll> pts; ll GCD(ll x, ll y) { if(x < y) swap(x, y); if(!y) return x; return GCD(y, x%y); } ll LCP(ll x, ll y) { return x*y/GCD(x, y); } map <ll, int> val; void print(ll x) { vector <int> ret; if(x == 0) cout << 0; while(x) { ret.pb(x%10); x /= 10; } reverse(all(ret)); for(auto i : ret) cout << i; } int main() { IOS; long long in1, in2, in3; cin >> in1 >> in2 >> in3; n = in1; A = in2; B = in3; ll len = A * B; pts.pb(0); pts.pb(len-1); pts.pb(len); for(ll i = 1; i <= n; i++) { long long in1, in2; ll l, r; cin >> in1 >> in2; l = in1; r = in2; if(r-l+1 >= len) { print(len); return 0; } if(l%len <= r%len) { val[l%len]++; val[r%len + 1]--; pts.pb(l%len); pts.pb(r%len + 1); } else { val[l%len]++; val[len]--; pts.pb(l%len); val[0]++; val[r%len + 1]--; pts.pb(r%len + 1); } } sort(all(pts)); pts.resize(unique(all(pts))-pts.begin()); ll cur = 0; ll ans = 0; for(ll i = 0; i < sz(pts); i++) { ll x = pts[i]; cur += val[x]; if(cur > 0 and i < sz(pts)-1) ans += pts[i+1]-pts[i]; } print(ans); }
#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...