oj.uz

Submission #652586

# Submission time Handle Problem Language Result Execution time Memory
652586 2022-10-23T09:15:09 Z l3nl3 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 107820 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 7;

int n, m, a[N], t[N*4];

void build (int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = a[tl];
		return;
	}
	int tm = (tl+tr) / 2;
	build(v+v, tl, tm);
	build(v+v+1, tm+1, tr);
	t[v] = max(t[v+v], t[v+v+1]);
}

int get (int v, int tl, int tr, int l, int r) {
	if (l <= tl && tr <= r) {
		return t[v];
	}
	if (r < tl || tr < l) return 0;
	int tm = (tl+tr) / 2;
	return max(get(v+v, tl, tm, l, r), get(v+v+1, tm+1, tr, l, r));
}

signed main () {
 	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;   
	vector<pair<int, int>> v;
	map<int, int> pos;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		v.push_back({a[i], i});
	}		
	sort(v.begin(), v.end());
	for (auto [x, p] : v) {
		a[p] = x;
		pos[x] = p;			
	}	                        	
	build(1, 1, n);
	cin >> m;
	while (m--) {
		int l, r, k;
		cin >> l >> r >> k;
		int f = get(1, 1, n, l, r);
		int s = get(1, 1, n, pos[f]+1, r);
		//cerr << f << ' ' << s << '\n';
		if (f+s <= k) cout << 1 << '\n';
		else cout << 0 << '\n';	
	}
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:42:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |  for (auto [x, p] : v) {
      |            ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3028 ms 107820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 5476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -