This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
BIT ft;
ft.init(n);
for (int i = n - 1; i >= 0; i--)
{
int l = 1, r = n;
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |