Submission #683429

#	Time	Username	Problem	Language	Result	Execution time	Memory
683429		NotLinux	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3100 ms	136856 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
const int inf = 1e18;
struct node {
	int answer;
	vector < int > v;
	int smaller(int x){
		auto it = (lower_bound(v.begin(),v.end(),x));
		if(it == v.begin() or v.size() == 0)return -inf;
		else return *(--it);
	}
};
node merge(node a , node b){
        node product;
        product.answer = max({a.answer , b.answer , a.smaller(1e18) + b.smaller(a.smaller(1e18))});
        int itr1 = 0 , itr2 = 0;
        while(itr1 < a.v.size() or itr2 < b.v.size()){
        	if(itr1 == a.v.size()){
        		product.v.push_back(b.v[itr2]);
        		itr2++;
        	}
        	else if(itr2 == b.v.size()){
        		product.v.push_back(a.v[itr1]);
        		itr1++;
        	}
        	else{
        		if(a.v[itr1] < b.v[itr2]){
        			product.v.push_back(a.v[itr1]);
        			itr1++;
        		}
        		else{
        			product.v.push_back(b.v[itr2]);
        			itr2++;
        		}
        	}
        }
        return product;
}
node etkisiz;
struct SEGMENT_TREE {
	vector < node > tree;
	int sz;
	void init(int x){
		sz = x;
		tree.clear();tree.resize(4*x);
	}
	node _query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return etkisiz;
		return merge(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
	}
	int query(int l , int r){
		return _query(1,1,sz,l,r).answer;
	}
	void _update(int ind , int l, int r , int pos , int val){
		if(l == r){
			tree[ind].answer = 0;
			tree[ind].v = {val};
			return;
		}
		if(pos <= mid)_update(ind*2,l,mid,pos,val);
		else _update(ind*2+1,mid+1,r,pos,val);
		tree[ind] = merge(tree[ind*2],tree[ind*2+1]);
	}
	void update(int pos , int val){
		_update(1,1,sz,pos,val);
	}
};
signed main(){
	etkisiz.answer = 0;
	etkisiz.v = {};
	int n,m;cin >> n >> m;
	vector < int > arr(n);
	for(auto &inp : arr)cin >> inp;
	SEGMENT_TREE segt;
	segt.init(n);
	for(int i = 1;i<=n;i++){
		segt.update(i,arr[i-1]);
	}
	while(m--){
		int cl,cr,cw;cin >> cl >> cr >> cw;
		cout << ( segt.query(cl,cr) > cw ? "0" : "1" ) << endl;
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'node merge(node, node)':
sortbooks.cpp:19:20: 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]
   19 |         while(itr1 < a.v.size() or itr2 < b.v.size()){
      |               ~~~~~^~~~~~~~~~~~
sortbooks.cpp:19:41: 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]
   19 |         while(itr1 < a.v.size() or itr2 < b.v.size()){
      |                                    ~~~~~^~~~~~~~~~~~
sortbooks.cpp:20:18: 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]
   20 |          if(itr1 == a.v.size()){
      |             ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:24: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]
   24 |          else if(itr2 == b.v.size()){
      |                  ~~~~~^~~~~~~~~~~~~

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