Submission #523743

#	Time	Username	Problem	Language	Result	Execution time	Memory
523743		Kalashnikov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	1913 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 1e6+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N];
struct DO{
	int mn = -1, mx , inv;
	set<int> v;
}t[4*N] , null;
int n, m;

void merge(DO &u , DO L , DO R) {
	if(L.mn == -1) u = R;
	else if(R.mn == -1) u = L;
	else {
		u.mn = min(L.mn , R.mn);
		u.mx = max(L.mx , R.mx);
		u.inv = max(L.inv , R.inv);
		auto it = R.v.lower_bound(L.mx);
		if(it != R.v.begin()) {
			--it;
			u.inv = max(u.inv , L.mx + *it);
		}
		if(L.v.size() < R.v.size()) {
			swap(L , R);
		}
		swap(u.v , L.v);
		for(auto x: R.v) {
			u.v.insert(x);
		}
	}
}

void build(int u = 1, int ul = 1 , int ur = n) {
	if(ul == ur) {
		t[u].mn = t[u].mx = a[ul];
		t[u].inv = 0;
		t[u].v.insert(a[ul]);
		return;
	}
	
	int um= ul+ur >> 1;
	build(u<<1 , ul , um);
	build(u<<1|1 , um+1 , ur);
	merge(t[u] , t[u<<1] , t[u<<1|1]);
}

DO get(int l , int r , int u = 1, int ul = 1, int ur = n) {
	if(l <= ul && ur <= r) {
		return t[u];
	}
	if(r < ul || ur < l) {
		return null;
	}
	
	int um = ul+ur >> 1;
	DO res;
	merge(res , get(l , r , u<<1 , ul , um) , get(l , r , u<<1|1 , um+1 , ur));
	return res;
}

void solve(int tc) {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	build();
	while(m --) {
		int l , r , x;
		cin >> l >> r >> x;
		cout << (get(l , r).inv <= x) << '\n';
	}
}
/*
*/
main() {
    ios;
    int tt = 1 , tc = 0;
    // cin >> tt;
    while(tt --) {
        solve(++tc);
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int um= ul+ur >> 1;
      |          ~~^~~
sortbooks.cpp: In function 'DO get(int, int, int, int, int)':
sortbooks.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int um = ul+ur >> 1;
      |           ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main() {
      | ^~~~

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