oj.uz

Submission #548959

# Submission time Handle Problem Language Result Execution time Memory
548959 2022-04-14T20:21:19 Z Bungmint Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2520 ms 262144 KB 
//Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define REP(a) F0R(_, a)

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7; //998244353;
const ld PI = acos((ld)-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
    os << '{';
    string sep;
    for (const T &x : v)
        os << sep << x, sep = ", ";
    return os << '}';
}
void dbg_out()
{
    cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda{
	template <typename Fun>
	struct y_combinator_result{
		Fun fun_;
		template <typename T> 
		explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)){}
		template <typename...Args>
		decltype(auto) operator()(Args &&...args){
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun){
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

void setIO(string s) // USACO
{
	#ifndef LOCAL
	    freopen((s + ".in").c_str(), "r", stdin);
	    freopen((s + ".out").c_str(), "w", stdout);
	#endif
}

const int N = 1e6 + 1;
pii jump[20][N]; // 160 MB
int a[20][N];

int query(int l, int r) {
	if (l > r) return 0;
	int lg = 31 - __builtin_clz(r - l + 1);
	return max(a[lg][l], a[lg][r - (1 << lg) + 1]);
}
int go(int l, int r) {
	int res = 0;
	R0F(i, 20) {
		auto [nxt, v] = jump[i][l];
		if (nxt <= r) {
			l = nxt;
			res = max(res, v);
		}
	}
	if (l != r) {
		res = max(res, query(l + 1, r) + a[0][l]);
	}
	return res;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	F0R(i, n) cin >> a[0][i];
	FOR(j, 1, 20) {
		for (int i = 0; i + (1 << j) <= n; i++) {
			a[j][i] = max(a[j - 1][i], a[j - 1][i + (1 << (j - 1))]);
		}
	}
	stack<int> st;
	F0R(i, 20) jump[i][n] = {n, 0};
	R0F(i, n) {
		while (sz(st) && a[0][st.top()] < a[0][i]) st.pop();
		jump[0][i].fi = (sz(st) ? st.top() : n);
		jump[0][i].se = query(i + 1, jump[0][i].fi - 1);
		if (jump[0][i].se) jump[0][i].se += a[0][i];
		dbg(jump[0][i]);
		st.push(i);
		FOR(j, 1, 20) {
			auto [nxt, v] = jump[j - 1][i];
			jump[j][i].fi = jump[j - 1][nxt].fi;
			jump[j][i].se = max(v, jump[j - 1][nxt].se);
		}
	}
	REP(m) {
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		int z = go(l, r);
		cout << (z <= k) << '\n';
	}
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase=1;
    // cin >> testcase;
    while (testcase--)
    {
        solve();
    }
}

Compilation message

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:71:18: warning: statement has no effect [-Wunused-value]
   71 | #define dbg(...) 42
      |                  ^~
sortbooks.cpp:140:3: note: in expansion of macro 'dbg'
  140 |   dbg(jump[0][i]);
      |   ^~~
sortbooks.cpp: In function 'void setIO(std::string)':
sortbooks.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |      freopen((s + ".in").c_str(), "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:95:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      freopen((s + ".out").c_str(), "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 4 ms 1748 KB Output is correct
15 Correct 5 ms 1748 KB Output is correct
16 Correct 4 ms 1620 KB Output is correct
17 Correct 4 ms 1492 KB Output is correct
18 Correct 4 ms 1620 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1214 ms 262144 KB Output is correct
2 Correct 1184 ms 262144 KB Output is correct
3 Correct 1135 ms 262144 KB Output is correct
4 Correct 1167 ms 262144 KB Output is correct
5 Correct 2520 ms 262144 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 24524 KB Output is correct
2 Correct 64 ms 24472 KB Output is correct
3 Correct 133 ms 25000 KB Output is correct
4 Correct 144 ms 24956 KB Output is correct
5 Correct 171 ms 25004 KB Output is correct
6 Correct 66 ms 24792 KB Output is correct
7 Correct 65 ms 24748 KB Output is correct
8 Correct 85 ms 24452 KB Output is correct
9 Correct 40 ms 2088 KB Output is correct
10 Correct 87 ms 24552 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 4 ms 1748 KB Output is correct
15 Correct 5 ms 1748 KB Output is correct
16 Correct 4 ms 1620 KB Output is correct
17 Correct 4 ms 1492 KB Output is correct
18 Correct 4 ms 1620 KB Output is correct
19 Correct 208 ms 51940 KB Output is correct
20 Correct 225 ms 51992 KB Output is correct
21 Correct 179 ms 51724 KB Output is correct
22 Correct 144 ms 51760 KB Output is correct
23 Correct 145 ms 51764 KB Output is correct
24 Correct 191 ms 52632 KB Output is correct
25 Correct 205 ms 52484 KB Output is correct
26 Correct 275 ms 52704 KB Output is correct
27 Correct 302 ms 52628 KB Output is correct
28 Correct 339 ms 52612 KB Output is correct
29 Correct 383 ms 52732 KB Output is correct
30 Correct 370 ms 52856 KB Output is correct
31 Correct 405 ms 52768 KB Output is correct
32 Correct 428 ms 52700 KB Output is correct
33 Correct 382 ms 52812 KB Output is correct
34 Correct 157 ms 52352 KB Output is correct
35 Correct 167 ms 52328 KB Output is correct
36 Correct 171 ms 52172 KB Output is correct
37 Correct 149 ms 52140 KB Output is correct
38 Correct 170 ms 52436 KB Output is correct
39 Correct 289 ms 51036 KB Output is correct
40 Correct 233 ms 34636 KB Output is correct
41 Correct 214 ms 50552 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 3 ms 1592 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 4 ms 1748 KB Output is correct
15 Correct 5 ms 1748 KB Output is correct
16 Correct 4 ms 1620 KB Output is correct
17 Correct 4 ms 1492 KB Output is correct
18 Correct 4 ms 1620 KB Output is correct
19 Correct 1214 ms 262144 KB Output is correct
20 Correct 1184 ms 262144 KB Output is correct
21 Correct 1135 ms 262144 KB Output is correct
22 Correct 1167 ms 262144 KB Output is correct
23 Correct 2520 ms 262144 KB Output is correct
24 Correct 95 ms 24524 KB Output is correct
25 Correct 64 ms 24472 KB Output is correct
26 Correct 133 ms 25000 KB Output is correct
27 Correct 144 ms 24956 KB Output is correct
28 Correct 171 ms 25004 KB Output is correct
29 Correct 66 ms 24792 KB Output is correct
30 Correct 65 ms 24748 KB Output is correct
31 Correct 85 ms 24452 KB Output is correct
32 Correct 40 ms 2088 KB Output is correct
33 Correct 87 ms 24552 KB Output is correct
34 Correct 208 ms 51940 KB Output is correct
35 Correct 225 ms 51992 KB Output is correct
36 Correct 179 ms 51724 KB Output is correct
37 Correct 144 ms 51760 KB Output is correct
38 Correct 145 ms 51764 KB Output is correct
39 Correct 191 ms 52632 KB Output is correct
40 Correct 205 ms 52484 KB Output is correct
41 Correct 275 ms 52704 KB Output is correct
42 Correct 302 ms 52628 KB Output is correct
43 Correct 339 ms 52612 KB Output is correct
44 Correct 383 ms 52732 KB Output is correct
45 Correct 370 ms 52856 KB Output is correct
46 Correct 405 ms 52768 KB Output is correct
47 Correct 428 ms 52700 KB Output is correct
48 Correct 382 ms 52812 KB Output is correct
49 Correct 157 ms 52352 KB Output is correct
50 Correct 167 ms 52328 KB Output is correct
51 Correct 171 ms 52172 KB Output is correct
52 Correct 149 ms 52140 KB Output is correct
53 Correct 170 ms 52436 KB Output is correct
54 Correct 289 ms 51036 KB Output is correct
55 Correct 233 ms 34636 KB Output is correct
56 Correct 214 ms 50552 KB Output is correct
57 Correct 1250 ms 262144 KB Output is correct
58 Correct 1225 ms 262144 KB Output is correct
59 Correct 1080 ms 262144 KB Output is correct
60 Correct 1085 ms 262144 KB Output is correct
61 Correct 1068 ms 262144 KB Output is correct
62 Correct 1058 ms 262144 KB Output is correct
63 Correct 950 ms 262144 KB Output is correct
64 Correct 909 ms 262144 KB Output is correct
65 Correct 2307 ms 262144 KB Output is correct
66 Correct 2330 ms 262144 KB Output is correct
67 Correct 2366 ms 262144 KB Output is correct
68 Correct 2456 ms 262144 KB Output is correct
69 Correct 2409 ms 262144 KB Output is correct
70 Correct 2481 ms 262144 KB Output is correct
71 Correct 2520 ms 262144 KB Output is correct
72 Correct 2494 ms 262144 KB Output is correct
73 Correct 783 ms 262144 KB Output is correct
74 Correct 867 ms 262144 KB Output is correct
75 Correct 759 ms 262144 KB Output is correct
76 Correct 803 ms 262144 KB Output is correct
77 Correct 836 ms 262144 KB Output is correct
78 Correct 1863 ms 262144 KB Output is correct
79 Correct 1256 ms 145836 KB Output is correct
80 Correct 1270 ms 259832 KB Output is correct