oj.uz

Submission #683422

# Submission time Handle Problem Language Result Execution time Memory
683422 2023-01-18T11:00:10 Z NotLinux Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 135008 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
#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 {
    node tree[4*N];
	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,N,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,N,pos,val);
	}
};
signed main(){
	etkisiz.answer = 0;
	etkisiz.v = {};
	int n,m;cin >> n >> m;
    int arr[n];
    for(int i = 0;i<n;i++)cin >> arr[i];
	SEGMENT_TREE segt;
	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 ) << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125420 KB Output is correct
2 Correct 67 ms 125516 KB Output is correct
3 Correct 77 ms 125572 KB Output is correct
4 Correct 75 ms 125516 KB Output is correct
5 Correct 81 ms 125516 KB Output is correct
6 Correct 109 ms 125608 KB Output is correct
7 Correct 104 ms 125680 KB Output is correct
8 Correct 119 ms 125592 KB Output is correct
9 Correct 85 ms 125628 KB Output is correct
10 Correct 118 ms 125644 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125420 KB Output is correct
2 Correct 67 ms 125516 KB Output is correct
3 Correct 77 ms 125572 KB Output is correct
4 Correct 75 ms 125516 KB Output is correct
5 Correct 81 ms 125516 KB Output is correct
6 Correct 109 ms 125608 KB Output is correct
7 Correct 104 ms 125680 KB Output is correct
8 Correct 119 ms 125592 KB Output is correct
9 Correct 85 ms 125628 KB Output is correct
10 Correct 118 ms 125644 KB Output is correct
11 Correct 505 ms 126124 KB Output is correct
12 Correct 2595 ms 127080 KB Output is correct
13 Correct 2847 ms 127092 KB Output is correct
14 Execution timed out 3074 ms 127176 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 135008 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 3063 ms 127988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125420 KB Output is correct
2 Correct 67 ms 125516 KB Output is correct
3 Correct 77 ms 125572 KB Output is correct
4 Correct 75 ms 125516 KB Output is correct
5 Correct 81 ms 125516 KB Output is correct
6 Correct 109 ms 125608 KB Output is correct
7 Correct 104 ms 125680 KB Output is correct
8 Correct 119 ms 125592 KB Output is correct
9 Correct 85 ms 125628 KB Output is correct
10 Correct 118 ms 125644 KB Output is correct
11 Correct 505 ms 126124 KB Output is correct
12 Correct 2595 ms 127080 KB Output is correct
13 Correct 2847 ms 127092 KB Output is correct
14 Execution timed out 3074 ms 127176 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 125420 KB Output is correct
2 Correct 67 ms 125516 KB Output is correct
3 Correct 77 ms 125572 KB Output is correct
4 Correct 75 ms 125516 KB Output is correct
5 Correct 81 ms 125516 KB Output is correct
6 Correct 109 ms 125608 KB Output is correct
7 Correct 104 ms 125680 KB Output is correct
8 Correct 119 ms 125592 KB Output is correct
9 Correct 85 ms 125628 KB Output is correct
10 Correct 118 ms 125644 KB Output is correct
11 Correct 505 ms 126124 KB Output is correct
12 Correct 2595 ms 127080 KB Output is correct
13 Correct 2847 ms 127092 KB Output is correct
14 Execution timed out 3074 ms 127176 KB Time limit exceeded
15 Halted 0 ms 0 KB -