oj.uz

Submission #526559

# Submission time Handle Problem Language Result Execution time Memory
526559 2022-02-15T08:21:38 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;
vector<int>v[2000005];
vector<int>::iterator lower, upper;
void build(int id, int l, int r){
    if(l == r){
      tree[id] = a[l];
      v[id].push_back(a[l]);
      return ;
    }
    int m = (l + r) / 2;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    v[id].insert(v[id].end(), v[id*2].begin(), v[id*2].end());
    v[id].insert(v[id].end(), v[id*2+1].begin(), v[id*2+1].end());
    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;
		sort(v[id].begin(),v[id].end());
		if(*v[id].begin() >= itr) return 0;
    	lower = lower_bound(v[id].begin(), v[id].end(), itr);
    	lower--;
		return *lower;
	}
	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 'long long int up(long long int, long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:33:7: warning: unused variable 'k' [-Wunused-variable]
   33 |   int k = 0;
      |       ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:57:12: warning: unused variable 'type' [-Wunused-variable]
   57 |        int type, l, r, x;
      |            ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47244 KB Output is correct
2 Correct 24 ms 47268 KB Output is correct
3 Correct 27 ms 47252 KB Output is correct
4 Correct 25 ms 47180 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 47 ms 47364 KB Output is correct
7 Correct 44 ms 47308 KB Output is correct
8 Correct 60 ms 47240 KB Output is correct
9 Correct 39 ms 47256 KB Output is correct
10 Correct 52 ms 47300 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47244 KB Output is correct
2 Correct 24 ms 47268 KB Output is correct
3 Correct 27 ms 47252 KB Output is correct
4 Correct 25 ms 47180 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 47 ms 47364 KB Output is correct
7 Correct 44 ms 47308 KB Output is correct
8 Correct 60 ms 47240 KB Output is correct
9 Correct 39 ms 47256 KB Output is correct
10 Correct 52 ms 47300 KB Output is correct
11 Correct 409 ms 47584 KB Output is correct
12 Correct 1220 ms 48272 KB Output is correct
13 Correct 1383 ms 48404 KB Output is correct
14 Correct 2297 ms 48420 KB Output is correct
15 Correct 2309 ms 48332 KB Output is correct
16 Execution timed out 3043 ms 48364 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 791 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 3022 ms 69480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47244 KB Output is correct
2 Correct 24 ms 47268 KB Output is correct
3 Correct 27 ms 47252 KB Output is correct
4 Correct 25 ms 47180 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 47 ms 47364 KB Output is correct
7 Correct 44 ms 47308 KB Output is correct
8 Correct 60 ms 47240 KB Output is correct
9 Correct 39 ms 47256 KB Output is correct
10 Correct 52 ms 47300 KB Output is correct
11 Correct 409 ms 47584 KB Output is correct
12 Correct 1220 ms 48272 KB Output is correct
13 Correct 1383 ms 48404 KB Output is correct
14 Correct 2297 ms 48420 KB Output is correct
15 Correct 2309 ms 48332 KB Output is correct
16 Execution timed out 3043 ms 48364 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47244 KB Output is correct
2 Correct 24 ms 47268 KB Output is correct
3 Correct 27 ms 47252 KB Output is correct
4 Correct 25 ms 47180 KB Output is correct
5 Correct 25 ms 47188 KB Output is correct
6 Correct 47 ms 47364 KB Output is correct
7 Correct 44 ms 47308 KB Output is correct
8 Correct 60 ms 47240 KB Output is correct
9 Correct 39 ms 47256 KB Output is correct
10 Correct 52 ms 47300 KB Output is correct
11 Correct 409 ms 47584 KB Output is correct
12 Correct 1220 ms 48272 KB Output is correct
13 Correct 1383 ms 48404 KB Output is correct
14 Correct 2297 ms 48420 KB Output is correct
15 Correct 2309 ms 48332 KB Output is correct
16 Execution timed out 3043 ms 48364 KB Time limit exceeded
17 Halted 0 ms 0 KB -