oj.uz

Submission #898116

# Submission time Handle Problem Language Result Execution time Memory
898116 2024-01-04T10:29:16 Z Litusiano Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
21 / 100
 3000 ms 216380 KB 
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'

struct MST{
	int n;
	vector<vector<int>> seg;
	void init(int n1){
		n = 1;
		while(n < n1) n*=2;
		seg.assign(2*n, vector<int>());
	}
 
	void merge(int i, int j, int k){
		int l = 0;
		int r = 0;
		while(l < seg[j].size() && r < seg[k].size()){
			if(seg[j][l] < seg[k][r]){
				seg[i].push_back(seg[j][l]); l++;
			}
			else{
				seg[i].push_back(seg[k][r]); r++;
			}
		}
		while(l < seg[j].size()){
			seg[i].push_back(seg[j][l]); l++;
		}
		while(r < seg[k].size()){
			seg[i].push_back(seg[k][r]); r++;
		}
	}
 
	void build(vector<int> v){
		for(int i = n; i < 2*n; i++){
			if(i-n >= v.size()) seg[i].push_back(0);
			else seg[i].push_back(v[i-n]);
		}
		for(int i = n-1; i>=0; i--){
			merge(i,2*i, 2*i+1);
		}
	}
 
	int query(int ql, int qr, int v, int k, int l, int r){
		if(r < ql || l > qr) return 0;
		if(ql <= l && r<= qr){
			auto it = lower_bound(seg[k].begin(),seg[k].end(), v);
			if(it == seg[k].begin()) return 0;
			return *(it-1);
		}
		int m = (l+r) / 2;
		int x = query(ql, qr, v, 2*k, l ,m);
		int y = query(ql, qr, v, 2*k+1, m+1 ,r);
		return max(x,y);
	}
 
	int query(int ql, int qr, int v){
		return query(ql, qr, v, 1, 0, n-1);
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
  int n,q; cin>>n>>q;
  vector<int> v(n); for(int& i : v) cin>>i;
  vector<int> pre(n+1);
 	for(int i = 1; i<n; i++){
  	pre[i+1] = pre[i] + (v[i] < v[i-1]); 
  }
  MST seg; seg.init(n); seg.build(v);
  while(q--){
  	int l,r,k; cin>>l>>r>>k;
  	if(n > 6000){
  		if(pre[r] - pre[l] == 0) cout<<1<<endl;
  		else cout<<0<<endl;
  	}
  	else{
  		l--; r--;
  		int mx = 0;
	  	for(int i = l; i < r; i++){
	  		// cerr<<i+1<<" "<<r<<endl;
	  		// cerr<<"QUERY: "<<i<<" "<< seg.query(i+1,r,v[i])<<endl;
	  		int x = seg.query(i+1,r,v[i]);
	  		if(!x) continue;
	  		mx = max(mx, v[i] + x);
	  	}
	  	if(mx > k) cout<<0<<endl;
	  	else cout<<1<<endl;
  	}
  	
  	
  }
}

Compilation message

sortbooks.cpp: In member function 'void MST::merge(int, int, int)':
sortbooks.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while(l < seg[j].size() && r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:18:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while(l < seg[j].size() && r < seg[k].size()){
      |                              ~~^~~~~~~~~~~~~~~
sortbooks.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   while(l < seg[j].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   while(r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'void MST::build(std::vector<int>)':
sortbooks.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    if(i-n >= v.size()) seg[i].push_back(0);
      |       ~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 348 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 6 ms 508 KB Output is correct
10 Correct 21 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 348 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 6 ms 508 KB Output is correct
10 Correct 21 ms 348 KB Output is correct
11 Correct 377 ms 828 KB Output is correct
12 Correct 1581 ms 1892 KB Output is correct
13 Correct 1822 ms 2152 KB Output is correct
14 Execution timed out 3015 ms 1952 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 211876 KB Output is correct
2 Correct 673 ms 215988 KB Output is correct
3 Correct 828 ms 216380 KB Output is correct
4 Correct 749 ms 216316 KB Output is correct
5 Correct 607 ms 216036 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 348 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 6 ms 508 KB Output is correct
10 Correct 21 ms 348 KB Output is correct
11 Correct 377 ms 828 KB Output is correct
12 Correct 1581 ms 1892 KB Output is correct
13 Correct 1822 ms 2152 KB Output is correct
14 Execution timed out 3015 ms 1952 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 348 KB Output is correct
7 Correct 16 ms 348 KB Output is correct
8 Correct 23 ms 348 KB Output is correct
9 Correct 6 ms 508 KB Output is correct
10 Correct 21 ms 348 KB Output is correct
11 Correct 377 ms 828 KB Output is correct
12 Correct 1581 ms 1892 KB Output is correct
13 Correct 1822 ms 2152 KB Output is correct
14 Execution timed out 3015 ms 1952 KB Time limit exceeded
15 Halted 0 ms 0 KB -