제출 #335856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335856		tengiz05	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	559 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 1e6+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, k, sz=1;
struct Node{
	int mx, ans;
	vector<int> v;
};
Node t[1<<21];
vector<int> mrg(vector<int> &l, vector<int> &r){
	vector<int> t={-mod};
	int i=0, j=0;
	while(i<l.size() && j<r.size()){
		if(l[i] <= r[j]){
			if(l[i]!=-mod)t.pb(l[i]);
			i++;
		}else {
			if(r[j]!=-mod)t.pb(r[j]);
			j++;
		}
	}
	while(i < l.size())t.pb(l[i]),i++;
	while(j < r.size())t.pb(r[j]),j++;
//	cout << "ans = ";for(auto x : t)cout << x << ' ';cout << '\n';
	return t;
}
Node Merge(Node &l, Node &r){
	Node res;
	res.v = mrg(l.v,r.v);
	res.mx = max(l.mx, r.mx);
	
	return res;
}

int get(int l, int r){
	vector<int> rel, rer;
	for(l+=sz,r+=sz;l<=r;l>>=1,r>>=1){
		if(l%2==1)rel.pb(l++);
		if(r%2==0)rer.pb(r--);
	}reverse(all(rer));
	for(auto x : rer)rel.pb(x);
	int mx = 0 ;
	int ans = 0;
/*	for(auto x : rel){
		cout << t[x].mx << ' ';
	}cout << '\n';*/
	for(int i=0;i<(int)rel.size()-1;i++){
		mx = max(mx, rel[i]);
		int pos = lower_bound(all(t[rel[i+1]].v), mx)-t[rel[i+1]].v.begin();
		pos--;
		ans = max(ans, t[rel[i+1]].v[pos]+mx);
	}return ans;
}

void solve(int test_case){
	int i, j, q;
	cin >> n >> q;
	while(sz<n)sz<<=1;
	for(i=0;i<n;i++){
		cin >> a[i];
		t[i+sz] = {a[i], 0, {-mod, a[i]}};
	}for(i=sz-1;i>0;i--)t[i] = Merge(t[i*2], t[i*2+1]);
//	for(auto x : t[1].v)cout << x << ' ';cout << '\n';
	while(q--){
		int l, r;
		cin >> l >> r >> k;
		l--, r--;
		int ans = get(l,r);
		if(ans <= k){
			cout << 1 << '\n';
		}else {
			cout << 0 << '\n';
		}
	}
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'std::vector<long long int> mrg(std::vector<long long int>&, std::vector<long long int>&)':
sortbooks.cpp:23:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  while(i<l.size() && j<r.size()){
      |        ~^~~~~~~~~
sortbooks.cpp:23:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  while(i<l.size() && j<r.size()){
      |                      ~^~~~~~~~~
sortbooks.cpp:32:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  while(i < l.size())t.pb(l[i]),i++;
      |        ~~^~~~~~~~~~
sortbooks.cpp:33:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while(j < r.size())t.pb(r[j]),j++;
      |        ~~^~~~~~~~~~
sortbooks.cpp: In function 'void solve(long long int)':
sortbooks.cpp:66:9: warning: unused variable 'j' [-Wunused-variable]
   66 |  int i, j, q;
      |         ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23