Submission #1127818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127818		kirakosyan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3096 ms	61764 KiB

sortbooks

#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<random>
#include<cmath>
#include<stack>
#include<map>
#include <iomanip>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll mod = 1e9 + 7;
ll pv(ll a, ll b) {
	if (b == 0)return 1;
	ll res = (pv(a, b / 2));
	if (b % 2) {
		return (((res * res) % mod) * (a % mod)) % mod;
	}
	else {
		return (res * res) % mod;
	}
}
ll gcd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}
ll n,s=1;
vector<ll> v, seg;
void build(ll l, ll r, ll u) {
	if(l == r) {
		if(l < n) seg[u] = v[l];
		return;
	}
	ll m = (l + r) / 2;
	build(l, m, 2 * u + 1), build(m + 1, r, 2 * u + 2);
	seg[u] = max(seg[2 * u + 1],seg[2 * u + 2]);
}

ll get(ll l, ll r, ll lx, ll rx, ll u) {
	if(lx >= l && rx <= r) return seg[u];
	if(lx > r || rx < l) return 0;
	ll m = (lx + rx) / 2;
	ll a = get(l, r, lx, m, 2 * u + 1), b = get(l, r, m + 1, rx, 2 * u + 2);
	return max(a,b) ;
}
void solve() {
	ll q;
	cin >> n >> q;
	v=vector<ll>(n);
	for(ll i=0; i<n; i++) {
		cin >> v[i];
	}
	while(s<n)s<<=1;
	seg=vector<ll>(2*s-1);
	build(0,s-1,0);
	while(q--) {
		ll l,r,k;
		cin >> l >> r >> k;
		--l,--r;
		vector<ll>a,b;
		map<ll,ll>mp;
		for(ll j=l; j<=r; j++) {
			b.push_back(v[j]);
		}
		sort(b.begin(),b.end());
		for(ll i=0; i<b.size(); i++) {
// 			cout<<b[i]<<" ";
			mp[b[i]]=l+i;
		}
// 		cout<<endl;
		ll mx=0,f=0;
		// 3 5 1
		for(ll i=l; i<=r; i++) {
			if(v[i]==b[i-l])continue;
			int hnar=k-v[i],cnt=0;
// 			cout<<hnar<<" "<<v[i]<<" "<<mp[v[i]]<<endl;
			if(i<mp[v[i]]) {
				for(int j=i+1; j<=r; j++) {
					if(v[j]<=hnar)cnt++;
				}
			}
			else{
			    for(int j=i-1; j>=l; j--) {
					if(v[j]<=hnar)cnt++;
				}
			}
			if(cnt<mp[v[i]]-i)f=1;
		}
		if(f)cout<<0<<endl;
		else cout<<1<<endl;
	}

}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll _ = 1;
// 	cin >> _;
	while (_--) {
		solve();
	}
}

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