Submission #1108172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108172		kuka_123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1132 ms	107528 KiB

sortbooks

															/*Bismillahir Rahmanir Raheem*/
#include <bits/stdc++.h>
  
using namespace std;
 
#define kuka ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define FOR(n) for(int i = 0; i < n; i++)
#define ff(x, y) for( int y = 0; y < x; y++)
#define fff(x, y) for( int y = x; y <= 0; y--)
#define F first
#define S second
//#define int long long  
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll INF = LLONG_MAX;
const int inf = INT_MAX;
const double PI = acos(-1);
const int N = 1e6 + 5;
const int MOD = 1e9 ;	 
 
vector<pair<int, pair<int, int> > > g[N];
int a[N], last[N], b[N], c[N], ans[N], t[N * 4];
 
void update(int v, int l, int r, int x, int y){
	if(l == r){
		t[v] = y;
		return;
	}
	int mid = (l + r) / 2;
	if(mid >= x)update(v * 2, l, mid, x, y);
	else update(v * 2 + 1, mid + 1, r, x, y);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int l , int r, int L , int R){
	if(l > R or L > r) return 0;
	if(l >= L and R >= r)return t[v];
	int mid = (l + r) / 2;
	return max(get(v * 2, l , mid, L, R), get(v * 2 + 1, mid + 1, r, L, R));
}
 
void oyan(){
	int n ,q;
	cin>>n>>q;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
//	for(int i = 1; i <= n; i++){
//		c[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b ;
//	}
	for(int i = 1; i <= q; i++){
		int l, r, x;
		cin>>l>>r>>x;
		g[r].pb({l, {x, i}});
	}
	stack<int> s;
	s.push(1);
	for(int i = 2; i <= n; i++){
		while(!s.empty() and a[s.top()] <= a[i])s.pop();
		if(s.empty()) last[i] = 0;
		else last[i] = s.top();
		s.push(i);
	}
	for(int i = 1; i <= n; i++){
		if(last[i])update(1, 1, n, last[i], a[last[i]] + a[i]);
		for(auto x : g[i]){
			if(get(1, 1, n, x.F, i) <= x.S.F)ans[x.S.S] = 1;
		}
	}
	for(int i = 1; i <= q; i++){
		cout<<ans[i]<<"\n";
	}
//	cout<<"\n";

	
}
 
main(){
    kuka;
	//freopen("test.txt", "r", stdin);
	//freopen("distance.in", "r", stdin);
    //freopen("distance.out", "w", stdout);
    int oylan = 1;
   	//cin>>oylan;
    while(oylan--){
        oyan();
    }
}
/*
NOTES
a/b module == (a*b^(module - 2)) % (module);
*/

Compilation message (stderr)

sortbooks.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23