Submission #638899

#	Time	Username	Problem	Language	Result	Execution time	Memory
638899		Pietra	Financial Report (JOI21_financial)	C++14	19 / 100	4057 ms	9264 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], esqq[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 ; 

    void sub1(){
     
    	int ans = 0 ;
     
        int tryy = (1<<7) + (1<<6) + (1<<5) + (1<<4); 
     
        for(int mask = 0 ; mask < (1<<(n+1)) ; mask++){
        	if(mask&(1<<0)) continue ; 
        	vector<int> vec ; 
        	// cout << mask << "\n" ; 
        	for(int i = 1 ; i < n + 1 ; i++){
        		if(mask&(1<<i)) vec.push_back(i) ; 
        	} 
        	bool ok = 1 ; 
        	for(int i = 1 ; i < vec.size() ; i++) if(vec[i] - vec[i-1] > d) ok = 0 ;
        	if(!ok) continue ;  
        	for(int i = 0 ; i < vec.size() ; i++){
        		int fmx = -1 ; 
        		for(int j = i - 1 ; j >= 0 ; j--){
        			if(v[vec[j]] >= v[vec[i]]){fmx = j ; break ;}  
        		}
        		esqq[i] = fmx ; 
        	}
        	int sm = 0 ; 
        	for(int i = 0 ; i < vec.size() ; i++) sm += (esqq[i]==-1) ; 
        	// for(auto a : vec) cout << a << " " ; 
        	// cout << "\n" ; 
        	// for(int i = 0 ; i < vec.size() ; i++) cout << esq[i] << " " ; 
        	// cout << "\n" ; 
         //    cout << sm << "\n" ; 
        	ans = max(ans, sm) ; 
        }
     
        cout << ans << "\n" ; 
        exit(0) ; 
     
    }

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 ; 

	if(n <= 20) sub1() ; 

	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 'void sub1()':
Main.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |          for(int i = 1 ; i < vec.size() ; i++) if(vec[i] - vec[i-1] > d) ok = 0 ;
      |                          ~~^~~~~~~~~~~~
Main.cpp:59:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |          for(int i = 0 ; i < vec.size() ; i++){
      |                          ~~^~~~~~~~~~~~
Main.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |          for(int i = 0 ; i < vec.size() ; i++) sm += (esqq[i]==-1) ;
      |                          ~~^~~~~~~~~~~~
Main.cpp:47:13: warning: unused variable 'tryy' [-Wunused-variable]
   47 |         int tryy = (1<<7) + (1<<6) + (1<<5) + (1<<4);
      |             ^~~~
Main.cpp: In function 'int main()':
Main.cpp:113:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  113 |   if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
      |   ^~
Main.cpp:113:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  113 |   if(att + 1 > ant) lst[v[i]] = ant ; lst_app[v[i]] = i ;
      |                                       ^~~~~~~

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