oj.uz

Submission #493199

# Submission time Handle Problem Language Result Execution time Memory
493199 2021-12-10T10:45:08 Z irmuun Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
21 / 100
 3000 ms 22180 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.14159265359
int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	ll n,m,w[1000001],h[1000001],l,r,k,ans,i,j,b,c,mn=1e9,a;
	vector<ll>v;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>w[i];
		if(i>1){
			if(w[i-1]>w[i]){
				v.pb(i);
			}
		}
		mn=min(mn,w[i]);
		h[i]=w[i];
	}
	for(i=1;i<=m;i++){
		cin>>l>>r>>k;
		if(k<mn){
			if(v.size()==0){
				cout<<1<<endl;
				continue;
			}
			if(v[v.size()-1]<=l){
				cout<<0<<endl;
				continue;
			}
			a=upper_bound(v.begin(),v.end(),l)-v.begin();
			if(l<v[a]&&v[a]<=r){
				cout<<0<<endl;
			}
			else{
				cout<<1<<endl;
			}
			continue;
		}
		c=0;
		while(c==0){
			c=1;
			for(j=l;j<r;j++){
				if(w[j]+w[j+1]<=k&&w[j]>w[j+1]){
					c=0;
					swap(w[j],w[j+1]);
				}
			}
		}
		c=1;
		for(j=l;j<r;j++){
			if(w[j]>w[j+1]){
				c=0;
				break;
			}
		}
		cout<<c<<endl;
		for(j=l;j<=r;j++){
			w[j]=h[j];
		}
	}
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:12:37: warning: unused variable 'ans' [-Wunused-variable]
   12 |  ll n,m,w[1000001],h[1000001],l,r,k,ans,i,j,b,c,mn=1e9,a;
      |                                     ^~~
sortbooks.cpp:12:45: warning: unused variable 'b' [-Wunused-variable]
   12 |  ll n,m,w[1000001],h[1000001],l,r,k,ans,i,j,b,c,mn=1e9,a;
      |                                             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 16000 KB Output is correct
3 Correct 9 ms 15848 KB Output is correct
4 Correct 7 ms 15884 KB Output is correct
5 Correct 8 ms 15860 KB Output is correct
6 Correct 39 ms 15948 KB Output is correct
7 Correct 35 ms 15884 KB Output is correct
8 Correct 22 ms 15948 KB Output is correct
9 Correct 19 ms 15948 KB Output is correct
10 Correct 20 ms 15948 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 16000 KB Output is correct
3 Correct 9 ms 15848 KB Output is correct
4 Correct 7 ms 15884 KB Output is correct
5 Correct 8 ms 15860 KB Output is correct
6 Correct 39 ms 15948 KB Output is correct
7 Correct 35 ms 15884 KB Output is correct
8 Correct 22 ms 15948 KB Output is correct
9 Correct 19 ms 15948 KB Output is correct
10 Correct 20 ms 15948 KB Output is correct
11 Correct 1412 ms 15984 KB Output is correct
12 Execution timed out 3053 ms 15948 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 22116 KB Output is correct
2 Correct 1744 ms 22176 KB Output is correct
3 Correct 1661 ms 22124 KB Output is correct
4 Correct 1716 ms 22180 KB Output is correct
5 Correct 1522 ms 18372 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 16000 KB Output is correct
3 Correct 9 ms 15848 KB Output is correct
4 Correct 7 ms 15884 KB Output is correct
5 Correct 8 ms 15860 KB Output is correct
6 Correct 39 ms 15948 KB Output is correct
7 Correct 35 ms 15884 KB Output is correct
8 Correct 22 ms 15948 KB Output is correct
9 Correct 19 ms 15948 KB Output is correct
10 Correct 20 ms 15948 KB Output is correct
11 Correct 1412 ms 15984 KB Output is correct
12 Execution timed out 3053 ms 15948 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 16000 KB Output is correct
3 Correct 9 ms 15848 KB Output is correct
4 Correct 7 ms 15884 KB Output is correct
5 Correct 8 ms 15860 KB Output is correct
6 Correct 39 ms 15948 KB Output is correct
7 Correct 35 ms 15884 KB Output is correct
8 Correct 22 ms 15948 KB Output is correct
9 Correct 19 ms 15948 KB Output is correct
10 Correct 20 ms 15948 KB Output is correct
11 Correct 1412 ms 15984 KB Output is correct
12 Execution timed out 3053 ms 15948 KB Time limit exceeded
13 Halted 0 ms 0 KB -