Submission #783078

#TimeUsernameProblemLanguageResultExecution timeMemory
783078andecaandeciStrange Device (APIO19_strange_device)C++17
0 / 100
411 ms17096 KiB
#include<bits/stdc++.h> using namespace std; #define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define int long long #define pii pair<int, int> #define fi first #define se second #define pb push_back int n, a, b; vector<pii> range; bool comp(pii a, pii b) { return (a.fi < b.fi || (a.fi == b.fi && a.se < b.se)); } signed main() { ioss; // cari cycle (bisa manual, baru cari pola) // --- a*b / fpb(a, b+1) // hitung segment aktif // line sweep cin >> n >> a >> b; __int128_t cycle = (__int128_t)a*b/(__gcd(a, (b+1))); for(int i = 0; i < n; i++) { int l, r; cin >> l >> r; l %= cycle, r %= cycle; if(l <= r) range.pb({l, r}); else range.pb({l, cycle-1}), range.pb({0, r}); } sort(range.begin(), range.end(), comp); auto [l, r] = range[0]; int ans = (r-l)+1; for(int i = 1; i < range.size(); i++) { auto [pl, pr] = range[i-1]; auto [l, r] = range[i]; if(pl <= l && pr >= r) continue; if(pl <= r && pr >= r) r = pl-1; if(pl <= l && pr >= l) l = pr+1; //cout << l << " " << r << endl; ans += (r-l)+1; } cout << ans << endl; }

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 1; i < range.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...