oj.uz

Submission #683775

# Submission time Handle Problem Language Result Execution time Memory
683775 2023-01-19T10:34:26 Z gagik_2007 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 50116 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
ll n, m, k;
ll a[N];
ll lgs[N];
vector<pair<pair<int, int>, pair<int, ll>>>q;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	lgs[1] = 0;
	lgs[2] = 1;
	for (int i = 3; i < N; i++) {
		lgs[i] = lgs[i / 2] + 1;
	}
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int>ans(m);
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r >> k;
		l--, r--;
		q.push_back({ { l,r },{i,k} });
	}
	sort(q.begin(), q.end());
	int qi = 0;
	for (int i = 0; i < n; i++) {
		ll max_val = 0;
		ll mx = 0;
		for (int j = i; j < n; j++) {
			if (mx > a[j]) {
				max_val = max(max_val, a[j] + mx);
			}
			else {
				mx = a[j];
			}
			while (qi < m && q[qi].ff.ff == i && q[qi].ff.ss == j) {
				ans[q[qi].ss.ff] = (max_val <= q[qi].ss.ss);
				//cout << "DNUM EM: " << q[qi].ss.ff << ": "
				//	<< max_val << ", " << q[qi].ss.ss << endl;
				qi++;
			}
		}
	}
	for (auto x : ans) {
		cout << x << endl;
	}
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8040 KB Output is correct
2 Correct 5 ms 8156 KB Output is correct
3 Correct 7 ms 8168 KB Output is correct
4 Correct 5 ms 8096 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 7 ms 8168 KB Output is correct
7 Correct 7 ms 8148 KB Output is correct
8 Correct 6 ms 8200 KB Output is correct
9 Correct 6 ms 8148 KB Output is correct
10 Correct 7 ms 8156 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8040 KB Output is correct
2 Correct 5 ms 8156 KB Output is correct
3 Correct 7 ms 8168 KB Output is correct
4 Correct 5 ms 8096 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 7 ms 8168 KB Output is correct
7 Correct 7 ms 8148 KB Output is correct
8 Correct 6 ms 8200 KB Output is correct
9 Correct 6 ms 8148 KB Output is correct
10 Correct 7 ms 8156 KB Output is correct
11 Correct 13 ms 8420 KB Output is correct
12 Correct 36 ms 8424 KB Output is correct
13 Correct 33 ms 8464 KB Output is correct
14 Correct 45 ms 8612 KB Output is correct
15 Correct 40 ms 8660 KB Output is correct
16 Correct 47 ms 8572 KB Output is correct
17 Correct 33 ms 8556 KB Output is correct
18 Correct 55 ms 8520 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8040 KB Output is correct
2 Correct 5 ms 8156 KB Output is correct
3 Correct 7 ms 8168 KB Output is correct
4 Correct 5 ms 8096 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 7 ms 8168 KB Output is correct
7 Correct 7 ms 8148 KB Output is correct
8 Correct 6 ms 8200 KB Output is correct
9 Correct 6 ms 8148 KB Output is correct
10 Correct 7 ms 8156 KB Output is correct
11 Correct 13 ms 8420 KB Output is correct
12 Correct 36 ms 8424 KB Output is correct
13 Correct 33 ms 8464 KB Output is correct
14 Correct 45 ms 8612 KB Output is correct
15 Correct 40 ms 8660 KB Output is correct
16 Correct 47 ms 8572 KB Output is correct
17 Correct 33 ms 8556 KB Output is correct
18 Correct 55 ms 8520 KB Output is correct
19 Execution timed out 3054 ms 22092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8040 KB Output is correct
2 Correct 5 ms 8156 KB Output is correct
3 Correct 7 ms 8168 KB Output is correct
4 Correct 5 ms 8096 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 7 ms 8168 KB Output is correct
7 Correct 7 ms 8148 KB Output is correct
8 Correct 6 ms 8200 KB Output is correct
9 Correct 6 ms 8148 KB Output is correct
10 Correct 7 ms 8156 KB Output is correct
11 Correct 13 ms 8420 KB Output is correct
12 Correct 36 ms 8424 KB Output is correct
13 Correct 33 ms 8464 KB Output is correct
14 Correct 45 ms 8612 KB Output is correct
15 Correct 40 ms 8660 KB Output is correct
16 Correct 47 ms 8572 KB Output is correct
17 Correct 33 ms 8556 KB Output is correct
18 Correct 55 ms 8520 KB Output is correct
19 Execution timed out 3016 ms 50116 KB Time limit exceeded
20 Halted 0 ms 0 KB -