Submission #784176

#TimeUsernameProblemLanguageResultExecution timeMemory
784176MISM06LIS (INOI20_lis)C++14
20 / 100
4078 ms549152 KiB
//0 1 1 0 1 //0 1 0 0 1 //1 0 0 1 1 //0 1 1 0 1 #include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2") using namespace std; #define F first #define S second #define pb push_back #define sze size() #define all(x) x.begin() , x.end() #define wall__ cout << "--------------------------------------\n"; #define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1 #define kid1 int mid = (tl + tr) >> 1, cl = v1 << 1, cr = v1 << 1 | 1 #define kid2 int mid = (tl + tr) >> 1, cl = v2 << 1, cr = v2 << 1 | 1 #define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout); typedef long long ll; typedef long double dl; typedef pair < int , int > pii; typedef pair < int , ll > pil; typedef pair < ll , int > pli; typedef pair < ll , ll > pll; typedef pair < int , pii > piii; typedef pair < ll, pll > plll; const ll N = 1e6 + 5; const ll mod = 1e9 + 7; const ll inf = 2e16; const ll INF = 1e9 + 10; const ll lg = 32; int n, a[N], p[N], ord[N], b[N], ans = 0; struct segtree1 { pii seg[N << 2]; int la[N << 2]; void build (int v = 1, int tl = 1, int tr = n) { la[v] = 0; if (tl == tr) { seg[v] = {p[tl], -tl}; return; } kids; build(cl, tl, mid); build(cr, mid + 1, tr); seg[v] = min(seg[cl], seg[cr]); } void shift (int v, int tl, int tr) { seg[v].F += la[v]; if (tl != tr) { la[v << 1] += la[v]; la[v << 1 | 1] += la[v]; } la[v] = 0; } void upd (int val, int l, int r, int v = 1, int tl = 1 , int tr = n) { shift(v, tl, tr); if (l > r) return; if (l == tl && r == tr) { la[v] += val; shift(v, tl, tr); return; } kids; upd(val, l, min(r, mid), cl, tl, mid); upd(val, max(l, mid + 1), r, cr, mid + 1, tr); seg[v] = min(seg[cl], seg[cr]); } int ask () { shift(1, 1, n); return -seg[1].S; } } place; struct segtree2 { vector < pii > vec[N << 2]; vector < pii > mn[N << 2]; vector < int > mx[N << 2]; int plc[N]; void build2 (int s, int v1, int v2, int tl, int tr) { mn[v1][v2] = {INF, plc[tl]}; mx[v1][v2] = 0; if (tl == tr) return; kid2; build2(s, v1, cl, tl, mid); build2(s, v1, cr, mid + 1, tr); } void upd2 (int pos, int val, int v1, int v2, int tl, int tr) { if (tl == tr) { mx[v1][v2] = val; mn[v1][v2].F = val; return; } kid2; if (pos <= mid) upd2(pos, val, v1, cl, tl, mid); else upd2(pos, val, v1, cr, mid + 1, tr); mx[v1][v2] = max(mx[v1][cl], mx[v1][cr]); mn[v1][v2] = min(mn[v1][cl], mn[v1][cr]); } pii MIN2 (int v1, int l, int r, int v2, int tl, int tr) { if (l == tl && r == tr) return mn[v1][v2]; kid2; if (r <= mid) return MIN2(v1, l, r, cl, tl, mid); else if (l > mid) return MIN2(v1, l, r, cr, mid + 1, tr); else return min(MIN2(v1, l, mid, cl, tl, mid), MIN2(v1, mid + 1, r, cr, mid + 1, tr)); } int MAX2 (int v1, int l, int r, int v2, int tl, int tr) { if (l == tl && r == tr) return mx[v1][v2]; kid2; if (r <= mid) return MAX2(v1, l, r, cl, tl, mid); else if (l > mid) return MAX2(v1, l, r, cr, mid + 1, tr); else return max(MAX2(v1, l, mid, cl, tl, mid), MAX2(v1, mid + 1, r, cr, mid + 1, tr)); } void build (int v = 1, int tl = 1, int tr = n) { vec[v].pb({-1, -1}); for (int i = tl; i <= tr; i++) { vec[v].pb({b[i], i}); } sort(all(vec[v])); for (int i = 1; i <= tr - tl + 1; i++) plc[i] = vec[v][i].S; int len = tr - tl + 2; mn[v].resize((len << 2) + 1); mx[v].resize((len << 2) + 1); build2(tl - 1, v, 1, 1, tr - tl + 1); if (tl == tr) return; kids; build(cl, tl, mid); build(cr, mid + 1, tr); } void upd (int pos, int val, int v = 1, int tl = 1, int tr = n) { int i = lower_bound(all(vec[v]), make_pair(b[pos], pos)) - vec[v].begin(); upd2(i, val, v, 1, 1, tr - tl + 1); if (tl == tr) return; kids; if (pos <= mid) upd(pos, val, cl, tl, mid); else upd(pos, val, cr, mid + 1, tr); } pii then_min (int bound, int l, int r, int v = 1, int tl = 1, int tr = n) { if (l > r) return {INF, INF}; if (l == tl && r == tr) { if (vec[v].back().F < bound) return {INF, INF}; int i = lower_bound(all(vec[v]), make_pair(bound, 0)) - vec[v].begin(); return MIN2(v, i, tr - tl + 1, 1, 1, tr - tl + 1); } kids; return min(then_min(bound, l, min(r, mid), cl, tl, mid), then_min(bound, max(l, mid + 1), r, cr, mid + 1, tr)); } int less_max (int bound, int l, int r, int v = 1, int tl = 1, int tr = n) { if (l > r) return 0; if (l == tl && r == tr) { int i; if (vec[v].back().F <= bound) i = tr - tl + 2; else i = lower_bound(all(vec[v]), make_pair(bound + 1, 0)) - vec[v].begin(); --i; if (i) return MAX2(v, 1, i, 1, 1, tr - tl + 1); else return 0; } kids; return max(less_max(bound, l, min(r, mid), cl, tl, mid), less_max(bound, max(l, mid + 1), r, cr, mid + 1, tr)); } } sg; void calc (int o, int h) { // cout << o << " - " << h << '\n'; ans = max(ans, h); sg.upd(o, h); int x = b[o]; pii y = sg.then_min(x + 1, o + 1, n); // cout << y.F << " * " << y.S << '\n'; while(y.F == h) { calc(y.S, h + 1); y = sg.then_min(x + 1, o + 1, n); } } void solve () { cin >> n; for (int i = 1; i <= n; i++) cin >> p[i] >> a[i]; place.build(); for (int i = 1; i <= n; i++) { int it = place.ask(); b[i] = a[it]; ord[it] = i; place.upd(1, 1, it - 1); place.upd(INF, it, it); } sg.build(); for (int i = 1; i <= n; i++) { int o = ord[i], x = a[i]; int h = sg.less_max(x - 1, 1, o - 1) + 1; calc (o, h); cout << ans << '\n'; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) {solve();} return 0; } /* */ //shrek is love;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...