oj.uz

Submission #526503

# Submission time Handle Problem Language Result Execution time Memory
526503 2022-02-15T04:24:00 Z CursedCode Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 262148 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
long long a[1000005];
long long tree[1000005];
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);
    std::merge(s[id*2].begin(), s[id*2].end(),
                s[id*2+1].begin(), s[id*2+1].end(),
                std::inserter(s[id], s[id].begin()));
    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) {
		if(*s[id].begin() >= itr) return 0;
		c = s[id].lower_bound(itr);
		c--;
		return *c;
	}
	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:56:12: warning: unused variable 'type' [-Wunused-variable]
   56 |        int type, l, r, x;
      |            ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 50 ms 94148 KB Output is correct
3 Correct 46 ms 94272 KB Output is correct
4 Correct 51 ms 94248 KB Output is correct
5 Correct 43 ms 94284 KB Output is correct
6 Correct 62 ms 94444 KB Output is correct
7 Correct 61 ms 94360 KB Output is correct
8 Correct 70 ms 94404 KB Output is correct
9 Correct 54 ms 94224 KB Output is correct
10 Correct 68 ms 94220 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 50 ms 94148 KB Output is correct
3 Correct 46 ms 94272 KB Output is correct
4 Correct 51 ms 94248 KB Output is correct
5 Correct 43 ms 94284 KB Output is correct
6 Correct 62 ms 94444 KB Output is correct
7 Correct 61 ms 94360 KB Output is correct
8 Correct 70 ms 94404 KB Output is correct
9 Correct 54 ms 94224 KB Output is correct
10 Correct 68 ms 94220 KB Output is correct
11 Correct 354 ms 95080 KB Output is correct
12 Correct 1075 ms 97524 KB Output is correct
13 Correct 1217 ms 97660 KB Output is correct
14 Correct 2060 ms 97680 KB Output is correct
15 Correct 2044 ms 97804 KB Output is correct
16 Execution timed out 3084 ms 97624 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 765 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 50 ms 94148 KB Output is correct
3 Correct 46 ms 94272 KB Output is correct
4 Correct 51 ms 94248 KB Output is correct
5 Correct 43 ms 94284 KB Output is correct
6 Correct 62 ms 94444 KB Output is correct
7 Correct 61 ms 94360 KB Output is correct
8 Correct 70 ms 94404 KB Output is correct
9 Correct 54 ms 94224 KB Output is correct
10 Correct 68 ms 94220 KB Output is correct
11 Correct 354 ms 95080 KB Output is correct
12 Correct 1075 ms 97524 KB Output is correct
13 Correct 1217 ms 97660 KB Output is correct
14 Correct 2060 ms 97680 KB Output is correct
15 Correct 2044 ms 97804 KB Output is correct
16 Execution timed out 3084 ms 97624 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 50 ms 94148 KB Output is correct
3 Correct 46 ms 94272 KB Output is correct
4 Correct 51 ms 94248 KB Output is correct
5 Correct 43 ms 94284 KB Output is correct
6 Correct 62 ms 94444 KB Output is correct
7 Correct 61 ms 94360 KB Output is correct
8 Correct 70 ms 94404 KB Output is correct
9 Correct 54 ms 94224 KB Output is correct
10 Correct 68 ms 94220 KB Output is correct
11 Correct 354 ms 95080 KB Output is correct
12 Correct 1075 ms 97524 KB Output is correct
13 Correct 1217 ms 97660 KB Output is correct
14 Correct 2060 ms 97680 KB Output is correct
15 Correct 2044 ms 97804 KB Output is correct
16 Execution timed out 3084 ms 97624 KB Time limit exceeded
17 Halted 0 ms 0 KB -