Submission #978114

#	Time	Username	Problem	Language	Result	Execution time	Memory
978114		Isam	Global Warming (CEOI18_glo)	C++17	25 / 100	2061 ms	7512 KiB

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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25