oj.uz

Submission #499062

# Submission time Handle Problem Language Result Execution time Memory
499062 2021-12-27T07:22:08 Z Ziyoda Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 76844 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const ll N = 1e6+1;
ll tr[N], n;
vector<ll>ad[N], a(N), li(N), ri(N), ki(N);

void add(ll q, ll w){
	for(int i=0; i<q; i++)
		tr[i] = max(tr[i], w);
}

int sol(ll q, ll w){
	ll c=0;
	for(int i=q; i<=w; i++)
		c = max(c, tr[i]);
	return c;
}

void solve(){
	ll m;
	cin >> n >> m;
	for(int i=1; i<=n; i++)
		cin >> a[i];
	vector<ll>s;
	for(int i=1; i<=m; i++){
		cin >> li[i] >> ri[i] >> ki[i];
		ad[ri[i]].push_back(i);
	}
	vector<bool>y(m+1);
	for(int i=1; i<=n; i++){
		while(!s.empty()){
			//cout << a[s.back()] << ' ';
			if(a[i]>=a[s.back()])
				s.pop_back();
			else
				break;	}
		ll p = (s.empty()? 0:s.back());
		//cout << a[p] << endl;
		add(p, a[p]+a[i]);
		for(auto u:ad[i])
			y[u] = (sol(li[u], ri[u])<=ki[u]);
		s.push_back(i);
		
	}
	//cout << 'u' << endl;
	for(int i=1; i<=m; i++)
		cout << y[i] << "\n";
}

int main()
{
	IOS;
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55080 KB Output is correct
2 Correct 32 ms 55124 KB Output is correct
3 Incorrect 23 ms 55152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55080 KB Output is correct
2 Correct 32 ms 55124 KB Output is correct
3 Incorrect 23 ms 55152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3012 ms 76844 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 3029 ms 58384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55080 KB Output is correct
2 Correct 32 ms 55124 KB Output is correct
3 Incorrect 23 ms 55152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 55080 KB Output is correct
2 Correct 32 ms 55124 KB Output is correct
3 Incorrect 23 ms 55152 KB Output isn't correct
4 Halted 0 ms 0 KB -