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