Submission #978113

#	Time	Username	Problem	Language	Result	Execution time	Memory
978113		Isam	Global Warming (CEOI18_glo)	C++17	38 / 100	2051 ms	10108 KiB

glo

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

#define eb emplace_back
#define intt long long

constexpr int sz = 2e5 + 5;
constexpr intt inf = (intt)1E18 + 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);
}

inline int lis(vector<intt> const& a) {
    
	int N = a.size();
	
	vector<intt> d(N+1, inf);
    
	d[0] = -inf;

    for (int i = 0; i < N; i++) {
        intt l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= N; l++) {
        if (d[l] < inf)
            ans = l;
    }
    return ans;
}


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<intt> b;
		for(register int i = 1; i <= n; ++i){
			b.eb(t[i]);
		}
		return cout << lis(b) << '\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<intt> b;
		for(register int i = 1; i <= n; ++i){
			b.eb(get_ans(1, n, 1, i, i).sm);
		}
		
		ans = max(ans, lis(b));
		
		
		update(1, 1, n, l, n, -x);
	}
	
	
	cout << ans << '\n';
		
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:96:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   96 |  for(register int i = 1; i <= n; ++i){
      |                   ^
glo.cpp:102:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  102 |   for(register int i = 1; i <= n; ++i){
      |                    ^
glo.cpp:112:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  112 |  for(register int l = 1; l <= n; ++l){
      |                   ^
glo.cpp:117:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  117 |   for(register int i = 1; i <= n; ++i){
      |                    ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25