oj.uz

Submission #1116683

# Submission time Handle Problem Language Result Execution time Memory
1116683 2024-11-22T07:54:30 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 75904 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;
		FORR(i,r,l,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 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 2 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 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 15 ms 592 KB Output is correct
12 Correct 62 ms 592 KB Output is correct
13 Correct 54 ms 876 KB Output is correct
14 Correct 129 ms 592 KB Output is correct
15 Correct 50 ms 848 KB Output is correct
16 Execution timed out 3061 ms 760 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 65112 KB Output is correct
2 Correct 979 ms 75856 KB Output is correct
3 Correct 1081 ms 75724 KB Output is correct
4 Correct 1024 ms 75904 KB Output is correct
5 Execution timed out 3060 ms 50896 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 5200 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 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 15 ms 592 KB Output is correct
12 Correct 62 ms 592 KB Output is correct
13 Correct 54 ms 876 KB Output is correct
14 Correct 129 ms 592 KB Output is correct
15 Correct 50 ms 848 KB Output is correct
16 Execution timed out 3061 ms 760 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 2 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 15 ms 592 KB Output is correct
12 Correct 62 ms 592 KB Output is correct
13 Correct 54 ms 876 KB Output is correct
14 Correct 129 ms 592 KB Output is correct
15 Correct 50 ms 848 KB Output is correct
16 Execution timed out 3061 ms 760 KB Time limit exceeded
17 Halted 0 ms 0 KB -