제출 #346609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346609		tengiz05	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3095 ms	240464 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,-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++;
	return t;
}
Node Merge(Node &l, Node &r){
	Node res;
	res.v = mrg(l.v,r.v);
	res.mx = max(l.mx, r.mx);
	res.ans = max(l.ans, r.ans);
	int p = lower_bound(all(r.v), l.mx)-r.v.begin();p--;
	res.ans = max(res.ans, l.mx+r.v[p]);
	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)ans = max(t[x].ans, ans);
	for(int i=0;i<(int)rel.size()-1;i++){
		mx = max(mx, t[rel[i]].mx);
		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;sz=n;
	for(i=0;i<n;i++){
		cin >> a[i];
		t[i+sz] = {a[i], 0, {-mod, -mod, a[i]}};
	}for(i=sz-1;i>0;i--)t[i] = Merge(t[i*2], t[i*2+1]);
	while(q--){
		int l, r;
		cin >> l >> r >> k;
		l--, r--;
		bool is = true;
		int m=0;
		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<int> mrg(std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  while(i<l.size() && j<r.size()){
      |                      ~^~~~~~~~~
sortbooks.cpp:34:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(i < l.size())t.pb(l[i]),i++;
      |        ~~^~~~~~~~~~
sortbooks.cpp:35:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while(j < r.size())t.pb(r[j]),j++;
      |        ~~^~~~~~~~~~
sortbooks.cpp: In function 'void solve(int)':
sortbooks.cpp:69:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   69 |  while(sz<n)sz<<=1;sz=n;
      |  ^~~~~
sortbooks.cpp:69:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   69 |  while(sz<n)sz<<=1;sz=n;
      |                    ^~
sortbooks.cpp:78:8: warning: unused variable 'is' [-Wunused-variable]
   78 |   bool is = true;
      |        ^~
sortbooks.cpp:79:7: warning: unused variable 'm' [-Wunused-variable]
   79 |   int m=0;
      |       ^
sortbooks.cpp:67:9: warning: unused variable 'j' [-Wunused-variable]
   67 |  int i, j, q;
      |         ^

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