Submission #976808

#TimeUsernameProblemLanguageResultExecution timeMemory
976808AIF_is_carvingStrange Device (APIO19_strange_device)C++17
10 / 100
5061 ms135220 KiB
#include<bits/stdc++.h> typedef long long ll; using namespace std; vector<vector<ll>> overlappedInterval(vector<vector<ll>>& intervals) { if (intervals.empty()) { return vector<vector<ll>>(); } // Sort intervals based on start values sort(intervals.begin(), intervals.end(), [](const vector<ll>& a, const vector<ll>& b) { return a[0] < b[0]; }); stack<vector<ll>> mergedStack; mergedStack.push(intervals[0]); for (int i = 1; i < intervals.size(); i++) { vector<ll> current = intervals[i]; vector<ll>& top = mergedStack.top(); if (current[0] <= top[1]) { // If current interval overlaps with the top of the stack, merge them top[1] = max(top[1], current[1]); } else { // If no overlap, push the current interval onto the stack mergedStack.push(current); } } // Convert the stack to a vector vector<vector<ll>> mergedIntervals; while (!mergedStack.empty()) { mergedIntervals.insert(mergedIntervals.begin(), mergedStack.top()); mergedStack.pop(); } return mergedIntervals; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); set<pair<ll, ll>> s; ll n, A, B; cin>>n>>A>>B; ll period; ll X = A/(gcd(B+1, A)); int powX=0, powB=0; ll xxx = X; while(xxx>0){ xxx/=2; powX+=1; } xxx=B; while(xxx>0){ xxx/=2; powB+=1; } if(powB+powX>61) period=4e18; else period = B*X; //cout<<period<<"\n"; vector<vector<ll>> v; for(int i=0; i<n; i++){ ll x, y; cin>>x>>y; if(y-x<period){ ll XX = x%period; ll YY = y%period; if(XX<=YY) v.push_back({XX,YY}); else{ v.push_back({XX, period-1}); v.push_back({0, YY}); } } else{ v.push_back({0, period-1}); } } //for(auto p: v) cout<<p.first<<" "<<p.second<<"\n"; vector<vector<ll>> merged = overlappedInterval(v); ll ans =0; for(auto vv: merged){ ans += vv[1]-vv[0]+1; } cout<<ans<<"\n"; return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'std::vector<std::vector<long long int> > overlappedInterval(std::vector<std::vector<long long int> >&)':
strange_device.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 1; i < intervals.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...