oj.uz

답안 #879577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879577 2023-11-27T16:32:10 Z Elvin_Fritl Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 96888 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

 
typedef long long ll;
 
ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}

 
const int N =  1e6 + 545, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;

struct segtree {

	int tree[N * 2];
	int get(int v,int l, int r, int ml , int mr) {
		if(l > mr || r < ml || l > r) {
			return 0;
		}
		if(ml <= l && r <= mr) {
			return tree[v];
		}
		int mid = (l + r)/2;
		return max(get(v*2 , l, mid , ml, mr), get(v*2 + 1 , mid + 1, r , ml, mr));
	}
	void update(int v,int l,int r,int pos ,int val) {
		if(l > r) {
			return;
		}
		if(l == r) {
			tree[v] = max(val , tree[v]);
			return;
		}
		int mid = (l + r)/2;
		if(pos <= mid) {
			update(v*2 , l , mid , pos , mid);
		}
		else {
			update(v*2 + 1, mid + 1 , r , pos , mid);
		}
		tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
	}
};

segtree S;

int main() {
	int n, q;
    cin >> n >> q;
    vector<pair<pair<int , int > , int>> qu[n + 1]; 
	int a[n + 1];
	vector<int> ans(q + 1 , 0);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
    }
    cerr << "true1\n";
    cerr << "true2\n";
    for(int i=1;i<=q;i++) {
        int l, r, k; 
        cin >> l >> r >> k;
        qu[r].push_back({{l, k}, i});
    }
    cerr << "true3\n";
    vector<int> v;
	for(int r=1;r<=n;r++) {
		while(!v.empty() && a[v.back()] <= a[r])  {
			v.pop_back();
		}
		if(!v.empty()) {
			S.update(1 ,1 , n , v.back(), a[r] + a[v.back()]); 
		}
		for(auto &i : qu[r]) {
			int l = i.first.first, k = i.first.second, ind = i.second;
			int tmp = S.get(1 , 1 , n  , l, r);
			if(tmp <= k){ 
				cerr << tmp << endl;
				ans[ind] = 1;
			}
		}
		v.push_back(r);
	}
	for(int i=1;i<=q;i++) {
		cout << ans[i] << endl;
	}
    
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3093 ms 96888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 227 ms 8724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -