Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: Punnawith

Problemset: ห้องสมุดเมือง 3M

Language: cpp

Time: 0.015 second

Submitted On: 2025-03-23 09:03:28

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// Comparator to sort events first by time, then by type (start event first if same time)
bool compareEvents(pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;  // Sort by time
    }
    return a.second < b.second;  // If times are equal, process start events (+1) before end events (-1)
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;  // Number of intervals

    // Create an array of events (start and end of intervals)
    vector<pair<int, int>> events(2 * n);

    int u, v;
    int totalLength = 0;  // Total length of all intervals

    // Read all intervals and create corresponding events
    for (int i = 0; i < 2 * n; i += 2) {
        cin >> u >> v;
        
        // Start event at 'u' (marked with +1)
        events[i].first = u;
        events[i].second = 1;

        // End event at 'v' (marked with -1)
        events[i + 1].first = v;
        events[i + 1].second = -1;

        // Add the length of the current interval to the total length
        totalLength += (v - u);
    }

    // Sort the events based on time (and type of event for tie-breaking)
    sort(events.begin(), events.end(), compareEvents);

    int activeIntervals = 0;  // To keep track of the number of active intervals
    int eventIndex = 0;  // Pointer to process the events
    int accumulatedOverlap = 0;  // The running total of accumulated overlap
    int halfTotalLength = totalLength / 2;  // The target overlap to reach

    // Process all events in sorted order
    while (true) {
        int currentTime = events[eventIndex].first;
        int startTime = currentTime;

        // Process all events that happen at the current time
        while (eventIndex < 2 * n && events[eventIndex].first == currentTime) {
            activeIntervals += events[eventIndex].second;  // Update the active intervals count
            eventIndex++;
        }

        // For each time step, update the accumulated overlap and check if it reaches the target
        while (startTime < events[eventIndex].first) {
            startTime++;  // Increment time by 1 unit
            accumulatedOverlap += activeIntervals;  // Add active intervals to the accumulated overlap

            // If accumulated overlap has reached or exceeded half of the total length, print the current time
            if (accumulatedOverlap >= halfTotalLength) {
                cout << startTime - 1;  // Print the time just before the overlap threshold is exceeded
                return 0;
            }
        }
    }

    return 0;
}