oj.uz

Submission #889871

# Submission time Handle Problem Language Result Execution time Memory
889871 2023-12-20T08:45:18 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 144536 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define forik(x) ll i = 1; i <= x; i++

// (a mod 1e9) / (b mod 1e9) = a * (b^1e9)

using namespace std;

ll a, b, c, e, f, t[8000001], n, m, k, p[200001], d[5001][5001];
vector <pair <ll, ll>> g;

void upd (ll idx, ll val, ll tl = 1, ll tr = n, ll v = 1){
	if (tl > idx || tr < idx){
		return;
	}
	if (tl == tr && tr == idx){
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	upd (idx, val, tl, tm, v * 2);
	upd (idx, val, tm + 1, tr, v * 2 + 1);
	t[v] = t[v * 2 + 1] + t[v * 2];
}

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (tl >= l && tr <= r){
		return t[v];
	}
	if (tl > r || l > tr){
		return 0;
	}
	ll tm = (tl + tr) / 2;
	return get (l, r, tl, tm, v * 2) + get (l, r, tm + 1, tr, v * 2 + 1);
}

signed main (){
	//freopen (".in", "r", stdin);
	//freopen (".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	if (n <= 5000 && m <= 5000){
		for (int i = 1; i <= n; i++){
			a = p[i];
			for (int y = i + 1; y <= n; y++){
				d[i][y] = d[i][y - 1];
				a = max (a, p[y]);
				if (a > p[y]){
					d[i][y] = max (d[i][y], a + p[y]);
				}
			}	
		}
		while (m--){
			cin >> a >> b >> c;
			e = 1;
			if (d[a][b] > c){
				e = 0;
			}
			cout << e << '\n';
		}	
	}
	else{
		a = p[1];
		for (int i = 1; i <= n; i++){
			if (a > p[i]){
				upd (i, p[i] + a);
			}
			a = p[i];
		}
		while (m--){
			cin >> a >> b >> c;
			if (a == b){
				cout << 1 << '\n';
				continue;
			}
			if (get (a + 1, b) > c){
				cout << "0\n";
			}
			else{
				cout << "1\n";
			}
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 13 ms 22872 KB Output is correct
12 Correct 61 ms 139920 KB Output is correct
13 Correct 56 ms 139624 KB Output is correct
14 Correct 56 ms 144320 KB Output is correct
15 Correct 56 ms 144468 KB Output is correct
16 Correct 49 ms 144400 KB Output is correct
17 Correct 37 ms 109928 KB Output is correct
18 Correct 52 ms 144536 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 6736 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 13 ms 22872 KB Output is correct
12 Correct 61 ms 139920 KB Output is correct
13 Correct 56 ms 139624 KB Output is correct
14 Correct 56 ms 144320 KB Output is correct
15 Correct 56 ms 144468 KB Output is correct
16 Correct 49 ms 144400 KB Output is correct
17 Correct 37 ms 109928 KB Output is correct
18 Correct 52 ms 144536 KB Output is correct
19 Incorrect 132 ms 11860 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 5468 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 13 ms 22872 KB Output is correct
12 Correct 61 ms 139920 KB Output is correct
13 Correct 56 ms 139624 KB Output is correct
14 Correct 56 ms 144320 KB Output is correct
15 Correct 56 ms 144468 KB Output is correct
16 Correct 49 ms 144400 KB Output is correct
17 Correct 37 ms 109928 KB Output is correct
18 Correct 52 ms 144536 KB Output is correct
19 Execution timed out 3027 ms 33224 KB Time limit exceeded
20 Halted 0 ms 0 KB -