oj.uz

Submission #891165

# Submission time Handle Problem Language Result Execution time Memory
891165 2023-12-22T09:16:12 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 1127 ms 123776 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//#pragma GCC optimization("g", on)
//#pragma GCC optimization("03")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse,-fgcse-lm")
//#pragma GCC optimize("-ftree-pre,-ftree-vrp")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define aboba ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define br break;
#define sp " "
#define en "\n"
#define pb push_back
#define sz size()
#define bg begin()
#define ed end()
#define in insert
#define ss second
#define ff first
#define setp(a) cout << fixed; cout << setprecision(a);
#define all(v) v.begin(), v.end()
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef double db;
typedef tree<
    long long,
    null_type,
    less_equal<long long>,
    rb_tree_tag,
    tree_order_statistics_node_update> orset;

void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
ll bp(ll x, ll y, ll z) { ll res = 1; while (y) { if (y & 1) { res = (res * x) % z; y--; } x = (x * x) % z; y >>= 1; } return res; }
// C(n, k) = ((fact[n] * bp(fact[k], mod - 2)) % mod * bp(fact[n - k], mod - 2)) % mod;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; }

const ll N = 1e6 + 11;
const ll inf = 1e9 + 7;
ll tt = 1;
ll a[N];
vector<pair<pll, ll>> g[N];
ll ans[N];
ll t[N * 4];

void upd(ll v, ll tl, ll tr, ll pos, ll x) {
	if (tl == tr) {
		t[v] = x;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (pos <= tm) upd(v * 2, tl, tm, pos, x);
	else upd(v * 2 + 1, tm + 1, tr, pos, x);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

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

void solve() {
	ll n, m; cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	for (int i = 1;i <= m;i++) {
		ll l, r, x; cin >> l >> r >> x;
		g[r].pb({{l, x}, i});
	}
	stack<ll> st;
	for (int i = 1;i <= n;i++) {
		while (!st.empty() && a[st.top()] <= a[i]) st.pop();
		ll x = (st.empty() ? 0 : st.top());
		st.push(i);
//		cout << x << en;
		upd(1, 1, n, x, a[i] + a[x]);
		for (auto to : g[i]) {
			ll l = to.ff.ff, x = to.ff.ss;
			ans[to.ss] = (get(1, 1, n, l, i) <= x);
		}
	}
	for (int i = 1;i <= m;i++) {
		cout << ans[i] << en;
	}
}
   
int main() {      
    aboba    
//    freopen("cownomics");
//    precalc();
//    cin >> tt;
    for (int i = 1;i <= tt;i++) {
		solve();
    }
}

Compilation message

sortbooks.cpp: In function 'void freopen(std::string)':
sortbooks.cpp:47:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:47:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29204 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29016 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29204 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29016 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 9 ms 29528 KB Output is correct
14 Correct 9 ms 29560 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 8 ms 29532 KB Output is correct
17 Correct 8 ms 29292 KB Output is correct
18 Correct 8 ms 29272 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1088 ms 90884 KB Output is correct
2 Correct 1127 ms 123600 KB Output is correct
3 Correct 1099 ms 123632 KB Output is correct
4 Correct 1102 ms 123776 KB Output is correct
5 Incorrect 1036 ms 113520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 34640 KB Output is correct
2 Correct 80 ms 37204 KB Output is correct
3 Incorrect 72 ms 36696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29204 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29016 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 9 ms 29528 KB Output is correct
14 Correct 9 ms 29560 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 8 ms 29532 KB Output is correct
17 Correct 8 ms 29292 KB Output is correct
18 Correct 8 ms 29272 KB Output is correct
19 Correct 171 ms 49028 KB Output is correct
20 Correct 167 ms 48724 KB Output is correct
21 Correct 149 ms 49392 KB Output is correct
22 Correct 149 ms 49236 KB Output is correct
23 Correct 150 ms 49408 KB Output is correct
24 Incorrect 143 ms 47624 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29204 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29016 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 9 ms 29528 KB Output is correct
14 Correct 9 ms 29560 KB Output is correct
15 Correct 9 ms 29532 KB Output is correct
16 Correct 8 ms 29532 KB Output is correct
17 Correct 8 ms 29292 KB Output is correct
18 Correct 8 ms 29272 KB Output is correct
19 Correct 1088 ms 90884 KB Output is correct
20 Correct 1127 ms 123600 KB Output is correct
21 Correct 1099 ms 123632 KB Output is correct
22 Correct 1102 ms 123776 KB Output is correct
23 Incorrect 1036 ms 113520 KB Output isn't correct
24 Halted 0 ms 0 KB -