Submission #607511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
607511	2022-07-26T18:58:10 Z	Pietra	Global Warming (CEOI18_glo)	C++14	15 / 100	2000 ms	7128 KB

glo

#include<bits/stdc++.h>
#define int long long
using namespace std ; 

const int maxn = 2e5 + 5 ; 
const int inf = 2e5 + 1 ;

int n, x, v[maxn] ; 
int bit[6*inf] ; 

struct BIT{
     
    void upd(int pos, int val){
        if(pos <= 0) return ;
        for(; pos < 4*inf ; pos += pos&-pos) bit[pos] = max(bit[pos], val) ;
    }
     
    int query(int pos){
        if(pos <= 0) return 0 ;
        int tot = 0 ;
        for(; pos > 0 ; pos -= pos&-pos) tot = max(tot, bit[pos]) ;
        return tot ;
    }
    
} Bit ;

void solve_1(){

	int val = 0 ; 

	for(int i = 1 ; i <= n ; i++){
        int mx = Bit.query(v[i] - 1) ;
        Bit.upd(v[i], mx + 1) ;
        val = max(val, v[i]) ;
    }

    int ans = Bit.query(val+1) ; 

	cout << ans << "\n" ; 

}

int try_val(int l, int r, int val){

	// cout << l << " " << r << " " << val << "\n" ; 
	for(int i = 1 ; i < inf ; i++) bit[i] = 0 ;  

	for(int i = l ; i <= r ; i++) v[i] += val ; 

	int va = 0 ; 

	for(int i = 1 ; i <= n ; i++){
        int mx = Bit.query(v[i] - 1) ;
        Bit.upd(v[i], mx + 1) ;
        va = max(va, v[i]) ;
    }

    int ans = Bit.query(va+1) ;

	for(int i = l ; i <= r ; i++) v[i] -= val ; 

	return ans ; 

}

void solve_2(){

	int ans = try_val(1, n, 0) ; 

	for(int i = 1 ; i <= x ; i++){ // add 
		for(int l = 1 ; l <= n ; l++){
			for(int r = l ; r <= n ; r++){
				ans = max(ans, try_val(l, r, i)) ; 
				ans = max(ans, try_val(l, r, -i)) ;
			}
		}
	}

	cout << ans << "\n" ; 

}

int32_t main(){

	ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 

	cin >> n >> x ; 

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

	if(x == 0){
		vector<int> vec ; 
		for(int i = 1 ; i <= n ; i++) vec.push_back(v[i]) ; 
		sort(vec.begin(), vec.end()) ; 
	    vec.erase(unique(vec.begin(), vec.end()), vec.end()) ; 
	    for(int i = 1 ; i <= n ; i++) v[i] = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin() + 1 ;  
		solve_1() ; 
	}
    else solve_2() ; 

}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	1876 KB	Output is correct
2	Correct	12 ms	1920 KB	Output is correct
3	Correct	4 ms	1912 KB	Output is correct
4	Correct	13 ms	1888 KB	Output is correct
5	Correct	8 ms	1876 KB	Output is correct
6	Correct	4 ms	1912 KB	Output is correct
7	Correct	3 ms	1876 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	32 ms	1876 KB	Output is correct
10	Correct	16 ms	1876 KB	Output is correct
11	Correct	44 ms	1876 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	1876 KB	Output is correct
2	Correct	12 ms	1920 KB	Output is correct
3	Correct	4 ms	1912 KB	Output is correct
4	Correct	13 ms	1888 KB	Output is correct
5	Correct	8 ms	1876 KB	Output is correct
6	Correct	4 ms	1912 KB	Output is correct
7	Correct	3 ms	1876 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	32 ms	1876 KB	Output is correct
10	Correct	16 ms	1876 KB	Output is correct
11	Correct	44 ms	1876 KB	Output is correct
12	Correct	1685 ms	1892 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Execution timed out	2079 ms	1876 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	1876 KB	Output is correct
2	Correct	12 ms	1920 KB	Output is correct
3	Correct	4 ms	1912 KB	Output is correct
4	Correct	13 ms	1888 KB	Output is correct
5	Correct	8 ms	1876 KB	Output is correct
6	Correct	4 ms	1912 KB	Output is correct
7	Correct	3 ms	1876 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	32 ms	1876 KB	Output is correct
10	Correct	16 ms	1876 KB	Output is correct
11	Correct	44 ms	1876 KB	Output is correct
12	Correct	1685 ms	1892 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Execution timed out	2079 ms	1876 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	5124 KB	Output is correct
2	Correct	84 ms	7048 KB	Output is correct
3	Correct	79 ms	7128 KB	Output is correct
4	Correct	76 ms	7052 KB	Output is correct
5	Correct	47 ms	5640 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	4360 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	16 ms	5204 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	1876 KB	Output is correct
2	Correct	12 ms	1920 KB	Output is correct
3	Correct	4 ms	1912 KB	Output is correct
4	Correct	13 ms	1888 KB	Output is correct
5	Correct	8 ms	1876 KB	Output is correct
6	Correct	4 ms	1912 KB	Output is correct
7	Correct	3 ms	1876 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	32 ms	1876 KB	Output is correct
10	Correct	16 ms	1876 KB	Output is correct
11	Correct	44 ms	1876 KB	Output is correct
12	Correct	1685 ms	1892 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Execution timed out	2079 ms	1876 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-