Submission #638884

#	Time	Username	Problem	Language	Result	Execution time	Memory
638884		Pietra	Financial Report (JOI21_financial)	C++14	14 / 100	268 ms	13832 KiB

Main

// n valores 
// qr escolher m p apresentar - a dif de 2 adjs n pode ser maior que d 
// o ultimo a ser mostrado é pm = n (o ultimo cara smp aparece)
// score é o n° vzs q o at eh maior que o pref dele + 1 
#include<bits/stdc++.h>
#define esq (2*no)
#define dir ((2*no)+1)
#define meio ((i+j)>>1)
#define int long long
using namespace std ;

// qual o 1o maior p cada cara - esquerda 
const int inf = 1e13 ; 
const int maxn = 3e5 + 5 ; 

int n, mx[maxn], d, v[maxn], esqq[maxn] ; 
int tree[4*maxn] ; 

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" ; 

}

// dp[i][d] - maior valor até i sendo d o ultimo usado 

struct SEG{

	// lis -> muda a pos do valor + 1 e query 1, no meu - 1 
	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]) ;  
	}

	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 sub2(){

	// d == n -> maior lis 

	int ans = 0 ; 

	for(int i = 1 ; i <= n ; i++){
		int at = Seg.query(1, 1, n, 1, i-1) + 1 ;
		Seg.upd(1, 1, n, i, at+1) ;  
		ans = max(ans, at) ; 
	}

	cout << ans << "\n" ; 

}

int32_t 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() ; 
    else sub2() ; 

}

Compilation message (stderr)

Main.cpp: In function 'void sub1()':
Main.cpp:33:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |      for(int i = 1 ; i < vec.size() ; i++) if(vec[i] - vec[i-1] > d) ok = 0 ;
      |                      ~~^~~~~~~~~~~~
Main.cpp:35:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |      for(int i = 0 ; i < vec.size() ; i++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:43:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |      for(int i = 0 ; i < vec.size() ; i++) sm += (esqq[i]==-1) ;
      |                      ~~^~~~~~~~~~~~
Main.cpp:23:9: warning: unused variable 'tryy' [-Wunused-variable]
   23 |     int tryy = (1<<7) + (1<<6) + (1<<5) + (1<<4);
      |         ^~~~

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