oj.uz

Submission #889960

# Submission time Handle Problem Language Result Execution time Memory
889960 2023-12-20T10:22:26 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 123560 KB 
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;

const int MOD = 1e9 + 7;
const int N = 2e6 + 7;
const int P = 911;
const ll INF = 1e18;

int rnd() {
	int x = rand() << 15;
	return x ^ rand();
}

int n, a[N], t[N << 2];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
	if (tl >= tr) {
		t[v] = max(t[v], val);
		return;
	}
	if (pos <= tm) upd(pos, val, ls);
	else upd(pos, val, rs);
	t[v] = max(t[v << 1], t[v << 1 | 1]);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (l <= tl && tr <= r) return t[v];
	if (r < tl || tr < l) return 0;
	return max(get(l, r, ls), get(l, r, rs));
}

int ql[N], qr[N], ans[N], k[N];
vector <int> act[N];

void GazizMadi() {
	int m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> ql[i] >> qr[i] >> k[i];
		act[ql[i]].pb(i); 
	}
	for (int i = n; i; i--) {
		for (int j = i + 1; j <= n; j++) {
			if (a[i] > a[j]) {
				upd(j, a[i] + a[j]);
				// cout << j << ' ' << a[i] + a[j] << '\n';
			}
		}
		for (int it: act[i]) {
			int l = i, r = qr[it];
			ans[it] = (get(l, r) <= k[it] ? 1 : 0);
			// cout << l << ' ' << r << ' ' << get(l, r) << '\n';
		}
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

const bool Cases = 0;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	srand(time(0));
	int TT = 1;
	if (Cases) cin >> TT;
	for (int i = 1; i <= TT; i++) {
		//cout << "Case " << i << ": ";
		GazizMadi();
	}
}

Compilation message

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:51:13: note: in expansion of macro 'tm'
   51 |  if (pos <= tm) upd(pos, val, ls);
      |             ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:14:24: note: in expansion of macro 'tm'
   14 | #define ls v << 1, tl, tm
      |                        ^~
sortbooks.cpp:51:31: note: in expansion of macro 'ls'
   51 |  if (pos <= tm) upd(pos, val, ls);
      |                               ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:15:24: note: in expansion of macro 'tm'
   15 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
sortbooks.cpp:52:21: note: in expansion of macro 'rs'
   52 |  else upd(pos, val, rs);
      |                     ^~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:14:24: note: in expansion of macro 'tm'
   14 | #define ls v << 1, tl, tm
      |                        ^~
sortbooks.cpp:59:23: note: in expansion of macro 'ls'
   59 |  return max(get(l, r, ls), get(l, r, rs));
      |                       ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:15:24: note: in expansion of macro 'tm'
   15 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
sortbooks.cpp:59:38: note: in expansion of macro 'rs'
   59 |  return max(get(l, r, ls), get(l, r, rs));
      |                                      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55896 KB Output is correct
2 Correct 12 ms 55896 KB Output is correct
3 Correct 12 ms 55896 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 12 ms 55904 KB Output is correct
6 Correct 15 ms 55900 KB Output is correct
7 Correct 14 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 12 ms 55900 KB Output is correct
10 Correct 12 ms 55956 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55896 KB Output is correct
2 Correct 12 ms 55896 KB Output is correct
3 Correct 12 ms 55896 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 12 ms 55904 KB Output is correct
6 Correct 15 ms 55900 KB Output is correct
7 Correct 14 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 12 ms 55900 KB Output is correct
10 Correct 12 ms 55956 KB Output is correct
11 Correct 40 ms 55896 KB Output is correct
12 Correct 418 ms 56156 KB Output is correct
13 Correct 433 ms 56200 KB Output is correct
14 Correct 451 ms 56196 KB Output is correct
15 Correct 444 ms 56152 KB Output is correct
16 Correct 64 ms 56152 KB Output is correct
17 Correct 135 ms 56164 KB Output is correct
18 Correct 125 ms 56156 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55896 KB Output is correct
2 Correct 12 ms 55896 KB Output is correct
3 Correct 12 ms 55896 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 12 ms 55904 KB Output is correct
6 Correct 15 ms 55900 KB Output is correct
7 Correct 14 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 12 ms 55900 KB Output is correct
10 Correct 12 ms 55956 KB Output is correct
11 Correct 40 ms 55896 KB Output is correct
12 Correct 418 ms 56156 KB Output is correct
13 Correct 433 ms 56200 KB Output is correct
14 Correct 451 ms 56196 KB Output is correct
15 Correct 444 ms 56152 KB Output is correct
16 Correct 64 ms 56152 KB Output is correct
17 Correct 135 ms 56164 KB Output is correct
18 Correct 125 ms 56156 KB Output is correct
19 Execution timed out 3060 ms 70620 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55896 KB Output is correct
2 Correct 12 ms 55896 KB Output is correct
3 Correct 12 ms 55896 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 12 ms 55904 KB Output is correct
6 Correct 15 ms 55900 KB Output is correct
7 Correct 14 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 12 ms 55900 KB Output is correct
10 Correct 12 ms 55956 KB Output is correct
11 Correct 40 ms 55896 KB Output is correct
12 Correct 418 ms 56156 KB Output is correct
13 Correct 433 ms 56200 KB Output is correct
14 Correct 451 ms 56196 KB Output is correct
15 Correct 444 ms 56152 KB Output is correct
16 Correct 64 ms 56152 KB Output is correct
17 Correct 135 ms 56164 KB Output is correct
18 Correct 125 ms 56156 KB Output is correct
19 Execution timed out 3029 ms 123560 KB Time limit exceeded
20 Halted 0 ms 0 KB -