Submission #889983

#	Time	Username	Problem	Language	Result	Execution time	Memory
889983		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	1741 ms	19320 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
 #pragma GCC optimize("Ofast,unroll-loops,fast-math")
 #pragma GCC target("popcnt")


typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back

const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(2e5)+10;
const long long inf = 2e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }

ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

const int B = 900;

int n, m, w[N], sta[20][N], LOG[N], mxsuf[N], pr[N];
//int ql[N], qr[N], qk[N]
int get(int l, int r) {
	if(l > r) return 0;
	int j = LOG[r - l + 1];
	return max(sta[j][l], sta[j][r-(1<<j)+1]);
}

void Baizho() {	
	for(int i = 2; i < N; i ++) LOG[i] = LOG[i / 2] + 1;
	cin>>n>>m;
	if(n > 2e5 && m > 2e5) {
		for(int i = 1; i <= n; i ++) {
			cin>>w[i];
			if(i > 1) {
				if(w[i - 1] > w[i]) pr[i] ++;
			}
			pr[i] += pr[i - 1];
		}
	
		while(m --) {
			int l, r, k; cin>>l>>r>>k;
			if(pr[r] - pr[l] > 0) cout<<"0\n";
			else cout<<"1\n";
		}
		return;
	}
	for(int i = 1; i <= n; i ++) {
		cin>>w[i];
		sta[0][i] = w[i];
	}
	for(int j = 1; j <= 19; j ++) {
		for(int i = 1; i+(1<<j)-1 <= n; i ++) {
			sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
		}
	}
	for(int i = 1; i <= n; i ++) {
		if(i % B == 1) {
			int r = min(n, i + B - 1), mx = 0, ans = 0;
			for(int j = i; j <= r; j ++) {
				if(mx > w[j]) mxsuf[j] = mx + w[j];
				mx = max(mx, w[j]);
			}
			for(int j = r - 1; j >= i; j --) mxsuf[j] = max(mxsuf[j], mxsuf[j + 1]);
		}
	}
//	for(int i = 1; i <= n; i ++) cout<<mxsuf[i]<<" ";
//	cout<<"\n";
	while(m --) {
		int l, r, k; cin>>l>>r>>k;
		int bl = (l - 1) / B, br = (r - 1) / B;
		if(bl == br) {
			int mx = 0, ans = 0;
			for(int i = l; i <= r; i ++) {
				if(mx > w[i]) ans = max(ans, w[i] + mx);
				mx = max(mx, w[i]);
			}
			cout<<(ans <= k)<<"\n";
			continue;
		}
		int ans = 0, mx = 0;
		for(int i = l; i <= bl * B + B; i ++) {
			if(mx > w[i]) ans = max(ans, w[i] + mx);
			mx = max(mx, w[i]);
		}
		for(int b = bl + 1; b < br; b ++) {
			int pos = b * B;
			for(int binl = b * B + 1, binr = b * B + B; binl <= binr; ) {
				int mid = (binl + binr) / 2;
				if(get(b * B + 1, mid) < mx) binl = mid + 1, pos = mid;
				else binr = mid - 1;
			}
			if(pos >= b * B + 1) ans = max(ans, get(b * B + 1, pos) + mx);
			if(pos < b * B + B) ans = max(ans, mxsuf[pos + 1]);
			mx = max(mx, get(b * B + 1, b * B + B));
		}
		for(int i = br * B + 1; i <= r; i ++) {
			if(mx > w[i]) ans = max(ans, w[i] + mx);
			mx = max(mx, w[i]);
		}
		cout<<(ans <= k)<<"\n";
	}
	
}
  
signed main() {		
 
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
   	
    int ttt = 1;
//    cin>>ttt;

    for(int i=1; i<=ttt; i++) { Baizho(); }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void Baizho()':
sortbooks.cpp:71:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |    sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
      |                                                ~^~
sortbooks.cpp:76:39: warning: unused variable 'ans' [-Wunused-variable]
   76 |    int r = min(n, i + B - 1), mx = 0, ans = 0;
      |                                       ^~~
sortbooks.cpp: In function 'void Freopen(std::string)':
sortbooks.cpp:34:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:34:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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