oj.uz

Submission #784176

# Submission time Handle Problem Language Result Execution time Memory
784176 2023-07-15T20:30:35 Z MISM06 LIS (INOI20_lis) C++14
20 / 100
 4000 ms 549152 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];
	vector < int > 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;
		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] = 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));
	}
	int 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));
	}
	int less_max (int bound, int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (l > r) return 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;
		} 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) + 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 141 ms 313440 KB Output is correct
2 Correct 125 ms 313464 KB Output is correct
3 Correct 130 ms 315204 KB Output is correct
4 Correct 149 ms 315236 KB Output is correct
5 Correct 254 ms 315300 KB Output is correct
6 Correct 195 ms 315224 KB Output is correct
7 Correct 169 ms 315304 KB Output is correct
8 Correct 163 ms 315220 KB Output is correct
9 Correct 170 ms 315236 KB Output is correct
10 Correct 155 ms 315300 KB Output is correct
11 Correct 175 ms 315304 KB Output is correct
12 Correct 148 ms 315180 KB Output is correct
13 Correct 166 ms 315280 KB Output is correct
14 Correct 175 ms 315288 KB Output is correct
15 Correct 162 ms 315292 KB Output is correct
16 Correct 163 ms 315212 KB Output is correct
17 Correct 166 ms 315296 KB Output is correct
18 Correct 162 ms 315412 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 313440 KB Output is correct
2 Correct 125 ms 313464 KB Output is correct
3 Correct 130 ms 315204 KB Output is correct
4 Correct 149 ms 315236 KB Output is correct
5 Correct 254 ms 315300 KB Output is correct
6 Correct 195 ms 315224 KB Output is correct
7 Correct 169 ms 315304 KB Output is correct
8 Correct 163 ms 315220 KB Output is correct
9 Correct 170 ms 315236 KB Output is correct
10 Correct 155 ms 315300 KB Output is correct
11 Correct 175 ms 315304 KB Output is correct
12 Correct 148 ms 315180 KB Output is correct
13 Correct 166 ms 315280 KB Output is correct
14 Correct 175 ms 315288 KB Output is correct
15 Correct 162 ms 315292 KB Output is correct
16 Correct 163 ms 315212 KB Output is correct
17 Correct 166 ms 315296 KB Output is correct
18 Correct 162 ms 315412 KB Output is correct
19 Correct 1220 ms 548956 KB Output is correct
20 Correct 1482 ms 548732 KB Output is correct
21 Correct 3682 ms 549152 KB Output is correct
22 Execution timed out 4078 ms 549044 KB Time limit exceeded
23 Halted 0 ms 0 KB -