oj.uz

Submission #898120

# Submission time Handle Problem Language Result Execution time Memory
898120 2024-01-04T10:35:21 Z Litusiano Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
21 / 100
 3000 ms 204988 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(l < seg[j].size() && r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:20:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while(l < seg[j].size() && r < seg[k].size()){
      |                              ~~^~~~~~~~~~~~~~~
sortbooks.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(l < seg[j].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'void MST::build(std::vector<int>)':
sortbooks.cpp:38:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    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 348 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 15 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 19 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 15 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 19 ms 348 KB Output is correct
11 Correct 352 ms 756 KB Output is correct
12 Correct 1481 ms 1796 KB Output is correct
13 Correct 1711 ms 1872 KB Output is correct
14 Correct 2848 ms 2048 KB Output is correct
15 Correct 2948 ms 2196 KB Output is correct
16 Execution timed out 3057 ms 1896 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 204988 KB Output is correct
2 Correct 656 ms 204424 KB Output is correct
3 Correct 697 ms 204272 KB Output is correct
4 Correct 707 ms 204560 KB Output is correct
5 Correct 573 ms 203508 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 23884 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 348 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 15 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 19 ms 348 KB Output is correct
11 Correct 352 ms 756 KB Output is correct
12 Correct 1481 ms 1796 KB Output is correct
13 Correct 1711 ms 1872 KB Output is correct
14 Correct 2848 ms 2048 KB Output is correct
15 Correct 2948 ms 2196 KB Output is correct
16 Execution timed out 3057 ms 1896 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 15 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 6 ms 600 KB Output is correct
10 Correct 19 ms 348 KB Output is correct
11 Correct 352 ms 756 KB Output is correct
12 Correct 1481 ms 1796 KB Output is correct
13 Correct 1711 ms 1872 KB Output is correct
14 Correct 2848 ms 2048 KB Output is correct
15 Correct 2948 ms 2196 KB Output is correct
16 Execution timed out 3057 ms 1896 KB Time limit exceeded
17 Halted 0 ms 0 KB -