oj.uz

Submission #903025

# Submission time Handle Problem Language Result Execution time Memory
903025 2024-01-11T05:19:14 Z LCJLY Financial Report (JOI21_financial) C++14
5 / 100
 1230 ms 387880 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 0 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 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 133 ms 2792 KB Output is correct
2 Incorrect 177 ms 2664 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 125 ms 2656 KB Output is correct
2 Correct 237 ms 2996 KB Output is correct
3 Correct 431 ms 9496 KB Output is correct
4 Correct 1185 ms 369328 KB Output is correct
5 Correct 985 ms 369516 KB Output is correct
6 Correct 1148 ms 368588 KB Output is correct
7 Correct 659 ms 387780 KB Output is correct
8 Correct 642 ms 387880 KB Output is correct
9 Correct 613 ms 367644 KB Output is correct
10 Correct 840 ms 368184 KB Output is correct
11 Correct 1230 ms 369388 KB Output is correct
12 Correct 1132 ms 369216 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 1 ms 360 KB Output isn't correct
16 Halted 0 ms 0 KB -