oj.uz

Submission #784175

# Submission time Handle Problem Language Result Execution time Memory
784175 2023-07-15T20:25:30 Z MISM06 LIS (INOI20_lis) C++14
20 / 100
 4000 ms 607816 KB 
//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], 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, plc[tl]};
		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].F = 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));
	}
	pii 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));
	}
	pii less_max (int bound, int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (l > r) return {0, 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, 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).F + 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;

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 313432 KB Output is correct
2 Correct 124 ms 313540 KB Output is correct
3 Correct 136 ms 315836 KB Output is correct
4 Correct 133 ms 315680 KB Output is correct
5 Correct 266 ms 315652 KB Output is correct
6 Correct 202 ms 315724 KB Output is correct
7 Correct 167 ms 315692 KB Output is correct
8 Correct 164 ms 315736 KB Output is correct
9 Correct 175 ms 315724 KB Output is correct
10 Correct 158 ms 315632 KB Output is correct
11 Correct 174 ms 315684 KB Output is correct
12 Correct 150 ms 315688 KB Output is correct
13 Correct 166 ms 315724 KB Output is correct
14 Correct 174 ms 315816 KB Output is correct
15 Correct 154 ms 315676 KB Output is correct
16 Correct 164 ms 315616 KB Output is correct
17 Correct 169 ms 315640 KB Output is correct
18 Correct 168 ms 315896 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 313432 KB Output is correct
2 Correct 124 ms 313540 KB Output is correct
3 Correct 136 ms 315836 KB Output is correct
4 Correct 133 ms 315680 KB Output is correct
5 Correct 266 ms 315652 KB Output is correct
6 Correct 202 ms 315724 KB Output is correct
7 Correct 167 ms 315692 KB Output is correct
8 Correct 164 ms 315736 KB Output is correct
9 Correct 175 ms 315724 KB Output is correct
10 Correct 158 ms 315632 KB Output is correct
11 Correct 174 ms 315684 KB Output is correct
12 Correct 150 ms 315688 KB Output is correct
13 Correct 166 ms 315724 KB Output is correct
14 Correct 174 ms 315816 KB Output is correct
15 Correct 154 ms 315676 KB Output is correct
16 Correct 164 ms 315616 KB Output is correct
17 Correct 169 ms 315640 KB Output is correct
18 Correct 168 ms 315896 KB Output is correct
19 Correct 1278 ms 607468 KB Output is correct
20 Correct 1601 ms 607024 KB Output is correct
21 Correct 3919 ms 607816 KB Output is correct
22 Execution timed out 4070 ms 607672 KB Time limit exceeded
23 Halted 0 ms 0 KB -