제출 #1197970

#제출 시각아이디문제언어결과실행 시간메모리
1197970JooDdaeWorst Reporter 2 (JOI16_worst_reporter2)C++20
0 / 100
5 ms9792 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using Node = array<int, 2>; #define mid ((l+r) >> 1) const int INF = 1e9; int n, a[200200], b[200200], c[200200], d[200200], p[200200], chk[200200]; map<int, int> mp[200200]; int lz[800800]; Node t[800800]; Node build(int node = 1, int l = 1, int r = n) { if(l == r) return t[node] = {p[l]-l+1, l}; return t[node] = min(build(node*2, l, mid), build(node*2+1, mid+1, r)); } void lazy_update(int node, int l, int r) { if(lz[node]) { t[node][0] += lz[node]; if(l != r) lz[node*2] += lz[node], lz[node*2+1] += lz[node]; lz[node] = 0; } } void update(int nl, int nr, int val, int node = 1, int l = 1, int r = n) { lazy_update(node, l, r); if(nr < l || r < nl) return; if(nl <= l && r <= nr) { lz[node] += val; lazy_update(node, l, r); return; } update(nl, nr, val, node*2, l, mid), update(nl, nr, val, node*2+1, mid+1, r); t[node] = min(t[node*2], t[node*2+1]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for(int i=1;i<=n;i++) cin >> a[i] >> b[i]; for(int i=1;i<=n;i++) cin >> c[i] >> d[i]; for(int i=1;i<=n;i++) { p[i] = p[i-1]; while(p[i] < n && d[p[i]+1] >= b[i]) p[i]++; mp[c[i]][d[i]] = i; } build(); int ans = 0; for(int i=1, j=1;i<=n;i++) { auto it = mp[a[i]].lower_bound(b[i]); if(it == mp[a[i]].end()) continue; auto id = upper_bound(p+1, p+1+n, it->second) - p; chk[it->second] = 1, mp[a[i]].erase(it), ans++; update(i, i, INF), update(i+1, n, 1); update(1, id-1, -1); while(t[1][0] == 1) { int u = t[1][1]; update(u, u, INF), update(u+1, n, 1); while(chk[j]) j++; chk[j] = 1, mp[c[j]].erase(d[j]); id = upper_bound(p+1, p+1+n, j) - p; update(1, id-1, INF); } } cout << n-ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...