oj.uz

Submission #342799

# Submission time Handle Problem Language Result Execution time Memory
342799 2021-01-02T20:42:15 Z Tosic Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 1717 ms 54380 KB 
#include <bits/stdc++.h>
#define maxn 4000010
using namespace std;

int n, m, a[maxn], ans;

struct node
{
	int maxS, minS, res;
	node(){
		maxS = 0;
		minS = 1e9+10;
		res = 0;
	}
};

node segTree[maxn];

void init(int idx, int l, int r){
	if(l == r){
		segTree[idx].maxS = segTree[idx].minS = a[l];
		return;
	}
	int mid = (r+l)/2;
	init(idx*2+1, l, mid);
	init(idx*2+2, mid+1, r);
	segTree[idx].maxS = max(segTree[idx*2+1].maxS, segTree[idx*2+2].maxS);
	segTree[idx].minS = min(segTree[idx*2+1].minS, segTree[idx*2+2].minS);
	segTree[idx].res = max(segTree[idx*2+1].res, segTree[idx*2+2].res);
	if(segTree[idx*2+1].maxS > segTree[idx*2+2].minS){
		segTree[idx].res = max(segTree[idx*2+1].maxS+segTree[idx*2+2].minS, segTree[idx].res);
	}

}

node query(int idx, int l, int r, int ql, int qr){
	if(l >= ql and r <= qr){
		return segTree[idx];
	}
	if(l > qr or r<ql){
		node tmp;
		return tmp;
	}
	int mid = (l+r)/2;
	node a = query(idx*2+1, l, mid, ql, qr);
	node b = query(idx*2+2, mid+1 ,r, ql, qr);
	node c;
	c.maxS = max(a.maxS, b.maxS);
	c.minS = min(a.minS, b.minS);
	c.res = max(a.res, b.res);
	if(a.maxS > b.minS){ c.res = max(c.res, a.maxS+b.minS);}
	return c;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	init(0, 0, n-1);
	for(int i = 0; i < m; ++i){
		int l,r,k;
		cin>>l>>r>>k;
		--l, --r;
		if(l == r){
			cout << "1\n";
			continue;
		}
		if(n <= 5000){
			int tmp = 0,res = 0;
			for(int i=l; i <= r; ++i){
				if(tmp > a[i]){
					res = max(res, tmp+a[i]);
				}
				
				tmp = max(tmp, a[i]);
			}
			cout << (res<=k) << '\n';
			continue;
		}
		//cerr << query(0,0,n-1,l,r).res << '\n';
		cout << (query(0, 0, n-1, l, r).res <= k) << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 29 ms 47340 KB Output is correct
4 Correct 31 ms 47340 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 29 ms 47340 KB Output is correct
7 Correct 29 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 30 ms 47340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 29 ms 47340 KB Output is correct
4 Correct 31 ms 47340 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 29 ms 47340 KB Output is correct
7 Correct 29 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 30 ms 47340 KB Output is correct
11 Correct 34 ms 47340 KB Output is correct
12 Correct 36 ms 47468 KB Output is correct
13 Correct 37 ms 47468 KB Output is correct
14 Correct 42 ms 47596 KB Output is correct
15 Correct 44 ms 47468 KB Output is correct
16 Correct 50 ms 47468 KB Output is correct
17 Correct 50 ms 47468 KB Output is correct
18 Correct 49 ms 47468 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 53324 KB Output is correct
2 Correct 1717 ms 53296 KB Output is correct
3 Correct 1698 ms 53304 KB Output is correct
4 Correct 1712 ms 53332 KB Output is correct
5 Correct 1662 ms 53356 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 47852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 29 ms 47340 KB Output is correct
4 Correct 31 ms 47340 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 29 ms 47340 KB Output is correct
7 Correct 29 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 30 ms 47340 KB Output is correct
11 Correct 34 ms 47340 KB Output is correct
12 Correct 36 ms 47468 KB Output is correct
13 Correct 37 ms 47468 KB Output is correct
14 Correct 42 ms 47596 KB Output is correct
15 Correct 44 ms 47468 KB Output is correct
16 Correct 50 ms 47468 KB Output is correct
17 Correct 50 ms 47468 KB Output is correct
18 Correct 49 ms 47468 KB Output is correct
19 Incorrect 314 ms 54380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct
3 Correct 29 ms 47340 KB Output is correct
4 Correct 31 ms 47340 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 29 ms 47340 KB Output is correct
7 Correct 29 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 30 ms 47340 KB Output is correct
11 Correct 34 ms 47340 KB Output is correct
12 Correct 36 ms 47468 KB Output is correct
13 Correct 37 ms 47468 KB Output is correct
14 Correct 42 ms 47596 KB Output is correct
15 Correct 44 ms 47468 KB Output is correct
16 Correct 50 ms 47468 KB Output is correct
17 Correct 50 ms 47468 KB Output is correct
18 Correct 49 ms 47468 KB Output is correct
19 Correct 1699 ms 53324 KB Output is correct
20 Correct 1717 ms 53296 KB Output is correct
21 Correct 1698 ms 53304 KB Output is correct
22 Correct 1712 ms 53332 KB Output is correct
23 Correct 1662 ms 53356 KB Output is correct
24 Incorrect 145 ms 47852 KB Output isn't correct
25 Halted 0 ms 0 KB -