oj.uz

Submission #469188

# Submission time Handle Problem Language Result Execution time Memory
469188 2021-08-31T05:49:54 Z Millad LIS (INOI20_lis) C++14
20 / 100
 4000 ms 123188 KB 
/// In the name of god
#include <bits/stdc++.h>
     
#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
     
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
     
const ll maxn = 1e6 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll q, x[maxn], p[maxn], b[maxn], ind[maxn], seg[maxn * 4], dp[maxn], lis;
set <ll> A[maxn], B[maxn];
vector <ll> Qu;
ll get_ind(ll id, ll ps = 0, ll v = 1, ll s = 0, ll e = q){
	if(e - s == 1){
		seg[v] = 1;
		return s;
	}
	ll mid = (e + s) >> 1, lc = v << 1, rc = lc | 1, ind;
	if(ps + (mid - s) - seg[lc] < id)ind = get_ind(id, ps + (mid - s) - seg[lc], rc, mid, e);
	else ind = get_ind(id, ps, lc, s, mid);
	seg[v] = seg[lc] + seg[rc];
	return ind;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> q;
	for(ll i = 0; i < q; i ++)cin >> p[i] >> x[i];
	for(ll i = q - 1; i >= 0; i --){
		ind[i] = get_ind(p[i]);
		b[ind[i]] = x[i];
	}
	for(ll i = 0; i < q; i ++){
		ll id = ind[i], d = 1;
		A[x[i]].insert(id);;
		for(ll j = 1; j < x[i]; j ++){
			if(A[j].empty())continue;
			if(*A[j].begin() > id)continue;
			if(*A[j].rbegin() < id){
				d = max(d, dp[*A[j].rbegin()] + 1);
			      	continue;	
			}
			auto pnt = A[j].upper_bound(id);
			pnt --; d = max(d, dp[*pnt] + 1);
		}
		dp[id] = d; B[d].insert(id);
		Qu.pb(id); lis = max(lis, d);
		while(Qu.size()){
			ll id2 = Qu.back(); Qu.pop_back();
			auto pnt = B[dp[id2]].lower_bound(id2);
			vector <ll> vec;
			while(true){
				pnt ++;
				if(pnt == B[dp[id2]].end())break;
				if(b[*pnt] < b[id2])break;
				if(b[*pnt] == b[id2])continue;
				vec.pb(*pnt);
			}
			for(ll j : vec){
				B[dp[j]].erase(j);
				dp[j] ++; lis = max(lis, dp[j]);
				B[dp[j]].insert(j); Qu.pb(j); 
			}
		}
		cout << lis << '\n';
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94232 KB Output is correct
2 Correct 73 ms 94272 KB Output is correct
3 Correct 59 ms 94532 KB Output is correct
4 Correct 59 ms 94568 KB Output is correct
5 Correct 112 ms 94608 KB Output is correct
6 Correct 66 ms 94532 KB Output is correct
7 Correct 73 ms 94472 KB Output is correct
8 Correct 63 ms 94536 KB Output is correct
9 Correct 68 ms 94528 KB Output is correct
10 Correct 71 ms 94580 KB Output is correct
11 Correct 66 ms 94560 KB Output is correct
12 Correct 68 ms 94528 KB Output is correct
13 Correct 70 ms 94516 KB Output is correct
14 Correct 60 ms 94484 KB Output is correct
15 Correct 67 ms 94556 KB Output is correct
16 Correct 63 ms 94468 KB Output is correct
17 Correct 70 ms 94528 KB Output is correct
18 Correct 81 ms 94528 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94232 KB Output is correct
2 Correct 73 ms 94272 KB Output is correct
3 Correct 59 ms 94532 KB Output is correct
4 Correct 59 ms 94568 KB Output is correct
5 Correct 112 ms 94608 KB Output is correct
6 Correct 66 ms 94532 KB Output is correct
7 Correct 73 ms 94472 KB Output is correct
8 Correct 63 ms 94536 KB Output is correct
9 Correct 68 ms 94528 KB Output is correct
10 Correct 71 ms 94580 KB Output is correct
11 Correct 66 ms 94560 KB Output is correct
12 Correct 68 ms 94528 KB Output is correct
13 Correct 70 ms 94516 KB Output is correct
14 Correct 60 ms 94484 KB Output is correct
15 Correct 67 ms 94556 KB Output is correct
16 Correct 63 ms 94468 KB Output is correct
17 Correct 70 ms 94528 KB Output is correct
18 Correct 81 ms 94528 KB Output is correct
19 Correct 246 ms 122932 KB Output is correct
20 Correct 307 ms 123188 KB Output is correct
21 Execution timed out 4043 ms 107068 KB Time limit exceeded
22 Halted 0 ms 0 KB -