oj.uz

Submission #891045

# Submission time Handle Problem Language Result Execution time Memory
891045 2023-12-22T06:48:07 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 4944 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 = 2e5 + 11;
const ll inf = 1e9 + 7;
ll tt = 1;
ll a[N];

void solve() {
	ll n, m; cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> a[i];
	while (m--) {
		ll l, r, x; cin >> l >> r >> x;
		set<ll> st, st1;
		for (int i = l;i <= r;i++) {
			st1.insert(a[i]);
		}
		bool f = 1;
		for (int i = r;i >= l;i--) {
			st1.erase(a[i]);
			auto to = st.lower_bound(a[i]);
			if (to != st.ed && to != st.bg) {
				to--;
//				cout << *to << sp << a[i] << en;
				if (a[i] + *to > x) f = 0;
			}
			if (!st1.empty()) {
//				cout << *(--st1.ed) << sp << a[i] << en;
				if (a[i] + *(--st1.ed) > x && *(--st1.ed) > a[i]) f = 0;
			}
			st.insert(a[i]);
		}
		cout << f << 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 21 ms 508 KB Output is correct
7 Correct 22 ms 348 KB Output is correct
8 Correct 42 ms 348 KB Output is correct
9 Correct 17 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 21 ms 508 KB Output is correct
7 Correct 22 ms 348 KB Output is correct
8 Correct 42 ms 348 KB Output is correct
9 Correct 17 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 385 ms 600 KB Output is correct
12 Correct 1320 ms 800 KB Output is correct
13 Correct 1530 ms 816 KB Output is correct
14 Correct 2596 ms 1112 KB Output is correct
15 Correct 2605 ms 1364 KB Output is correct
16 Execution timed out 3058 ms 828 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 4944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 1880 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 21 ms 508 KB Output is correct
7 Correct 22 ms 348 KB Output is correct
8 Correct 42 ms 348 KB Output is correct
9 Correct 17 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 385 ms 600 KB Output is correct
12 Correct 1320 ms 800 KB Output is correct
13 Correct 1530 ms 816 KB Output is correct
14 Correct 2596 ms 1112 KB Output is correct
15 Correct 2605 ms 1364 KB Output is correct
16 Execution timed out 3058 ms 828 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 21 ms 508 KB Output is correct
7 Correct 22 ms 348 KB Output is correct
8 Correct 42 ms 348 KB Output is correct
9 Correct 17 ms 344 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 385 ms 600 KB Output is correct
12 Correct 1320 ms 800 KB Output is correct
13 Correct 1530 ms 816 KB Output is correct
14 Correct 2596 ms 1112 KB Output is correct
15 Correct 2605 ms 1364 KB Output is correct
16 Execution timed out 3058 ms 828 KB Time limit exceeded
17 Halted 0 ms 0 KB -