Submission #420064

#	Time	Username	Problem	Language	Result	Execution time	Memory
420064		oolimry	Financial Report (JOI21_financial)	C++17	100 / 100	1259 ms	150556 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

int arr[300005];
int block[300005];
int dp[300005];

const int N = (1<<19);
int SZ[2*N];
vector<ii> tree[2*N];

void init(){
	for(int i = N;i < 2*N;i++) SZ[i] = 1;
	for(int i = N-1;i > 0;i--) SZ[i] = SZ[i<<1]+SZ[i<<1|1];
}

void update(int i, ii x){
	i += N;
	while(i > 0){
		tree[i].push_back(x);
		if(sz(tree[i]) == SZ[i]){
			sort(all(tree[i]));
			vector<ii> temp;
			for(ii x : tree[i]){
				if(temp.empty()) temp.push_back(x);
				if(temp.back().second < x.second) temp.push_back(x);
			}
			swap(tree[i],temp);
			temp.clear();
		}
		i >>= 1;
	}
}

int get(vector<ii> &v, int x){
	auto it = lower_bound(all(v), ii(x,-1));
	if(it == v.begin()) return 0;
	it--;
	return it->second;
}

lint query(int l, int r, int X){
	int res = 0;
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res = max(res, get(tree[l++], X));
		if(r&1) res = max(res, get(tree[--r], X));
	}
	return res;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	init();
	int n, D;  cin >> n >> D;
	for(int i = 1;i <= n;i++) cin >> arr[i];
	multiset<int> S;
	for(int i = 1;i <= n;i++){
		S.insert(arr[i]);
		if(i-D >= 1) S.erase(S.find(arr[i-D]));
		
		if(sz(S) < D) block[i] = 0;
		else block[i] = *(S.begin());
	}
	
	vector<ii> B = {{1023456789, 0}};
	for(int i = 1;i <= n;i++){
		int low = 0, high = sz(B);
		while(low != high-1){
			int mid = (low+high)/2;
			if(B[mid].first < arr[i]) high = mid;
			else low = mid;
		}
		
		ii x = B[low];
		if(x.first == 1023456789) x.second = 0;
		//show2(i, x.second+1);
		
		///compute dp
		dp[i] = query(x.second+1, i-1, arr[i])+1;
		if(dp[i] < 1) dp[i] = 1;
		update(i, ii(arr[i],dp[i]));
		
		
		while(not B.empty()){
			if(B.back().first <= block[i]) B.pop_back();
			else break;
		}
		
		B.push_back(ii(block[i], i));
	}
	
	int ans = 1;
	for(int i = 1;i <= n;i++) ans = max(ans, dp[i]);
	cout << ans;
	
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35