Submission #1044716

#TimeUsernameProblemLanguageResultExecution timeMemory
1044716vjudge1Strange Device (APIO19_strange_device)C++17
100 / 100
330 ms31928 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; ll n, a, b; vector<pair<ll, ll>> v; void solve(){ cin >> n >> a >> b; ll g = gcd(b+1, a); ll val = a / g; if(log2(val) + log2(b) > 60){ ll tot = 0; for(int i = 1; i <= n; ++i){ ll t1, t2; cin >> t1 >> t2; tot += t2 - t1 + 1; } cout << tot; return; } ll rep = b*val; ll ans = 0; for(int i = 1; i <= n; ++i){ ll t1, t2; cin >> t1 >> t2; if(t1 + rep <= t2){ ans = rep; }else{ if(t2 % rep < t1 % rep){ v.pb({0, t2 % rep}); v.pb({t1 % rep, rep - 1}); }else{ v.pb({t1%rep, t2%rep}); } } } if(ans == rep) cout << ans; else{ sort(all(v)); ll ans = rep; if(v.size() && v[0].ff > 0) ans -= v[0].ff; if(v.size() && v.back().ss < rep - 1) ans -= rep - v.back().ss - 1; ll mx = v[0].ss; for(int i = 1; i < v.size(); ++i){ if(v[i].ff > mx) ans -= v[i].ff - mx - 1; mx = max(mx, v[i].ss); } // for(auto p: v) cout << p.ff << ' ' << p.ss << '\n'; cout << ans; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 1; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:64:15: warning: unused variable 'aa' [-Wunused-variable]
   64 |   int tt = 1, aa;
      |               ^~
#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...