oj.uz

Submission #93984

# Submission time Handle Problem Language Result Execution time Memory
93984 2019-01-13T20:53:23 Z jasony123123 Global Warming (CEOI18_glo) C++11
0 / 100
 171 ms 7072 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

/*************************CEOI 2018 Day 1 P2*************************/

template<int SZ, class T> struct SegmentTree {
	T data[2 * SZ];
	int _N;

	T id = 0; // identity function (a,id) = a; (id,a) = a;
	T combine(T a, T b) {
		return max(a, b);
	}

	SegmentTree() {}
	void clear(int n) {
		_N = n;
		FOR(i, 0, 2 * _N) data[i] = id;
	}

	void update(int p, T val) { // set value at i to val !not add val!
		data[p + _N] = val;
		for (p += _N; p > 1; p >>= 1)
			data[p >> 1] = combine(data[p], data[p ^ 1]);
	}
	T query(int l, int r) {
		if (l > r) return id;
		r++;
		T resl = id, resr = id;
		for (l += _N, r += _N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) resl = combine(resl, data[l++]);
			if (r & 1) resr = combine(data[--r], resr);
		}
		return combine(resl, resr);
	}
};

const int MX = 200099;
SegmentTree<MX, int> tree;
int n, A[MX], x;
int bacc[MX], forw[MX];

inline bool cmpa(int i, int j) {
	return A[i] < A[j];
}

int addlis(int x, v<int> &cur) {
	int idx = upper_bound(all(cur), x) - cur.begin();
	if (idx == cur.size()) cur.push_back(x);
	else cur[idx] = x;
	return idx;
}

int main() {
	io();
	cin >> n >> x;
	FOR(i, 0, n) cin >> A[i];
	
	v<int> temp = { INT_MIN };
	FOR(i, 0, n)
		bacc[i] = addlis(A[i], temp);
	temp = { INT_MIN };
	RFORE(i, n - 1, 0)
		forw[i] = addlis(-A[i], temp);
//	darr(forw, n);
//	darr(bacc, n);

	v<int> idx(n);
	FOR(i, 0, n) idx[i] = i;
	sort(all(idx), cmpa);
	int ans = 0;

	// +x
	tree.clear(n);
	for (int pi = n - 1, pj = n - 1; pi >= 0; pi--) {
		while (pj >= 0 && A[idx[pj]] >= A[idx[pi]] - x + 1) {
			tree.update(idx[pj], forw[idx[pj]]);
			pj--;
		}
		maxx(ans, bacc[idx[pi]] + tree.query(idx[pi] + 1, n - 1));
	}

	// -x
	tree.clear(n);
	for (int pi = 0, pj = 0; pi < n; pi++) {
		while (pj < n && A[idx[pj]] <= A[idx[pi]] + x - 1) {
			tree.update(idx[pj], bacc[idx[pj]]);
			pj++;
		}
		maxx(ans, forw[idx[pi]] + tree.query(0, idx[pi] - 1));
	}

	cout << ans << "\n";
}

Compilation message

glo.cpp: In function 'int addlis(int, std::vector<int>&)':
glo.cpp:85:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (idx == cur.size()) cur.push_back(x);
      ~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7032 KB Output is correct
2 Correct 133 ms 7032 KB Output is correct
3 Correct 127 ms 7032 KB Output is correct
4 Correct 143 ms 7032 KB Output is correct
5 Incorrect 95 ms 6772 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2040 KB Output is correct
2 Correct 31 ms 2044 KB Output is correct
3 Correct 29 ms 2040 KB Output is correct
4 Incorrect 21 ms 2040 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3708 KB Output is correct
2 Correct 61 ms 3772 KB Output is correct
3 Correct 171 ms 7072 KB Output is correct
4 Incorrect 82 ms 6796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -