Submission #785891

#TimeUsernameProblemLanguageResultExecution timeMemory
785891MISM06LIS (INOI20_lis)C++17
100 / 100
2182 ms159920 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; set < int > s[N]; 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; void calc (int o, int h) { ans = max(ans, h); s[h].insert(o); auto it = s[h].upper_bound(o); while(it != s[h].end()) { int oo = *it; if (b[oo] <= b[o]) break; s[h].erase(it); calc(oo, h + 1); it = s[h].upper_bound(o); } } 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); } for (int i = 1; i <= n; i++) { int o = ord[i]; int x = a[i]; int h = 0; for (int j = 1; j < a[i]; j++) { auto it = s[j].lower_bound(o); if (it == s[j].begin() || s[j].sze == 0) continue; --it; int oo = *it; if (b[oo] >= x) continue; else h = j; } ++h; 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...