oj.uz

Submission #497472

# Submission time Handle Problem Language Result Execution time Memory
497472 2021-12-23T06:33:52 Z Ziel Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 73800 KB 
/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");

string to_string(const string s) {
	return '"' + s + '"';
}
string to_string(const char c) {
 	return char(39) + string(1, c) + char(39);
}
string to_string(const char* s) {
 	return to_string(string(s));
}
string to_string(bool f) {
	return (f ? "true" : "false");
}
template<class A, class B>
string to_string(const pair<A, B> x) {
	return "(" + to_string(x.first) + ", " + to_string(x.second) + ")";
}
template<class A, class B, class C>
string to_string(const tuple<A, B, C> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ")";
}
template<class A, class B, class C, class D>
string to_string(const tuple<A, B, C, D> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ", " + to_string(get<3>(x)) + ")";
}
template<class T>
string to_string(const T v) {
	string res = "{"; bool f = true;
	for (auto x: v)
		res += (f ? to_string(x) : ", " + to_string(x)), f = false;
	return res + "}";
}
void debug_args() { cerr << "]\n"; }
template<class H, class... T>
void debug_args(H x, T... y) {
	cerr << to_string(x);
	if (sizeof... (y))
	cerr << ", ";
	debug_args(y...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: [", debug_args(__VA_ARGS__);
#else
#define debug(...) 47
#endif

#define int ll

const int N = 1e6 + 12456;
struct node {
	int mx1, mx2, mn, k;
} t[4 * N];
int a[N], n, q;

//find last smaller
int fls(int l, int r, int v, int x, int lx, int rx) {
	if (lx == rx) {
		if (l <= lx && rx <= r)
			return a[lx];
		return -1;
	}
	int mid = (lx + rx) / 2;
	ll res = -1;
	if (!(mid < l || r < lx) && t[2 * x + 1].mn < v)
		res = max(res, fls(l, r, v, 2 * x + 1, lx, mid));
	if (!(rx < l || r < mid + 1) && t[2 * x + 2].mn < v)
		res = max(res, fls(l, r, v, 2 * x + 2, mid + 1, rx));
	return res;
}
node unite(node a, node b, int bx, int blx, int brx, int l, int r) {
	node res;
	res.k = max(a.k, b.k);
	res.mn = min(a.mn, b.mn);

	if (a.mx1 > b.mx1) {
		res.mx1 = a.mx1;
		if (a.mx2 > b.mx1) {
			res.mx2 = a.mx2;
		} else {
			if (b.mx1 == a.mx1)
				res.mx2 = a.mx2;
			else
				res.mx2 = b.mx1;
		}
	} else {
		res.mx1 = b.mx1;
		if (b.mx2 > a.mx1) {
			res.mx2 = b.mx2;
		} else {
			if (a.mx1 == b.mx1)
				res.mx2 = b.mx2;
			else
				res.mx2 = a.mx1;
		}
	}

	if (a.mx1 <= b.mn)
		return res;
	if (a.mx1 > b.mx1) {
		res.k = max(res.k, a.mx1 + b.mx1);
		return res;
	} else {
		res.k = max(res.k, a.mx1 + fls(l, r, a.mx1, bx, blx, brx));
		return res;
	}
}
void build(int x = 0, int lx = 1, int rx = n) {
	if (lx == rx) {
		t[x].mx1 = a[lx];
		t[x].mx2 = 0;
		t[x].mn = a[lx];
		t[x].k = 0;
	} else {
		int mid = (lx + rx) / 2;
		build(2 * x + 1, lx, mid);
		build(2 * x + 2, mid + 1, rx);
		t[x] = unite(t[2 * x + 1], t[2 * x + 2], 2 * x + 2, mid + 1, rx, lx, rx);
	}
}
node get(int l, int r, int x = 0, int lx = 1, int rx = n) {
	if (r < lx || rx < l) return {-1, -1, -1, -1};
	if (l <= lx && rx <= r) return t[x];
	int mid = (lx + rx) / 2;
	node res1 = get(l, r, 2 * x + 1, lx, mid);
	node res2 = get(l, r, 2 * x + 2, mid + 1, rx);
	if (res1.mx1 == -1 && res2.mx1 == -1)
		assert(false);
	if (res1.mx1 == -1)
		return res2;
	if (res2.mx1 == -1)
		return res1;
	return unite(res1, res2, 2 * x + 2, mid + 1, rx, l, r);
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build();
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		node res = get(l, r);
		cout << bool(res.k <= k) << '\n';
	}
}

signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> tt;
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

sortbooks.cpp: In function 'void setIO(const string&)':
sortbooks.cpp:179:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 29 ms 864 KB Output is correct
13 Correct 25 ms 884 KB Output is correct
14 Correct 48 ms 880 KB Output is correct
15 Correct 53 ms 1004 KB Output is correct
16 Correct 24 ms 844 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 22 ms 844 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 73800 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 3066 ms 9436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 29 ms 864 KB Output is correct
13 Correct 25 ms 884 KB Output is correct
14 Correct 48 ms 880 KB Output is correct
15 Correct 53 ms 1004 KB Output is correct
16 Correct 24 ms 844 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 22 ms 844 KB Output is correct
19 Execution timed out 3051 ms 18304 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 29 ms 864 KB Output is correct
13 Correct 25 ms 884 KB Output is correct
14 Correct 48 ms 880 KB Output is correct
15 Correct 53 ms 1004 KB Output is correct
16 Correct 24 ms 844 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 22 ms 844 KB Output is correct
19 Execution timed out 3080 ms 73800 KB Time limit exceeded
20 Halted 0 ms 0 KB -