oj.uz

Submission #903023

# Submission time Handle Problem Language Result Execution time Memory
903023 2024-01-11T05:18:25 Z LCJLY Financial Report (JOI21_financial) C++14
5 / 100
 1126 ms 390688 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,arr[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 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 1 ms 444 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 1 ms 444 KB Output is correct
15 Incorrect 0 ms 348 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 5560 KB Output is correct
2 Incorrect 175 ms 5316 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 175 ms 24684 KB Output is correct
2 Correct 197 ms 24384 KB Output is correct
3 Correct 371 ms 31056 KB Output is correct
4 Correct 1126 ms 372276 KB Output is correct
5 Correct 1038 ms 372144 KB Output is correct
6 Correct 1126 ms 371720 KB Output is correct
7 Correct 624 ms 390560 KB Output is correct
8 Correct 597 ms 390688 KB Output is correct
9 Correct 567 ms 370516 KB Output is correct
10 Correct 791 ms 370924 KB Output is correct
11 Correct 1049 ms 372348 KB Output is correct
12 Correct 1031 ms 372072 KB Output is correct

Subtask #6
0 / 35.0

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