oj.uz

Submission #761539

# Submission time Handle Problem Language Result Execution time Memory
761539 2023-06-19T23:03:25 Z NK_ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 676 ms 74376 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;



const int INF = 1e9+10;
struct BIT {
	int N; V<int> A; void init(int n) { N = n; A = V<int>(N, INF); }
	void upd(int p, int x) { p = N - 1 - p; for(++p;p<=N;p+=p&-p) A[p-1] = min(A[p-1], x);}
	int get(int r) { r = N - 1 - r; int s = INF; for(++r;r;r-=r&-r) s = min(A[r-1], s); return s; }
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;
	V<int> A(N); for(auto& x : A) cin >> x;

	BIT B; B.init(N);

	V<array<int, 4>> Q(K); for(int i = 0; i < K; i++) {
		cin >> Q[i][1] >> Q[i][2] >> Q[i][0];
		--Q[i][1], --Q[i][2];
		Q[i][3] = i;
	}

	V<array<int, 3>> E;
	V<pair<int, int>> stk = {{-1, -1}};
	for(int i = N - 1; i >= 0; i--) {
		int pos = i;
		while(stk.back().first != -1 && A[stk.back().first] <= A[i]) {
			int x = A[stk.back().first] + A[i];
			// cout << x << " " << i << " " << pos << endl;
			E.push_back({x, i, pos});
			pos = max(pos, stk.back().second);

			stk.pop_back();
		}	
		B.upd(i, N);
		stk.push_back({i, pos});
	}

	sort(rbegin(Q), rend(Q));
	sort(rbegin(E), rend(E));

	vector<int> ans(K);

	int j = 0;
	for(int q = 0; q < K; q++) {
		// cout << q << endl;
		while(j < int(size(E)) && E[j][0] > Q[q][0]) {
			auto [k, i, x] = E[j];
			// cout << i << " " << x << endl;
			B.upd(i, x);
			j++;
		}

		auto [k, l, r, i] = Q[q];

		int x = B.get(l); 
		// cout << l << " " << r << " " << x << endl;
		ans[i] = x >= r;
	}

	for(auto x : ans) cout << x << nl;

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 73344 KB Output is correct
2 Correct 626 ms 74344 KB Output is correct
3 Correct 653 ms 74236 KB Output is correct
4 Correct 676 ms 74376 KB Output is correct
5 Incorrect 480 ms 70628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -