제출 #976817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976817		AIF_is_carving	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	427 ms	60240 KiB

strange_device

#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;
// }

struct Interval {
    ll s, e;
};

// Function used in sort
bool mycomp(Interval a, Interval b) { return a.s < b.s; }

void mergeIntervals(Interval arr[], ll n)
{
    // Sort Intervals in increasing order of
    // start time
    sort(arr, arr + n, mycomp);

    ll index = 0; // Stores index of last element
    // in output array (modified arr[])

    // Traverse all input Intervals
    for (ll i = 1; i < n; i++) {
        // If this is not first Interval and overlaps
        // with the previous one
        if (arr[index].e >= arr[i].s) {
            // Merge previous and current Intervals
            arr[index].e = max(arr[index].e, arr[i].e);
        }
        else {
            index++;
            arr[index] = arr[i];
        }
    }

    // Now arr[0..index-1] stores the merged Intervals
    //cout << "\n The Merged Intervals are: ";
    ll ans =0;
    for (ll i = 0; i <= index; i++) ans+= arr[i].e-arr[i].s+1;

        cout<<ans<<"\n";
        //cout << "[" << arr[i].s << ", " << arr[i].e << "] ";
}

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<pair<ll, 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});
        }
    }

    Interval arr[int(v.size())];
    for(int i=0; i<int(v.size()); i++){
        arr[i].s = v[i].first;
        arr[i].e = v[i].second;
    }
    //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";

    mergeIntervals(arr, int(v.size()));

    return 0;
}
 

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30