Submission #1288370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288370		shidou26	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	17 / 100	552 ms	69164 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 1e6 + 3;

int n, q;
int a[N];
tp3 query[N];

void input() {
	cin >> n >> q;

	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for(int i = 1; i <= q; i++) {
		int l, r, k; cin >> l >> r >> k;
		query[i] = {l, r, k};
	}
}

namespace subtask_2 {
	bool approve() {
		return max(n, q) <= 5000;
	}

	const int N = 5e3 + 3;

	void execute() {
		for(int t = 1; t <= q; t++) {
			int l, r, k; tie(l, r, k) = query[t];

			bool passed = true;	
			for(int i = l, optimal = 0; i <= r; i++) {
				if(optimal > a[i] && optimal + a[i] > k) {
					passed = false;
					break;
				}

				maximize(optimal, a[i]);
			}

			cout << passed << endl;
		}
	}
}

namespace subtask_3 {
	bool approve() {
		int max_k = 0;
		for(int i = 1; i <= q; i++) maximize(max_k, get<2>(query[i]));
		for(int i = 1; i <= n; i++) {
			if(max_k >= a[i]) return false; 
		}

		return true;
	}

	int answer[N];
	vector<pii> event[N];

	struct FenwickTree {
		vector<int> tr;
		FenwickTree (int n) : tr(n + 3) {}

		void update(int p, int v) {
			for(; p < sz(tr); p += p & -p)
				tr[p] += v;
		}

		int get(int p) {
			int tot = 0;
			for(; p > 0; p -= p & -p) 
				tot += tr[p];
			return tot;
		}
	};

	void execute() {
		for(int i = 1; i <= q; i++) {
			int l, r, k; tie(l, r, k) = query[i];
			event[r].emplace_back(l, i);
		}

		stack<int> stk;
		FenwickTree ft(n);

		for(int i = 1; i <= n; i++) {
			while(!stk.empty() && a[stk.top()] < a[i]) stk.pop();
			if(!stk.empty()) ft.update(stk.top(), 1);
			stk.push(i);

			for(auto [l, j] : event[i]) {
				answer[j] = (ft.get(i) == ft.get(l - 1)); 
			}
		}

		for(int i = 1; i <= q; i++)
			cout << answer[i] << endl;
	}
}

namespace subtask_6 {
	bool approve() {
		return true;
	}

	int answer[N];
	vector<tp3> event[N];

	struct SegmentTree {
		vector<int> tr;
		SegmentTree (int n) : tr(n + 3) {}

		void update(int id, int l, int r, int p, int v) {
			if(l == r) {
				maximize(tr[id], v);
				return;
			}

			int mid = (l + r) >> 1;
			if(p <= mid) update(id << 1, l, mid, p, v);
			else update(id << 1 | 1, mid + 1, r, p, v);

			tr[id] = max(tr[id << 1], tr[id << 1 | 1]);
		}

		int get(int id, int l, int r, int u, int v) {
			if(r < u || v < l) return 0;
			if(u <= l && r <= v) return tr[id];

			int mid = (l + r) >> 1;
			return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
		}
	};

	void execute() {
		for(int i = 1; i <= q; i++) {
			int l, r, k; tie(l, r, k) = query[i];
			event[r].emplace_back(l, k, i);
		}

		stack<int> stk;
		SegmentTree st(n);

		for(int i = 1; i <= n; i++) {
			while(!stk.empty() && a[stk.top()] < a[i]) stk.pop();
			if(!stk.empty()) st.update(1, 1, n, stk.top(), a[i] + a[stk.top()]);
			stk.push(i);

			for(auto [l, k, j] : event[i]) {
				answer[j] = (st.get(1, 1, n, l, i) <= k); 
			}
		}

		for(int i = 1; i <= q; i++)
			cout << answer[i] << endl;
	}
}

void process() {
    if(subtask_2::approve()) return subtask_2::execute();
    if(subtask_3::approve()) return subtask_3::execute();
    if(subtask_6::approve()) return subtask_6::execute();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int testcase = 1; // cin >> testcase;    
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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