oj.uz

Submission #784172

# Submission time Handle Problem Language Result Execution time Memory
784172 2023-07-15T20:22:08 Z MISM06 LIS (INOI20_lis) C++14
20 / 100
 4000 ms 608336 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 + 10;
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], DP[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;
		vector < pii > q;
		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 147 ms 313412 KB Output is correct
2 Correct 127 ms 313464 KB Output is correct
3 Correct 133 ms 315712 KB Output is correct
4 Correct 140 ms 315768 KB Output is correct
5 Correct 268 ms 315740 KB Output is correct
6 Correct 225 ms 315724 KB Output is correct
7 Correct 171 ms 315688 KB Output is correct
8 Correct 163 ms 315724 KB Output is correct
9 Correct 170 ms 315676 KB Output is correct
10 Correct 154 ms 315752 KB Output is correct
11 Correct 189 ms 315760 KB Output is correct
12 Correct 149 ms 315708 KB Output is correct
13 Correct 174 ms 315632 KB Output is correct
14 Correct 168 ms 315844 KB Output is correct
15 Correct 156 ms 315712 KB Output is correct
16 Correct 162 ms 315684 KB Output is correct
17 Correct 169 ms 315752 KB Output is correct
18 Correct 160 ms 315664 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 313412 KB Output is correct
2 Correct 127 ms 313464 KB Output is correct
3 Correct 133 ms 315712 KB Output is correct
4 Correct 140 ms 315768 KB Output is correct
5 Correct 268 ms 315740 KB Output is correct
6 Correct 225 ms 315724 KB Output is correct
7 Correct 171 ms 315688 KB Output is correct
8 Correct 163 ms 315724 KB Output is correct
9 Correct 170 ms 315676 KB Output is correct
10 Correct 154 ms 315752 KB Output is correct
11 Correct 189 ms 315760 KB Output is correct
12 Correct 149 ms 315708 KB Output is correct
13 Correct 174 ms 315632 KB Output is correct
14 Correct 168 ms 315844 KB Output is correct
15 Correct 156 ms 315712 KB Output is correct
16 Correct 162 ms 315684 KB Output is correct
17 Correct 169 ms 315752 KB Output is correct
18 Correct 160 ms 315664 KB Output is correct
19 Correct 1331 ms 607444 KB Output is correct
20 Correct 1566 ms 606932 KB Output is correct
21 Correct 3945 ms 607740 KB Output is correct
22 Execution timed out 4083 ms 608336 KB Time limit exceeded
23 Halted 0 ms 0 KB -