oj.uz

Submission #861110

# Submission time Handle Problem Language Result Execution time Memory
861110 2023-10-15T10:32:13 Z lovrot Teams (CEOI11_tea) C++17
0 / 100
 2500 ms 28200 KB 
#include <cstdio> 
#include <algorithm> 
#include <queue>
#include <stack> 
#include <deque> 
#include <vector> 

#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6 + 10;
const int oo = 2e9; 

template <typename T> 
struct mono_stack {
	stack<T> S; 
	bool empty() const { return S.empty(); }
	void push(T x) {
		while(!S.empty() && S.top() < x) S.pop(); 
		S.push(x); 
	}
	void clear() {
		while(!S.empty()) S.pop();
	}
	void pop(T x) {
		if(!S.empty() && S.top() == x) S.pop();
	}
	T top() {
		if(S.empty()) return T();
		return S.top(); 
	}
};

template <typename T> 
struct mono_deque {	
	mono_stack<T> L, R;
	deque<T> D;
	bool empty() const { return D.empty(); }
	void build() {
		L.clear(); 
		R.clear(); 
		for(int i = (D.size() - 1) / 2; i >= 0; --i) L.push(D[i]); 
		for(int i = (D.size() - 1) / 2 + 1; i < D.size(); ++i) R.push(D[i]); 
	}
	void pop_front() {
		if(D.empty()) return;
		T x = D.front();
		D.pop_front(); 
		if(L.empty()) this->build();
		else L.pop(x);
	}
	void pop_back() {
		if(D.empty()) return;
		T x = D.back();
		D.pop_back(); 
		if(R.empty()) this->build();
		else R.pop(x);
	}
	void push_front(T x) { 
		D.push_front(x);
		L.push(x); 
	}
	void push_back(T x) { 
		D.push_back(x);
		R.push(x);
	}
	T max() { 
		T a = L.top(), b = R.top();
		return a < b ? b : a;
	}
	void print() {
		for(int i = 0; i < D.size(); ++i) printf("%d%c", D[i].X, " \n"[i == (D.size()) - 1]);
	}
};

int n, A[N];

int I[N], DP[N], TO[N];

int bs(int s) {
	mono_deque<pii> D;
	D.push_back(make_pair(0, 0));
	int l = 0, r = 0;
	for(int i = 1; i <= n; ++i) {
		int x = A[I[i]], _l = i - s, _r = i - A[I[i]];

		if(_l > _r) return -1;

		for(l; l < _l; ++l) D.pop_front();
		
		if(r < _r) 
			for(r; r < _r; ++r) D.push_back(make_pair(DP[r + 1], r + 1));
		else 
			for(r; r > _r; --r) D.pop_back(); 

		pii res = D.max(); 
		DP[i] = res.X + 1;
		TO[i] = res.Y;
//		D.print();
//		printf("%d %d %d\n", i, DP[i], TO[i]);
	}
	return DP[n];
}

int main() {
	scanf("%d", &n); 
	for(int i = 1; i <= n; ++i) {
		scanf("%d", A + i); 
		I[i] = i;
	}
	sort(I + 1, I + n + 1, [](int a, int b) { return A[a] < A[b]; });

	int ans = bs(oo); 

	int lo = 1, hi = n;
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		int res = bs(mi);
		if(res < ans) lo = mi;
		else hi = mi;
	}

	ans = bs(hi);

	printf("%d\n", hi);
	printf("%d", ans);
	for(int i = n, j = n; i > 0; --i) {
		if(i == j) {
			printf("\n%d ", i - TO[i]);
			j = TO[i];
		}
		printf("%d ", I[i]); 
	}
	printf("\n");
	return 0;
}

Compilation message

tea.cpp: In function 'int bs(int)':
tea.cpp:93:7: warning: statement has no effect [-Wunused-value]
   93 |   for(l; l < _l; ++l) D.pop_front();
      |       ^
tea.cpp:96:8: warning: statement has no effect [-Wunused-value]
   96 |    for(r; r < _r; ++r) D.push_back(make_pair(DP[r + 1], r + 1));
      |        ^
tea.cpp:98:8: warning: statement has no effect [-Wunused-value]
   98 |    for(r; r > _r; --r) D.pop_back();
      |        ^
tea.cpp:89:7: warning: unused variable 'x' [-Wunused-variable]
   89 |   int x = A[I[i]], _l = i - s, _r = i - A[I[i]];
      |       ^
tea.cpp: In instantiation of 'void mono_deque<T>::build() [with T = std::pair<int, int>]':
tea.cpp:53:23:   required from 'void mono_deque<T>::pop_front() [with T = std::pair<int, int>]'
tea.cpp:93:35:   required from here
tea.cpp:47:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = (D.size() - 1) / 2 + 1; i < D.size(); ++i) R.push(D[i]);
      |                                       ~~^~~~~~~~~~
tea.cpp: In function 'int main()':
tea.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
tea.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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