oj.uz

Submission #784174

# Submission time Handle Problem Language Result Execution time Memory
784174 2023-07-15T20:24:48 Z MISM06 LIS (INOI20_lis) C++17
20 / 100
 4000 ms 607792 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 123 ms 313420 KB Output is correct
2 Correct 122 ms 313448 KB Output is correct
3 Correct 139 ms 315676 KB Output is correct
4 Correct 143 ms 315736 KB Output is correct
5 Correct 269 ms 315736 KB Output is correct
6 Correct 221 ms 315836 KB Output is correct
7 Correct 172 ms 315624 KB Output is correct
8 Correct 167 ms 315824 KB Output is correct
9 Correct 170 ms 315676 KB Output is correct
10 Correct 160 ms 315676 KB Output is correct
11 Correct 173 ms 315676 KB Output is correct
12 Correct 150 ms 315724 KB Output is correct
13 Correct 169 ms 315608 KB Output is correct
14 Correct 169 ms 315696 KB Output is correct
15 Correct 178 ms 315680 KB Output is correct
16 Correct 162 ms 315616 KB Output is correct
17 Correct 170 ms 315624 KB Output is correct
18 Correct 163 ms 315712 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 313420 KB Output is correct
2 Correct 122 ms 313448 KB Output is correct
3 Correct 139 ms 315676 KB Output is correct
4 Correct 143 ms 315736 KB Output is correct
5 Correct 269 ms 315736 KB Output is correct
6 Correct 221 ms 315836 KB Output is correct
7 Correct 172 ms 315624 KB Output is correct
8 Correct 167 ms 315824 KB Output is correct
9 Correct 170 ms 315676 KB Output is correct
10 Correct 160 ms 315676 KB Output is correct
11 Correct 173 ms 315676 KB Output is correct
12 Correct 150 ms 315724 KB Output is correct
13 Correct 169 ms 315608 KB Output is correct
14 Correct 169 ms 315696 KB Output is correct
15 Correct 178 ms 315680 KB Output is correct
16 Correct 162 ms 315616 KB Output is correct
17 Correct 170 ms 315624 KB Output is correct
18 Correct 163 ms 315712 KB Output is correct
19 Correct 1255 ms 607412 KB Output is correct
20 Correct 1639 ms 606976 KB Output is correct
21 Execution timed out 4002 ms 607792 KB Time limit exceeded
22 Halted 0 ms 0 KB -