oj.uz

Submission #1092678

# Submission time Handle Problem Language Result Execution time Memory
1092678 2024-09-24T18:09:27 Z 4QT0R Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 669 ms 143996 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct query{
	ll x;
	ll y;
	ll k;
	ll ind;
	ll type;
};

ll wej[1000003];
vector<query> ev;

const ll base=1<<20;
ll tree[2*base];
void update(ll v, ll x){
	v+=base;
	if (tree[v]>=x)return;
	tree[v]=x;
	v>>=1;
	while(v){
		tree[v]=max(tree[2*v],tree[2*v+1]);
		v>>=1;
	}
}
ll check(ll p){
	ll ans=0;
	p+=base-1;
	while(p/2){
		if (p&1)ans=max(ans,tree[p-1]);
		p>>=1;
	}
	return ans;
}
ll odpow[1000003];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,m;
	cin >> n >> m;
	stack<pair<ll,ll>> st;
	for (ll i = 1; i<=n; i++){
		cin >> wej[i];
		while(st.size() && st.top().first<=wej[i])st.pop();
		if (st.size())ev.push_back({st.top().second,i,st.top().first+wej[i],i,0});
		st.push({wej[i],i});
	}
	for (ll i = 1,a,b,c; i<=m; i++){
		cin >> a >> b >> c;
		ev.push_back({a,b,c,i,1});
	}
	sort(ev.begin(),ev.end(),[](query a, query b){return a.x==b.x?a.type<b.type:a.x>b.x;});
	for (ll i = 0; i<ev.size(); i++){
		if (ev[i].type)odpow[ev[i].ind]=check(ev[i].y)<=ev[i].k;
		else update(ev[i].y,ev[i].k);
	}
	for (ll i = 1; i<=m; i++)cout << odpow[i] << '\n';
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (ll i = 0; i<ev.size(); i++){
      |                 ~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 13768 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -