oj.uz

Submission #683778

# Submission time Handle Problem Language Result Execution time Memory
683778 2023-01-19T10:40:39 Z gagik_2007 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 1619 ms 18032 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);
	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 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 Correct 2 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 21 ms 548 KB Output is correct
13 Correct 23 ms 572 KB Output is correct
14 Correct 27 ms 664 KB Output is correct
15 Correct 35 ms 640 KB Output is correct
16 Correct 28 ms 656 KB Output is correct
17 Correct 20 ms 660 KB Output is correct
18 Correct 31 ms 652 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1609 ms 18032 KB Output is correct
2 Correct 1570 ms 17864 KB Output is correct
3 Correct 1619 ms 17888 KB Output is correct
4 Correct 1612 ms 17944 KB Output is correct
5 Correct 1533 ms 17900 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 21 ms 548 KB Output is correct
13 Correct 23 ms 572 KB Output is correct
14 Correct 27 ms 664 KB Output is correct
15 Correct 35 ms 640 KB Output is correct
16 Correct 28 ms 656 KB Output is correct
17 Correct 20 ms 660 KB Output is correct
18 Correct 31 ms 652 KB Output is correct
19 Incorrect 308 ms 3772 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 21 ms 548 KB Output is correct
13 Correct 23 ms 572 KB Output is correct
14 Correct 27 ms 664 KB Output is correct
15 Correct 35 ms 640 KB Output is correct
16 Correct 28 ms 656 KB Output is correct
17 Correct 20 ms 660 KB Output is correct
18 Correct 31 ms 652 KB Output is correct
19 Correct 1609 ms 18032 KB Output is correct
20 Correct 1570 ms 17864 KB Output is correct
21 Correct 1619 ms 17888 KB Output is correct
22 Correct 1612 ms 17944 KB Output is correct
23 Correct 1533 ms 17900 KB Output is correct
24 Incorrect 148 ms 2080 KB Output isn't correct
25 Halted 0 ms 0 KB -