oj.uz

Submission #526504

# Submission time Handle Problem Language Result Execution time Memory
526504 2022-02-15T04:29:18 Z CursedCode Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
long long a[1000005];
long long tree[1000005],i;
long long row;
set<int>s[2000005];
set<int>::iterator c;
void build(int id, int l, int r){
    if(l == r){
      tree[id] = a[l];
      s[id].insert(a[l]);
      return ;
    }
    int m = (l + r) / 2;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    tree[id] = max(tree[id * 2] ,tree[id * 2 + 1]);
}
long long query(int id, int L, int R, int l, int r){
	if(R < l || r < L) return 0;
	if(l <= L && R <= r) {
		return tree[id];
	}
	return max(query(id * 2, L, (L + R) / 2, l, r) ,query(id * 2 + 1, (L + R) / 2 + 1, R, l, r));
}
long long up(int id, int L, int R, int l, int r, int itr){
	if(R < l || r < L) return 0;
	if(l <= L && R <= r) {
		int k = 0;
		for(i = L;i <= R;i++){
			if(a[i] < itr) k = max(k,a[i]);
		} 
		if(k == 0) return 0;
		return k;
	}
	return max(up(id * 2, L, (L + R) / 2, l, r, itr) ,up(id * 2 + 1, (L + R) / 2 + 1, R, l, r, itr));
}
long long sit(int l, int r){
    int m = (l + r) / 2;
    if(l == r) return 0;
    int x = query(1,1,n,l,m);
    long long k = up(1,1,n,m+1,r,x);
    if(k == 0) return max(sit(l, m) , sit(m+1, r)); 
	return max(sit(l, m) , max(sit(m+1, r) , k + x));
}
signed main(){
  	int Q;
  	cin >> n;
  	cin >> Q;
  	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	while(Q--){
      	int type, l, r, x;
      	cin >> l >> r >> x;
      	if(sit(l,r) > x) cout << '0' << endl;
      	else cout << '1' << endl;
  	}
  	return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:12: warning: unused variable 'type' [-Wunused-variable]
   55 |        int type, l, r, x;
      |            ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94148 KB Output is correct
2 Correct 40 ms 94152 KB Output is correct
3 Correct 46 ms 94140 KB Output is correct
4 Correct 43 ms 94156 KB Output is correct
5 Correct 46 ms 94228 KB Output is correct
6 Correct 70 ms 94264 KB Output is correct
7 Correct 58 ms 94284 KB Output is correct
8 Correct 77 ms 94224 KB Output is correct
9 Correct 51 ms 94232 KB Output is correct
10 Correct 67 ms 94244 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94148 KB Output is correct
2 Correct 40 ms 94152 KB Output is correct
3 Correct 46 ms 94140 KB Output is correct
4 Correct 43 ms 94156 KB Output is correct
5 Correct 46 ms 94228 KB Output is correct
6 Correct 70 ms 94264 KB Output is correct
7 Correct 58 ms 94284 KB Output is correct
8 Correct 77 ms 94224 KB Output is correct
9 Correct 51 ms 94232 KB Output is correct
10 Correct 67 ms 94244 KB Output is correct
11 Correct 364 ms 94408 KB Output is correct
12 Correct 1018 ms 94716 KB Output is correct
13 Correct 1217 ms 94728 KB Output is correct
14 Correct 1978 ms 94776 KB Output is correct
15 Correct 2074 ms 94776 KB Output is correct
16 Execution timed out 3066 ms 94728 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 584 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94148 KB Output is correct
2 Correct 40 ms 94152 KB Output is correct
3 Correct 46 ms 94140 KB Output is correct
4 Correct 43 ms 94156 KB Output is correct
5 Correct 46 ms 94228 KB Output is correct
6 Correct 70 ms 94264 KB Output is correct
7 Correct 58 ms 94284 KB Output is correct
8 Correct 77 ms 94224 KB Output is correct
9 Correct 51 ms 94232 KB Output is correct
10 Correct 67 ms 94244 KB Output is correct
11 Correct 364 ms 94408 KB Output is correct
12 Correct 1018 ms 94716 KB Output is correct
13 Correct 1217 ms 94728 KB Output is correct
14 Correct 1978 ms 94776 KB Output is correct
15 Correct 2074 ms 94776 KB Output is correct
16 Execution timed out 3066 ms 94728 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94148 KB Output is correct
2 Correct 40 ms 94152 KB Output is correct
3 Correct 46 ms 94140 KB Output is correct
4 Correct 43 ms 94156 KB Output is correct
5 Correct 46 ms 94228 KB Output is correct
6 Correct 70 ms 94264 KB Output is correct
7 Correct 58 ms 94284 KB Output is correct
8 Correct 77 ms 94224 KB Output is correct
9 Correct 51 ms 94232 KB Output is correct
10 Correct 67 ms 94244 KB Output is correct
11 Correct 364 ms 94408 KB Output is correct
12 Correct 1018 ms 94716 KB Output is correct
13 Correct 1217 ms 94728 KB Output is correct
14 Correct 1978 ms 94776 KB Output is correct
15 Correct 2074 ms 94776 KB Output is correct
16 Execution timed out 3066 ms 94728 KB Time limit exceeded
17 Halted 0 ms 0 KB -