Submission #866780

#TimeUsernameProblemLanguageResultExecution timeMemory
866780sleepntsheepOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
242 ms9168 KiB
#include <iostream> #include <vector> #include <algorithm> #include <deque> #include <set> #include <utility> #include <array> using namespace std; #define ALL(x) x.begin(), x.end() using ll = long long; #define N 200005 int n, q, t[N<<2], lz[N<<2]; pair<int, int> a[N]; void push(int v, int l, int r) { if (lz[v]) { t[v] += lz[v]; if (l != r) { int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; lz[vl]+=lz[v],lz[vr]+=lz[v]; } lz[v] = 0; } } void update(int v, int l, int r, int x, int y, int k) { push(v, l, r); if (r < x || y < l) return; if (x <= l && r <= y) { lz[v] += k; push(v, l, r); return; } int m = (l+r)/2, vl=v+1, vr=v+(m-l+1)*2; update(vl, l, m, x, y, k), update(vr, m+1, r, x, y, k); t[v] = max(t[vl], t[vr]); } void update(int x, int y, int k) { update(0, 0, 2*n, x, y, k); } void compress() { vector<int> C; C.reserve(2*n); for (int i = 0; i < n; ++i) C.push_back(a[i].first), C.push_back(a[i].second); sort(ALL(C)); for (int i = 0; i < n; ++i) a[i].first = lower_bound(ALL(C), a[i].first) - C.begin(), a[i].second = lower_bound(ALL(C), a[i].second) - C.begin(); } struct qry { int l, r, i; bool operator<(const qry &o) { if (l/400 != o.l/400) return l<o.l; if (r != o.r) return r<o.r; return i<o.i; } } b[N]; int ans[N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second; compress(); cin >> q; for (int i = 0; i < 1; ++i) { int L, R; cin >> L>>R; for (int j=0;j<n;++j) update(a[j].first,a[j].second,1); push(0,0,2*n); cout<<t[0]; return 0; } for (int i = 0; i < q; ++i) cin >> b[i].l >> b[i].r, --b[i].l, --b[i].r, b[i].i = i; sort(b, b+q); int l = b[0].l, r = b[0].l-1; for (int i = 0; i < q; ++i) { auto [L, R, j] = b[i]; while (l > L) --l, update(a[l].first, a[l].second, 1); while (r < R) ++r, update(a[r].first, a[r].second, 1); while (l < L) update(a[l].first, a[l].second, -1), ++l; while (r > R) update(a[r].first, a[r].second, -1), --r; push(0, 0, 2*n); ans[j] = t[0]; } for (int i = 0; i < q; ++i) cout << ans[i] << '\n'; return 0; }
#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...