oj.uz

Submission #683420

# Submission time Handle Problem Language Result Execution time Memory
683420 2023-01-18T10:53:04 Z NotLinux Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 135088 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))});
        for(auto itr : a.v){
            product.v.push_back(itr);
        }
        for(auto itr : b.v){
            product.v.push_back(itr);
        }
        sort(product.v.begin() , product.v.end());
        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;
	}
}

Subtask #1
8.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 4 ms 384 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 14 ms 428 KB Output is correct
8 Correct 10 ms 456 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 7 ms 468 KB Output is correct

Subtask #2
9.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 4 ms 384 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 14 ms 428 KB Output is correct
8 Correct 10 ms 456 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 170 ms 928 KB Output is correct
12 Correct 927 ms 2200 KB Output is correct
13 Correct 965 ms 2308 KB Output is correct
14 Correct 1389 ms 2196 KB Output is correct
15 Correct 1346 ms 2244 KB Output is correct
16 Correct 861 ms 2248 KB Output is correct
17 Correct 530 ms 1600 KB Output is correct
18 Correct 493 ms 2252 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 135088 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 3093 ms 15592 KB Time limit exceeded
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 4 ms 384 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 14 ms 428 KB Output is correct
8 Correct 10 ms 456 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 170 ms 928 KB Output is correct
12 Correct 927 ms 2200 KB Output is correct
13 Correct 965 ms 2308 KB Output is correct
14 Correct 1389 ms 2196 KB Output is correct
15 Correct 1346 ms 2244 KB Output is correct
16 Correct 861 ms 2248 KB Output is correct
17 Correct 530 ms 1600 KB Output is correct
18 Correct 493 ms 2252 KB Output is correct
19 Execution timed out 3091 ms 28904 KB Time limit exceeded
20 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 4 ms 384 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 14 ms 468 KB Output is correct
7 Correct 14 ms 428 KB Output is correct
8 Correct 10 ms 456 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 170 ms 928 KB Output is correct
12 Correct 927 ms 2200 KB Output is correct
13 Correct 965 ms 2308 KB Output is correct
14 Correct 1389 ms 2196 KB Output is correct
15 Correct 1346 ms 2244 KB Output is correct
16 Correct 861 ms 2248 KB Output is correct
17 Correct 530 ms 1600 KB Output is correct
18 Correct 493 ms 2252 KB Output is correct
19 Execution timed out 3078 ms 135088 KB Time limit exceeded
20 Halted 0 ms 0 KB -