oj.uz

Submission #683777

# Submission time Handle Problem Language Result Execution time Memory
683777 2023-01-19T10:39:32 Z gagik_2007 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 1618 ms 38096 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];
ll c[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];
	}
	if (n <= 5000 && m <= 5000) {
		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;
		}
	}
	else {
		int cur = 0;
		c[0] = 0;
		for (int i = 1; i < n; i++) {
			if (a[i] < a[i - 1])cur++;
			c[i] = cur;
		}
		for (int i = 0; i < m; i++) {
			int l, r;
			cin >> l >> r >> k;
			l--, r--;
			cout << (c[l] == c[r]) << 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 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8068 KB Output is correct
5 Correct 5 ms 8176 KB Output is correct
6 Correct 5 ms 8144 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8068 KB Output is correct
5 Correct 5 ms 8176 KB Output is correct
6 Correct 5 ms 8144 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 11 ms 8404 KB Output is correct
12 Correct 31 ms 8384 KB Output is correct
13 Correct 31 ms 8392 KB Output is correct
14 Correct 40 ms 8472 KB Output is correct
15 Correct 37 ms 8524 KB Output is correct
16 Correct 41 ms 8532 KB Output is correct
17 Correct 25 ms 8480 KB Output is correct
18 Correct 32 ms 8484 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1565 ms 25708 KB Output is correct
2 Correct 1537 ms 26576 KB Output is correct
3 Correct 1614 ms 38096 KB Output is correct
4 Correct 1606 ms 38024 KB Output is correct
5 Correct 1618 ms 37908 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8068 KB Output is correct
5 Correct 5 ms 8176 KB Output is correct
6 Correct 5 ms 8144 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 11 ms 8404 KB Output is correct
12 Correct 31 ms 8384 KB Output is correct
13 Correct 31 ms 8392 KB Output is correct
14 Correct 40 ms 8472 KB Output is correct
15 Correct 37 ms 8524 KB Output is correct
16 Correct 41 ms 8532 KB Output is correct
17 Correct 25 ms 8480 KB Output is correct
18 Correct 32 ms 8484 KB Output is correct
19 Incorrect 312 ms 11712 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 5 ms 8068 KB Output is correct
5 Correct 5 ms 8176 KB Output is correct
6 Correct 5 ms 8144 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 5 ms 8148 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Correct 11 ms 8404 KB Output is correct
12 Correct 31 ms 8384 KB Output is correct
13 Correct 31 ms 8392 KB Output is correct
14 Correct 40 ms 8472 KB Output is correct
15 Correct 37 ms 8524 KB Output is correct
16 Correct 41 ms 8532 KB Output is correct
17 Correct 25 ms 8480 KB Output is correct
18 Correct 32 ms 8484 KB Output is correct
19 Correct 1565 ms 25708 KB Output is correct
20 Correct 1537 ms 26576 KB Output is correct
21 Correct 1614 ms 38096 KB Output is correct
22 Correct 1606 ms 38024 KB Output is correct
23 Correct 1618 ms 37908 KB Output is correct
24 Incorrect 148 ms 9892 KB Output isn't correct
25 Halted 0 ms 0 KB -