Submission #1268218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268218		Bui_Quoc_Cuong	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	920 ms	63608 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int LIM = 1e6 + 5;
int n, q;
int a[LIM];
vector <array <int, 3>> ask[LIM];
int ans[LIM];
int st[4 * LIM];
void up(int pos, int val){
	int id = 1, l = 1, r = n;
	while(l < r){
		int mid = (l + r) >> 1;
		if(pos <= mid) id = id << 1, r = mid;
		else id = id << 1 | 1, l = mid + 1;
	}
	st[id] = max(st[id], a[pos] + val);
	while(id > 1){
		id >>= 1;
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}
}
int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    #define koa "kieuoanh"
    if(fopen(koa".inp", "r")){
        freopen(koa".inp", "r", stdin); freopen(koa".out", "w", stdout);
    }
    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;
    	ask[r].push_back({l, k, i});
    	ans[i] = true;
    }
    stack <int> st;
    for(int i = 1; i <= n; i++){
    	while(!st.empty() && a[st.top()] <= a[i]) st.pop();
    	if(!st.empty()){
    		up(st.top(), a[i]);
    	}
    	st.push(i);
    	for(auto it : ask[i]){
    		int l = it[0], k = it[1], id = it[2];
    		if(get(1, 1, n, l, i) > k){
    			ans[id] = 0;
    		}
    	}
    }
    for(int i = 1; i <= q; i++){
    	cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

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

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