Submission #933177

#TimeUsernameProblemLanguageResultExecution timeMemory
933177zhaohaikunInspections (NOI23_inspections)C++17
0 / 100
3 ms4696 KiB
// MagicDark #include <bits/stdc++.h> #define debug cerr << "[" << __LINE__ << "] " #define SZ(x) (int) x.size() - 1 #define all(x) x.begin(), x.end() #define ms(x, y) memset(x, y, sizeof x) #define F(i, x, y) for (int i = (x); i <= (y); i++) #define DF(i, x, y) for (int i = (x); i >= (y); i--) using namespace std; typedef long long ll; typedef unsigned long long ull; template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);} template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);} template <typename T> inline void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); x *= f; } const int N = 2e5 + 10, inf = 1e9; const ll INF = 1e18; int n, m, q, l[N], r[N]; ll sum; pair <ll, int> qq[N]; set <pair <pair <int, int>, ll>> s; auto split(int x) { // x - 1 x auto it = s.lower_bound(make_pair(make_pair(x, inf), 0)); if (it == s.begin()) return it; it--; if (it -> first.first < x && it -> first.second >= x) { auto g = *it; s.erase(it); s.emplace(make_pair(g.first.first, x - 1), g.second); return s.emplace(make_pair(x, g.first.second), g.second).first; } return it; } vector <pair <ll, int>> v; void dot(int x, ll y) { v.emplace_back(y, x); } void ins(int l, int r, ll g) { auto tr = split(r + 1), tl = split(l); // if (r != 6) { // debug << tl -> first.first << " " << tl -> first.second << endl; // debug << tr -> first.first << " " << tr -> first.second << endl; // } // for (auto [a, b]: s) debug << a.first << " " << a.second << " : " << b << endl; debug << endl; while (tl != tr) { // debug << tl -> first.first << " " << tl -> first.second << endl; dot(tl -> first.second - tl -> first.first + 1, g - tl -> second); tl = s.erase(tl); } s.emplace(make_pair(l, r), g); } int pos; ll e, ans[N]; signed main() { read(n), read(m), read(q); // s.emplace(make_pair(1, n), -INF); F(i, 1, m) { read(l[i]), read(r[i]); ins(l[i], r[i], sum - l[i] + 1); sum += r[i] - l[i] + 1; } F(i, 1, q) read(qq[i].first), qq[i].second = i; sort(qq + 1, qq + q + 1); sort(v.rbegin(), v.rend()); // for (auto [a, b]: v) cout << a << " " << b << endl; DF(i, q, 1) { while (pos <= SZ(v) && v[pos].first > qq[i].first) { e += v[pos].second; pos++; } // debug << qq[i].first << " " << e << endl; ans[qq[i].second] = e; } F(i, 1, q) cout << ans[i] << ' '; return 0; } /* why? */
#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...