oj.uz

Submission #682073

# Submission time Handle Problem Language Result Execution time Memory
682073 2023-01-15T15:17:11 Z dsyz Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1487 ms 207628 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e)>>1;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll val){
		if(s == e){
			v = max(v,val);
			return;
		}else{
			if(x > m) r -> update(x,val);
			else l -> update(x,val);
			v = max(l -> v,r -> v);
		}
	}
	ll rmaxq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmaxq(x,y);
			else if(y <= m) return l -> rmaxq(x,y);
			else return max(l -> rmaxq(x,m),r -> rmaxq(m + 1,y));
		}
	}
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	root = new node(0,N + 5);
	ll W[N];
	for(ll i = 0;i < N;i++){
		cin>>W[i];
	}
	vector<pair<pair<ll,ll>,pair<ll,ll> > > queries; //{{R,L},{K,ith query}}
	for(ll i = 0;i < M;i++){
		ll L,R,K;
		cin>>L>>R>>K;
		L--;
		R--;
		queries.push_back({{R,L},{K,i}});
	}
	sort(queries.begin(),queries.end());
	ll ans[M];
	memset(ans,-1,sizeof(ans));
	ll Rptr = -1;
	deque<pair<ll,ll> > dq;
	for(ll q = 0;q < queries.size();q++){
		ll L = queries[q].first.second;
		ll R = queries[q].first.first;
		ll K = queries[q].second.first;
		ll index = queries[q].second.second;
		while(Rptr < R){
			Rptr++;
			auto it = upper_bound(dq.begin(),dq.end(),make_pair(W[Rptr],ll(-1e18)));
			if(it != dq.end()){
				ll Wj = (*it).first;
				ll j = -1 * (*it).second;
				root -> update(j,Wj + W[Rptr]);
			}
			while(!dq.empty() && dq.front().first <= W[Rptr]){
				dq.pop_front();
			}
			dq.push_front(make_pair(W[Rptr],-Rptr));
		}
		ll maximum = root -> rmaxq(L,R);
		if(maximum <= K){
			ans[index] = 1;
		}else{
			ans[index] = 0;
		}
	}
	for(ll i = 0;i < M;i++){
		cout<<ans[i]<<'\n';
	}
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1425 ms 206424 KB Output is correct
2 Correct 1431 ms 207432 KB Output is correct
3 Correct 1375 ms 207368 KB Output is correct
4 Correct 1487 ms 207436 KB Output is correct
5 Incorrect 1300 ms 207628 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 19784 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Halted 0 ms 0 KB -