Submission #862552

#TimeUsernameProblemLanguageResultExecution timeMemory
862552Mizo_CompilerOsumnjičeni (COCI21_osumnjiceni)C++17
0 / 110
648 ms173172 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; #define pb push_back #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define F first #define S second const int N = 2e5+5; int n, mx[(1 << 19)], a[N]; struct node { int ls, ans; }; vector<node> t((1 << 19)); multiset<int, greater<>> val[N+N]; void mxupd(int l, int r, int x, int i, int v) { if (l == r) { mx[x] = v; return; } int m = (l + r) >> 1; if (i <= m)mxupd(l, m, x*2+1, i, v); else mxupd(m+1, r, x*2+2, i, v); mx[x] = max(mx[x*2+1], mx[x*2+2]); } int mxget(int li, int ri, int x, int l, int r) { if (li > r || ri < l)return 0; if (li >= l && ri <= r)return mx[x]; int m = (li + ri) >> 1; return max(mxget(li, m, x*2+1, l, r), mxget(m+1, ri, x*2+2, l, r)); } node nd; node merge(node x, node y, int ly) { return { (y.ls == ly && a[x.ls] >= ly ? x.ls : y.ls), x.ans + y.ans - (y.ls == ly && a[x.ls] >= ly ? 1 : 0) }; } void build(int li, int ri, int x) { if (li == ri) { t[x].ans = 1; t[x].ls = li; return; } int m = (li + ri) >> 1; build(li, m, x*2+1); build(m+1, ri, x*2+2); t[x] = merge(t[x*2+1], t[x*2+2], m+1); } void get(int li, int ri, int x, int l, int r) { if (li > r || ri < l)return; if (li >= l && ri <= r) { nd = merge(nd, t[x], li); return; } int m = (li + ri) >> 1; get(li, m, x*2+1, l, r); get(m+1, ri, x*2+2, l, r); } int l[N], r[N]; int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; set<int> st; for (int i = 1; i <= n; i++) { cin >> l[i] >> r[i]; val[i].insert(0); val[n+i].insert(0); st.insert(l[i]), st.insert(r[i]); } int cur = 1; map<int, int> mp; for (auto &x : st) { mp[x] = cur++; } for (int i = 1; i <= n; i++) { l[i] = mp[l[i]], r[i] = mp[r[i]]; } int cr = n; a[n] = n; val[l[n]].insert(r[n]); mxupd(1, 2*n, 0, l[n], r[n]); for (int cl = n-1; cl >= 1; cl--) { while (mxget(1, 2*n, 0, 1, r[cl]) >= l[cl]) { val[l[cr]].erase(val[l[cr]].find(r[cr])); mxupd(1, 2*n, 0, l[cr], *val[l[cr]].begin()); cr--; } val[l[cl]].insert(r[cl]); mxupd(1, 2*n, 0, l[cl], *val[l[cl]].begin()); a[cl] = cr; } build(1, n, 0); int q; cin >> q; while (q--) { int a, b; cin >> a >> b; nd.ans = 0; nd.ls = -1; get(1, n, 0, a, b); cout << nd.ans << "\n"; } }
#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...