Submission #1086017

#TimeUsernameProblemLanguageResultExecution timeMemory
1086017peacebringer1667Strange Device (APIO19_strange_device)C++17
100 / 100
391 ms69992 KiB
#include<bits/stdc++.h> #define ll long long #define ldb long double #define fi first #define se second #define sza(a) (int)a.size() #define pir pair<int,int> #define pirll pair<ll,ll> using namespace std; const ll inf = 1e18 + 1e17; const int maxn = 1e6 + 5; ll l[maxn],r[maxn]; vector <pirll> lst; void input(int n){ for (int i = 1 ; i <= n ; i++) cin >> l[i] >> r[i]; } ll get_val(ll A,ll B){ A /= __gcd(A,B + 1); if (A > inf/B) return inf; return A * B; } void gen_pir(int n,ll T){ for (int i = 1 ; i <= n ; i++){ ll L = l[i],R = r[i]; if (L/T == R/T){ lst.push_back({L % T,R % T}); continue; } if (R/T > L/T + 1){ lst.push_back({0,T - 1}); return; } ll NL = L + (T - L % T) - 1; if (NL >= L) lst.push_back({L % T,NL % T}); ll NR = R - R % T; lst.push_back({NR % T,R % T}); //L..R } } ll solve(int n,ll T){ gen_pir(n,T); sort(lst.begin(),lst.end()); ll L = lst[0].fi,R = lst[0].se; ll res = lst[0].se - lst[0].fi + 1,cur = R; for (int i = 1 ; i < lst.size() ; i++){ L = lst[i].fi;R = lst[i].se; if (R > cur) res += R - max(cur + 1,L) + 1; cur = max(cur,R); } return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n;ll A,B; cin >> n >> A >> B; input(n); ll T = get_val(A,B); cout << solve(n,T); return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'long long int solve(int, long long int)':
strange_device.cpp:57:21: 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]
   57 |  for (int i = 1 ; i < lst.size() ; i++){
      |                   ~~^~~~~~~~~~~~
#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...