답안 #964906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964906 2024-04-17T17:12:08 Z Acanikolic Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
13 / 100
1303 ms 110212 KB
#include <bits/stdc++.h>
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 1000000 + 10;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9; 	

int a[N],res[N];
vector<array<int,3>>kveri[N];

long long st[N * 4];

void update(int node,int tl,int tr,int index,long long val) {
	if(tl > index || tr < index) return;
	if(tl == tr) {
		st[node] = val;
		return;
	}
	int mid = (tl + tr) / 2;
	update(node * 2,tl,mid,index,val);
	update(node * 2 + 1,mid + 1,tr,index,val);
	st[node] = max(st[node * 2],st[node * 2 + 1]);
}

long long get(int node,int tl,int tr,int l,int r) {
	if(tl > r || tr < l) return 0ll;
	if(tl >= l && tr <= r) return st[node];
	int mid = (tl + tr) / 2;
	return get(node * 2,tl,mid,l,r) + get(node * 2 + 1,mid + 1,tr,l,r);
}
	 		 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,q;
	cin >> n >> q;
	vector<int>a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int>prev(n + 1,-1);
	stack<int>st;
	for(int i = 1; i <= n; i++) {
		while(st.size() && a[st.top()] <= a[i]) st.pop();
		if(st.size()) prev[i] = st.top();
		st.push(i);
	}
	for(int i = 1; i <= q; i++) {
		int l,r,k;
		cin >> l >> r >> k;
		kveri[r].pb({l,k,i});
	}
	for(int i = 1; i <= n; i++) {
		if(prev[i] != -1) update(1,1,n,prev[i],a[prev[i]] + a[i]);
		for(auto X : kveri[i]) {
			res[X[2]] = (get(1,1,n,X[0],i) > X[1] ? 0 : 1);
		}
	}
	for(int i = 1; i <= q; i++) cout << res[i] << "\n";
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 8 ms 25176 KB Output is correct
3 Incorrect 7 ms 25292 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 8 ms 25176 KB Output is correct
3 Incorrect 7 ms 25292 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1302 ms 108908 KB Output is correct
2 Correct 1257 ms 110200 KB Output is correct
3 Correct 1303 ms 109912 KB Output is correct
4 Correct 1294 ms 110212 KB Output is correct
5 Correct 965 ms 93632 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 32160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 8 ms 25176 KB Output is correct
3 Incorrect 7 ms 25292 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 24924 KB Output is correct
2 Correct 8 ms 25176 KB Output is correct
3 Incorrect 7 ms 25292 KB Output isn't correct
4 Halted 0 ms 0 KB -