Submission #1092688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092688		4QT0R	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	726 ms	145684 KiB

sortbooks

#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 (stderr)

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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23