Submission #638897

#	Time	Username	Problem	Language	Result	Execution time	Memory
638897		Pietra	Financial Report (JOI21_financial)	C++14	5 / 100	4051 ms	12128 KiB

Main

#include<bits/stdc++.h>
#define esq (2*no)
#define dir ((2*no)+1)
#define meio ((i+j)>>1)
using namespace std ; 

// mantenho num vetor os kras q eu add - preciso mudar tds os caras q eu n atualizei desde o kra q eu to vendo 
// se essa dist passar de d 

const int maxn = 3e5 + 5 ; 

int n, d, v[maxn], lst_app[maxn], lst[maxn] ; 
int tree[4*maxn] ; 

struct SEG{

	void upd(int no, int i, int j, int pos, int val){
		if(i == j){
    		tree[no] = max(tree[no], val) ; return ; 
    	}
    	if(pos <= meio) upd(esq, i, meio, pos, val) ; 
    	else upd(dir, meio + 1, j, pos, val) ; 
    	tree[no] = max(tree[esq], tree[dir]) ;  
	}

	void upd2(int no, int i, int j, int pos, int val){
		if(i == j){
    		tree[no] = val ; return ; 
    	}
    	if(pos <= meio) upd2(esq, i, meio, pos, val) ; 
    	else upd2(dir, meio + 1, j, pos, val) ; 
    	tree[no] = max(tree[esq], tree[dir]) ;  
	}

	int query(int no, int i, int j, int a, int b){
		if(a > j || b < i) return 0 ; 
    	if(b >= j && a <= i) return tree[no] ; 
		return max(query(esq, i, meio, a, b), query(dir, meio + 1, j, a, b)) ;   
	}

} Seg ; 

int main(){

	cin >> n >> d ; 

	vector<int> vec ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> v[i] ; 
		vec.push_back(v[i]) ; 
	}

	sort(vec.begin(), vec.end()) ; 

	for(int i = 1 ; i <= n ; i++) v[i] = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin() + 1 ; 

	int ans = 0 ; 

	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; ; j++){
			if(i-j <= d) break ; 
			if(lst_app[v[j]] == j){
				// cout << i << " " << j << " " << lst[v[j]] << "\n" ; 
				Seg.upd2(1, 1, n, v[j], lst[v[j]]) ; 
				lst_app[v[j]] = 0 ;
				// cout << Seg.query(1, 1, n, v[j], v[j]) << "\n" ; 
			}
		}
		int att = Seg.query(1, 1, n, 1, v[i]-1) ;
		// cout << i << " " << att << "\n" ;
		int ant = Seg.query(1, 1, n, v[i], v[i]) ; 
		if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
		ans = max(ans, att + 1) ;  
		Seg.upd(1, 1, n, v[i], att + 1) ;  
	}

	cout << ans << "\n" ; 

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   73 |   if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
      |   ^~
Main.cpp:73:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   73 |   if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
      |                                       ^~~~~~~

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