oj.uz

Submission #889928

# Submission time Handle Problem Language Result Execution time Memory
889928 2023-12-20T09:54:07 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1213 ms 124128 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 t[8000001], a, b, c, d, e, f, n, m, k, p[1000001], l, md[8000001];
pair <ll, ll> mx[8000001];

pair <ll, ll> qw (pair <ll, ll> a, pair <ll, ll> b){
	if (a.F > b.F){
		return a;
	}
	else if (b.F > a.F){
		return b;
	}
	else{
		if (b.S > a.S){
			return b;
		}
		else{
			return a;
		}
	}
}

void buildmx (ll tl = 1, ll tr = n, ll v = 1){
	if (tl == tr){
		mx[v] = {p[tl], tl};
		return;
	}
	ll tm = (tl + tr) / 2;
	buildmx (tl, tm, v * 2);
	buildmx (tm + 1, tr, v * 2 + 1);
	mx[v] = qw (mx[v * 2], mx[v * 2 + 1]);
}

pair <ll, ll> getmx (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (l <= tl && tr <= r){
		return mx[v];
	}
	if (tr < l || r < tl){
		return {-1e18, 0};
	}
	ll tm = (tl + tr) / 2;
	return qw (getmx (l, r, tl, tm, v * 2), getmx (l, r, tm + 1, tr, v * 2 + 1));
}

void push (ll tl, ll tr, ll v){
	if (md[v] != -1){
		t[v] = max (md[v], t[v]);
		if (tl != tr){
			md[v * 2] += md[v];
			md[v * 2 + 1] += md[v];
		}
		md[v] = -1;
	}
}

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

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	push (tl, tr, v);
	if (l <= tl && tr <= r){
		return t[v];
	}
	if (l > tr || tl > r){
		return -1;
	}
	ll tm = (tl + tr) / 2;
	return max (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 <= 8000000; i++){
		md[i] = -1;
	}
	for (int i = 1; i <= n; i++){
		cin >> p[i];
	}
	buildmx ();
	for (int i = 2; i <= n; i++){
//		l = 1;
		while (l < i){
			pair <ll, ll> an = getmx (l, i);
			if (an.S == i){
				break;
			}
//			cout << an.F << ' ' << an.S << ' ' << i << ' ' << l << '\n';
			upd (l, i, an.F + p[i]);
			l = an.S + 1;
		}
	}
	while (m--){
		cin >> a >> b >> c;
		if (get (a, b) > c){
			cout << 0 << '\n';
		}
		else{
			cout << 1 << '\n';
		}
	}
//	for (int i = 1; i <= 40; i++){
//		cout << t[i] << ' ';
//	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 67932 KB Output is correct
2 Correct 8 ms 67928 KB Output is correct
3 Incorrect 8 ms 68184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 67932 KB Output is correct
2 Correct 8 ms 67928 KB Output is correct
3 Incorrect 8 ms 68184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 67932 KB Output is correct
2 Correct 8 ms 67928 KB Output is correct
3 Incorrect 8 ms 68184 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 67932 KB Output is correct
2 Correct 8 ms 67928 KB Output is correct
3 Incorrect 8 ms 68184 KB Output isn't correct
4 Halted 0 ms 0 KB -