Submission #978114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978114	2024-05-08T21:07:08 Z	Isam	Global Warming (CEOI18_glo)	C++17	25 / 100	2000 ms	7512 KB

glo

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

#define eb emplace_back
#define intt long long
#define all(x) begin(x),end(x)


constexpr int sz = 2e5 + 5;
constexpr int inf = 1E9 + 7;

int n, x, t[sz];

struct Node{
	intt sm;
	
} st[sz << 2], lazy[sz << 2];

Node operator+(Node i, Node j){
	return Node{i.sm + j.sm};
}

inline void build(int in, int l, int r){
	if(l == r){
		st[in].sm = t[l];
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(in << 1, l, mid);
	build(in << 1 | 1, mid + 1, r);
	st[in] = st[in << 1] + st[in << 1 | 1];
	return;
}

Node zro;

inline void relax(int in, int l, int r){
	if(l ^ r){
		lazy[in << 1].sm += lazy[in].sm;
		lazy[in << 1 | 1].sm += lazy[in].sm;
	}
	st[in].sm += lazy[in].sm * (r - l + 1);
	lazy[in] = zro;
	return;
}

inline void update(int in, int l, int r, int L, int R, int val){
	if(lazy[in].sm != zro.sm) relax(in, l, r);
	if(l > R || r < L || l > r) return;
	if(l >= L && r <= R){
		lazy[in].sm += val;
		relax(in, l, r);
		return;
	}
	int mid = l + ((r - l) >> 1);
	update(in << 1, l, mid, L, R, val);
	update(in << 1 | 1, mid + 1, r, L, R, val);
	st[in] = st[in << 1] + st[in << 1 | 1];
	return;
}

Node get_ans(int l, int  r, int in, int L, int R){
	if(lazy[in].sm != zro.sm) relax(in, l, r);
	if(l > R || r < L || r < l) return zro;	
	if(l >= L && r <= R) return st[in];
	int mid = l + ((r - l) >> 1);
	return get_ans(l, mid, in << 1, L, R) + get_ans(mid + 1, r, in << 1 | 1, L, R);
}

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	cin >> n >> x;
	
	for(register int i = 1; i <= n; ++i){
		cin >> t[i];
	}
	
	if(x == 0){
		vector<int> dp(n+1, inf);
		
		dp[0] = -inf;
		
		for(register int i = 1; i <= n; ++i){
			
			int l = upper_bound(all(dp), t[i]) - dp.begin();
			
			if(dp[l] > t[i] && dp[l-1] < t[i]){
				dp[l] = t[i];
			}
			
			
		}
		
		int res(1);
		
		for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) res = i;
		
		return cout << res << '\n', 0;
	}
	
	build(1, 1, n);
	
	int ans(1);
	
	for(register int l = 1; l <= n; ++l){
		
		update(1, 1, n, l, n, x);
		
		vector<int> dp(n+1, inf);
		
		dp[0] = -inf;
		
		for(register int i = 1; i <= n; ++i){
			t[i] = get_ans(1, n, 1, i, i).sm;
		}
		
		for(register int i = 1; i <= n; ++i){
			
			int l = upper_bound(all(dp), t[i]) - dp.begin();
			
			if(dp[l] > t[i] && dp[l-1] < t[i]){
				dp[l] = t[i];
			}
			
			
		}
		
		int res(1);
		
		for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) res = i;
		
		ans = max(ans, res);
		
		
		update(1, 1, n, l, n, -x);
	}
	
	
	cout << ans << '\n';
		
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:75:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   75 |  for(register int i = 1; i <= n; ++i){
      |                   ^
glo.cpp:84:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   84 |   for(register int i = 1; i <= n; ++i){
      |                    ^
glo.cpp:97:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   97 |   for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) res = i;
      |                    ^
glo.cpp:106:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  106 |  for(register int l = 1; l <= n; ++l){
      |                   ^
glo.cpp:114:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  114 |   for(register int i = 1; i <= n; ++i){
      |                    ^
glo.cpp:118:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  118 |   for(register int i = 1; i <= n; ++i){
      |                    ^
glo.cpp:131:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  131 |   for(register int i = 1; i <= n; ++i) if(dp[i] ^ inf) res = i;
      |                    ^

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	2548 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	2548 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	2548 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Incorrect	113 ms	2392 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	1880 KB	Output is correct
2	Correct	27 ms	1992 KB	Output is correct
3	Correct	27 ms	1808 KB	Output is correct
4	Correct	32 ms	1812 KB	Output is correct
5	Correct	20 ms	1884 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2061 ms	7064 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2021 ms	7512 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	2548 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Incorrect	113 ms	2392 KB	Output isn't correct
20	Halted	0 ms	0 KB	-