oj.uz

Submission #902883

# Submission time Handle Problem Language Result Execution time Memory
902883 2024-01-11T04:11:14 Z LCJLY Financial Report (JOI21_financial) C++14
5 / 100
 1209 ms 390740 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline int combine(int a, int b){
	return max(a,b);
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(0){
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void upd(int x, int y){
		if(s==e){
			v=y;
			return;
		}
		inst();
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){	
	int n,k;
	cin >> n >> k;
	
	int maxn=1000000005;
	node st(0,maxn);
	int arr[n];
	map<int,int>last;
	for(int x=0;x<n;x++){
		cin >> arr[x];
		arr[x]++;
		last[arr[x]]=-1;
	}
	
	int dp[n];
	
	set<pii>se;
	for(int x=0;x<n;x++){
		//remove
		while(!se.empty()){
			if(se.begin()->first<x-k){
				pii hold=*se.begin();
				se.erase(se.begin());
				st.upd(hold.second,0);
				last[hold.second]=-1;
			}
			else break;
		}
		
		int l=st.query(0,arr[x]-1)+1;
		int r=st.query(arr[x],maxn);
		dp[x]=max(l,r);
		st.upd(arr[x],l);
		if(last[arr[x]]!=-1){
			int index=last[arr[x]];
			se.erase(se.find({index,dp[index]}));
			last[arr[x]]=x;
		}
		se.insert({x,arr[x]});
	}
	
	cout << dp[n-1];
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 464 KB Output is correct
15 Incorrect 1 ms 360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 464 KB Output is correct
15 Incorrect 1 ms 360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 464 KB Output is correct
15 Incorrect 1 ms 360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 2792 KB Output is correct
2 Incorrect 169 ms 2660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 21520 KB Output is correct
2 Correct 226 ms 21740 KB Output is correct
3 Correct 434 ms 30964 KB Output is correct
4 Correct 1195 ms 372236 KB Output is correct
5 Correct 1075 ms 372224 KB Output is correct
6 Correct 1209 ms 371524 KB Output is correct
7 Correct 606 ms 390740 KB Output is correct
8 Correct 631 ms 390588 KB Output is correct
9 Correct 586 ms 370260 KB Output is correct
10 Correct 806 ms 371084 KB Output is correct
11 Correct 1123 ms 372080 KB Output is correct
12 Correct 1010 ms 372276 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 464 KB Output is correct
15 Incorrect 1 ms 360 KB Output isn't correct
16 Halted 0 ms 0 KB -