oj.uz

Submission #1116668

# Submission time Handle Problem Language Result Execution time Memory
1116668 2024-11-22T06:52:40 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 42316 KB 
// Problem: E - Hedgehog Daniyar and Algorithms
// Contest: Virtual Judge - Selection
// URL: https://vjudge.net/contest/673521#problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

/**********************************                               //deque,priority_queue
 *    author:  NurkhatKrutoi2009
 *    created: Just now
 *    P.S: tourist ne katai
**********************************/
#include <bits/stdc++.h>
/* for ordered_set <int> st; --> st.order_of_key(j)
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std; 
using namespace __gnu_pbds;  //Delete the other one
template<class T> using ordered_set = tree<T, null_type, 
less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, 
rb_tree_tag, tree_order_statistics_node_update>;
*//*
#include <algorithm>
#include <iostream>
#include <cmath>
*//*
#pragma GCC optimize("fast-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2,fma")
#pragma GCC optimization ("unroll-loops")
*/
#define int long long
#define FREOPEN  freopen("  .in", "r", stdin);  freopen("  .out", "w", stdout);
#define sonic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define all(x) (x).begin(), (x).end()
#define pss pair<string,string>
#define nextp next_permutation
#define pii pair<int,int>
#define priq priority_queue
#define mii map<int,int>
#define sz(x) (x).size()
#define stirng string
#define str to_string
#define rev reverse
#define pb push_back
#define ll long long
#define endl '\n'
#define S second
#define F first
const int Pi=3.1415926535;
const int MOD=1e9+7;
const int N=1e6+123;
const int lol=63;
const int inf=1e10+5;
using namespace std;
int tc=1;
struct node{
	int mx=0,mn=inf;
};
int n,m,l,r,k;
node t[4*N];
int s[N];
node link(node a, node b){
	node ans;
	ans.mx=max( a.mx, b.mx );
	ans.mn=min( a.mn, b.mn );
	return ans;
}
void build(int v=1, int tl=1, int tr=n){
	if(tl==tr){
		t[v]={s[tl],s[tl]};
		return;
	}int tm=(tl+tr)>>1;
	build(v+v,tl,tm);
	build(v+v+1,tm+1,tr);
	t[v]=link(t[v+v],t[v+v+1]);
}
int get(int l, int r, int x, int v=1, int tl=1, int tr=n){
	if(l>tr || r<tl || t[v].mn>=x)return 0;
	if( t[v].mx<x && l<=tl && tr<=r) return t[v].mx;
	int tm=(tl+tr)>>1;
	return max( get(l,r,x,v+v,tl,tm), get(l,r,x,v+v+1,tm+1,tr) );
	
}
void code( ){ 
	cin>>n>>m;
	FOR(i,1,n,1)cin>>s[i];
	build();
	while(m--){ bool ok=1;
		int l,r,k;
		cin>>l>>r>>k;
		FOR(i,l,r,1){
			int mx=get(i+1,r,s[i]);
			if(mx+s[i]>k && mx!=0){ok=0;break;}
		}
		if(ok)cout<<1;
		else cout<<0;
		cout<<'\n';
	}
}signed main(){sonic   //FREOPEN
    //cin>>tc;  
    while(tc--){
    code();
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 15 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 15 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 271 ms 592 KB Output is correct
13 Correct 172 ms 592 KB Output is correct
14 Correct 393 ms 848 KB Output is correct
15 Correct 285 ms 764 KB Output is correct
16 Execution timed out 3045 ms 848 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 15 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 271 ms 592 KB Output is correct
13 Correct 172 ms 592 KB Output is correct
14 Correct 393 ms 848 KB Output is correct
15 Correct 285 ms 764 KB Output is correct
16 Execution timed out 3045 ms 848 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 15 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 271 ms 592 KB Output is correct
13 Correct 172 ms 592 KB Output is correct
14 Correct 393 ms 848 KB Output is correct
15 Correct 285 ms 764 KB Output is correct
16 Execution timed out 3045 ms 848 KB Time limit exceeded
17 Halted 0 ms 0 KB -