oj.uz

Submission #683429

# Submission time Handle Problem Language Result Execution time Memory
683429 2023-01-18T11:20:09 Z NotLinux Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 136856 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 448 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 448 KB Output is correct
11 Correct 72 ms 820 KB Output is correct
12 Correct 248 ms 2200 KB Output is correct
13 Correct 267 ms 2272 KB Output is correct
14 Correct 390 ms 2240 KB Output is correct
15 Correct 340 ms 2248 KB Output is correct
16 Correct 307 ms 2332 KB Output is correct
17 Correct 138 ms 1520 KB Output is correct
18 Correct 310 ms 2248 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3100 ms 136856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 18892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 448 KB Output is correct
11 Correct 72 ms 820 KB Output is correct
12 Correct 248 ms 2200 KB Output is correct
13 Correct 267 ms 2272 KB Output is correct
14 Correct 390 ms 2240 KB Output is correct
15 Correct 340 ms 2248 KB Output is correct
16 Correct 307 ms 2332 KB Output is correct
17 Correct 138 ms 1520 KB Output is correct
18 Correct 310 ms 2248 KB Output is correct
19 Execution timed out 3098 ms 31560 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 448 KB Output is correct
11 Correct 72 ms 820 KB Output is correct
12 Correct 248 ms 2200 KB Output is correct
13 Correct 267 ms 2272 KB Output is correct
14 Correct 390 ms 2240 KB Output is correct
15 Correct 340 ms 2248 KB Output is correct
16 Correct 307 ms 2332 KB Output is correct
17 Correct 138 ms 1520 KB Output is correct
18 Correct 310 ms 2248 KB Output is correct
19 Execution timed out 3100 ms 136856 KB Time limit exceeded
20 Halted 0 ms 0 KB -