Submission #999533

#TimeUsernameProblemLanguageResultExecution timeMemory
999533vjudge1LIS (INOI20_lis)C++17
0 / 100
12 ms50780 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F struct DSU { vector<int> e; void init(int n) { e.assign(n + 1, -1); } int get(int x) { if (e[x] < 0) return x; return e[x] = get(e[x]); } void unite(int x, int y) { x = get(x), y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; struct BIT { int n; vector<int> ft; void init(int N) { n = N + 5; ft.assign(n + 5, 0); } void add(int pos, int val) { for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val; } int get(int pos, int res = 0) { for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos]; return res; } }; const int MXN = 1e6 + 5; set<int> st[MXN]; int res[MXN], v[MXN]; int ans = 0; void add(int i) { ans = max(ans, res[i]); auto it = st[res[i]].begin(); while ((it = st[res[i]].upper_bound(i)) != st[res[i]].end() && v[*it] > v[i]) { int x = *it; st[res[i]].erase(it); res[x] = res[i] + 1; add(x); } st[res[i]].insert(i); } signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; array<int, 2> a[n]; for (array<int, 2> &i : a) cin >> i[0] >> i[1], i[0]--; BIT ft; ft.init(n); for (int i = n - 1; i >= 0; i--) { int l = 0, r = n - 1; while (l < r) { int mid = (l + r) >> 1; if (mid - ft.get(mid) >= a[i][0]) r = mid; else l = mid + 1; } a[i][0] = l; v[l] = a[i][1]; ft.add(l, 1); } for (array<int, 2> &i : a) { res[i[0]] = 1; for (int j = 1; j < i[1]; j++) { auto it = st[j].lower_bound(i[0]); if (!(it == st[j].begin() || v[*prev(it)] > i[1])) res[i[0]] = j + 1; } add(i[0]); cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...