oj.uz

Submission #889919

# Submission time Handle Problem Language Result Execution time Memory
889919 2023-12-20T09:43:45 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 90776 KB 
#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(1e6)+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 = 300;

int n, m, w[N], sta[20][N], LOG[N], mxsuf[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;
	int mxpref = 0;
	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);
			for(int j = r; j >= i; j --) {
				int mx = get(i, j - 1);
				if(j < r) mxsuf[j] = mxsuf[j + 1];
				if(mx > w[j]) {
					mxsuf[j] = max(mxsuf[j], mx + w[j]);
				}
			} 
		}
	}
//	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;
			}
			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));
		}
		int pos = br * B;
		for(int binl = br * B + 1, binr = r; binl <= binr; ) {
			int mid = (binl + binr) / 2;
			if(get(br * B + 1, mid) < mx) binl = mid + 1, pos = mid;
			else binr = mid - 1;
		}
		ans = max(ans, get(br * B + 1, pos) + mx);
		if(pos < r) ans = max(ans, mxsuf[pos + 1]);
		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

sortbooks.cpp: In function 'void Baizho()':
sortbooks.cpp:56:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |    sta[j][i] = max(sta[j-1][i], sta[j-1][i+(1<<j-1)]);
      |                                                ~^~
sortbooks.cpp:49:6: warning: unused variable 'mxpref' [-Wunused-variable]
   49 |  int mxpref = 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 21340 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Incorrect 4 ms 23400 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 21340 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Incorrect 4 ms 23400 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 345 ms 46700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 21340 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Incorrect 4 ms 23400 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 21340 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 3 ms 21340 KB Output is correct
6 Correct 4 ms 23388 KB Output is correct
7 Incorrect 4 ms 23400 KB Output isn't correct
8 Halted 0 ms 0 KB -