oj.uz

Submission #497479

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

#pragma GCC optimization("g", on)
#pragma GCC optimize ("inline")
#pragma GCC optimization("03")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")

#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:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("g", on)
      | 
sortbooks.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization("03")
      | 
sortbooks.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization("unroll-loops")
      | 
sortbooks.cpp:9: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    9 | #pragma comment(linker, "/stack:200000000")
      | 
sortbooks.cpp: In function 'void setIO(const string&)':
sortbooks.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 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 0 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 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 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 9 ms 472 KB Output is correct
12 Correct 31 ms 876 KB Output is correct
13 Correct 24 ms 880 KB Output is correct
14 Correct 45 ms 884 KB Output is correct
15 Correct 50 ms 880 KB Output is correct
16 Correct 26 ms 880 KB Output is correct
17 Correct 6 ms 588 KB Output is correct
18 Correct 23 ms 896 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 73796 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 3063 ms 9444 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 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 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 9 ms 472 KB Output is correct
12 Correct 31 ms 876 KB Output is correct
13 Correct 24 ms 880 KB Output is correct
14 Correct 45 ms 884 KB Output is correct
15 Correct 50 ms 880 KB Output is correct
16 Correct 26 ms 880 KB Output is correct
17 Correct 6 ms 588 KB Output is correct
18 Correct 23 ms 896 KB Output is correct
19 Execution timed out 3068 ms 18268 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 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 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 9 ms 472 KB Output is correct
12 Correct 31 ms 876 KB Output is correct
13 Correct 24 ms 880 KB Output is correct
14 Correct 45 ms 884 KB Output is correct
15 Correct 50 ms 880 KB Output is correct
16 Correct 26 ms 880 KB Output is correct
17 Correct 6 ms 588 KB Output is correct
18 Correct 23 ms 896 KB Output is correct
19 Execution timed out 3065 ms 73796 KB Time limit exceeded
20 Halted 0 ms 0 KB -