Submission #61822105


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
static const int MAXD = 700010;
struct Segment {
long long start, end;
long long val;
};
void applyContest(int L, int R, vector<Segment> &segs) {
vector<Segment> newSegs;
newSegs.reserve(segs.size() + 2);
for (auto &sg : segs) {
long long s = sg.start, e = sg.end, v = sg.val;
if (s >= e) continue;
long long A = (long long)L - v;
long long B = (long long)R + 1 - v;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <bits/stdc++.h>
using namespace std;


static const int MAXD = 700010;

struct Segment {
    long long start, end;
    long long val;
};

void applyContest(int L, int R, vector<Segment> &segs) {
    vector<Segment> newSegs;
    newSegs.reserve(segs.size() + 2);

    for (auto &sg : segs) {
        long long s = sg.start, e = sg.end, v = sg.val;
        if (s >= e) continue;
        long long A = (long long)L - v;
        long long B = (long long)R + 1 - v;

        long long leftEnd = std::min(e, A);
        if (leftEnd > s) {
            newSegs.push_back({s, leftEnd, v});
        }

        long long midStart = std::max(s, A);
        long long midEnd   = std::min(e, B);
        if (midEnd > midStart) {
            newSegs.push_back({midStart, midEnd, v + 1});
        }

        long long rightStart = std::max(s, B);
        if (rightStart < e) {
            newSegs.push_back({rightStart, e, v});
        }
    }

    sort(newSegs.begin(), newSegs.end(), [](auto &a, auto &b){
        return a.start < b.start;
    });

    vector<Segment> merged;
    merged.reserve(newSegs.size());
    for (auto &sg : newSegs) {
        if (!merged.empty()) {
            auto &back = merged.back();
            if (back.end == sg.start && back.val == sg.val) {
                back.end = sg.end;
                continue;
            }
        }
        merged.push_back(sg);
    }

    segs.swap(merged);
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int,int>> intervals(N);
    for(int i=0; i<N; i++){
        cin >> intervals[i].first >> intervals[i].second;
    }

    vector<Segment> segs;
    segs.push_back({0, MAXD, 0});

    for(int i=0; i<N; i++){
        auto [L, R] = intervals[i];
        applyContest(L, R, segs);
    }

    int Q; cin >> Q;

    while(Q--){
        long long X; 
        cin >> X;
        int low = 0, high = (int)segs.size() - 1;
        long long cVal = 0;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (segs[mid].start <= X && X < segs[mid].end) {
                cVal = segs[mid].val;
                break;
            }
            if (X < segs[mid].start) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        cout << (X + cVal) << "\n";
    }

    return 0;
}

Submission Info

Submission Time
Task F - Rated Range
User caomeinaixi
Language C++ 20 (gcc 12.2)
Score 0
Code Size 2484 Byte
Status TLE
Exec Time 2759 ms
Memory 7320 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 525
Status
AC × 3
AC × 13
TLE × 23
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3368 KB
00_sample_01.txt AC 1 ms 3516 KB
00_sample_02.txt AC 1 ms 3528 KB
01_test_00.txt AC 6 ms 3656 KB
01_test_01.txt AC 7 ms 3652 KB
01_test_02.txt AC 4 ms 3648 KB
01_test_03.txt AC 1 ms 3488 KB
01_test_04.txt TLE 2759 ms 6236 KB
01_test_05.txt TLE 2759 ms 7268 KB
01_test_06.txt TLE 2759 ms 7080 KB
01_test_07.txt TLE 2759 ms 7280 KB
01_test_08.txt TLE 2759 ms 7220 KB
01_test_09.txt TLE 2759 ms 7152 KB
01_test_10.txt TLE 2759 ms 6188 KB
01_test_11.txt TLE 2759 ms 7260 KB
01_test_12.txt TLE 2759 ms 6372 KB
01_test_13.txt TLE 2759 ms 7288 KB
01_test_14.txt TLE 2759 ms 6780 KB
01_test_15.txt TLE 2759 ms 7248 KB
01_test_16.txt TLE 2759 ms 5672 KB
01_test_17.txt TLE 2759 ms 7248 KB
01_test_18.txt TLE 2759 ms 6904 KB
01_test_19.txt TLE 2759 ms 7288 KB
01_test_20.txt TLE 2759 ms 6596 KB
01_test_21.txt TLE 2759 ms 6616 KB
01_test_22.txt TLE 2759 ms 6428 KB
01_test_23.txt AC 53 ms 4640 KB
01_test_24.txt TLE 2759 ms 7164 KB
01_test_25.txt TLE 2759 ms 7320 KB
01_test_26.txt TLE 2759 ms 7228 KB
01_test_27.txt TLE 2759 ms 7164 KB
01_test_28.txt AC 1 ms 3636 KB
01_test_29.txt AC 1 ms 3508 KB
01_test_30.txt AC 1 ms 3516 KB
01_test_31.txt AC 1 ms 3488 KB
01_test_32.txt AC 2 ms 3404 KB


2025-03-01 (Sat)
00:46:04 +00:00