oj.uz

Submission #560671

# Submission time Handle Problem Language Result Execution time Memory
560671 2022-05-11T20:09:10 Z aryan12 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 114 ms 17480 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
vector<int> a(N), val(N, -1);
vector<array<int, 2> > g[N];
int seg[N * 4];

void Update(int l, int r, int pos, int qpos, int qval)
{
	seg[pos] = max(seg[pos], qval);
	if(l == r)
	{
		return;
	}
	int mid = (l + r) >> 1;
	if(qpos <= mid) Update(l, mid, pos * 2, qpos, qval);
	else Update(mid + 1, r, pos * 2 + 1, qpos, qval);
}

int Query(int l, int r, int pos, int ql, int qr)
{
	if(ql <= l && r <= qr)
	{
		return seg[pos];
	}
	if(ql > r || l > qr)
	{
		return 0;
	}
	int mid = (l + r) >> 1;
	return max(Query(l, mid, pos * 2, ql, qr), Query(mid + 1, r, pos * 2 + 1, ql, qr));
}

struct query
{
	int l, r, idx, ans, value;
};

vector<query> queries(N);

bool cmp(query x, query y)
{
	if(x.r != y.r)
	{
		return x.r < y.r;
	}
	return x.l < y.l;
}

bool cmp2(query x, query y)
{
	return x.idx < y.idx; 
}

void Solve() 
{
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++)
	{
		cin >> queries[i].l >> queries[i].r >> queries[i].value;
		queries[i].idx = i;
		queries[i].ans = 0;
	}
	stack<pair<int, int> > s;
	s.push({val[1], 1});
	for(int i = 2; i <= n; i++)
	{
		while(!s.empty() && s.top().first <= a[i])
		{
			s.pop();
		}
		if(!s.empty())
		{
			val[i] = s.top().second;
		}
		s.push({a[i], i});
	}
	for(int i = 1; i <= n; i++)
	{
		if(val[i] != -1)
		{
			// cout << i << " -> " << val[i] << ", with wt -> " << a[val[i]] + a[i] << "\n";
			g[i].push_back({val[i], a[val[i]] + a[i]});
		}
	}
	sort(queries.begin() + 1, queries.begin() + 1 + q, cmp);
	int pos = 1;
	for(int i = 1; i <= n; i++)
	{
		for(auto [to, wt]: g[i])
		{
			Update(1, n, 1, to, wt);
		}
		while(pos != q + 1 && queries[pos].r == i)
		{
			// cout << "pos = " << pos << ", idx = " << queries[pos].idx << "\n";
			queries[pos].ans = Query(1, n, 1, queries[pos].l, queries[pos].r);
			// cout << "queries[i].ans = " << queries[pos].ans << "\n";
			// cout << "queries[i].l = " << queries[pos].l << ", queries[i].r = " << queries[pos].r << "\n";
			pos++;
		}
	}
	sort(queries.begin() + 1, queries.begin() + 1 + q, cmp2);
	for(int i = 1; i <= q; i++)
	{
		// cout << "queries[i].ans = " << queries[i].ans << "\n";
		if(queries[i].ans <= queries[i].value)
		{
			cout << "1\n";
		}
		else
		{
			cout << "0\n";
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8180 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8184 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 4 ms 8176 KB Output is correct
6 Correct 5 ms 8196 KB Output is correct
7 Correct 4 ms 8316 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8180 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8180 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8184 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 4 ms 8176 KB Output is correct
6 Correct 5 ms 8196 KB Output is correct
7 Correct 4 ms 8316 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8180 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 8 ms 8532 KB Output is correct
13 Correct 7 ms 8532 KB Output is correct
14 Correct 9 ms 8580 KB Output is correct
15 Correct 9 ms 8552 KB Output is correct
16 Correct 9 ms 8404 KB Output is correct
17 Correct 8 ms 8324 KB Output is correct
18 Correct 8 ms 8404 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 13780 KB Output is correct
2 Correct 114 ms 15404 KB Output is correct
3 Correct 100 ms 10268 KB Output is correct
4 Correct 96 ms 10332 KB Output is correct
5 Correct 113 ms 10280 KB Output is correct
6 Correct 93 ms 10484 KB Output is correct
7 Correct 95 ms 10480 KB Output is correct
8 Correct 87 ms 12264 KB Output is correct
9 Correct 59 ms 9628 KB Output is correct
10 Correct 85 ms 11820 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8180 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8184 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 4 ms 8176 KB Output is correct
6 Correct 5 ms 8196 KB Output is correct
7 Correct 4 ms 8316 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8180 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 8 ms 8532 KB Output is correct
13 Correct 7 ms 8532 KB Output is correct
14 Correct 9 ms 8580 KB Output is correct
15 Correct 9 ms 8552 KB Output is correct
16 Correct 9 ms 8404 KB Output is correct
17 Correct 8 ms 8324 KB Output is correct
18 Correct 8 ms 8404 KB Output is correct
19 Runtime error 20 ms 17480 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8180 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8184 KB Output is correct
4 Correct 5 ms 8148 KB Output is correct
5 Correct 4 ms 8176 KB Output is correct
6 Correct 5 ms 8196 KB Output is correct
7 Correct 4 ms 8316 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 5 ms 8180 KB Output is correct
11 Correct 6 ms 8276 KB Output is correct
12 Correct 8 ms 8532 KB Output is correct
13 Correct 7 ms 8532 KB Output is correct
14 Correct 9 ms 8580 KB Output is correct
15 Correct 9 ms 8552 KB Output is correct
16 Correct 9 ms 8404 KB Output is correct
17 Correct 8 ms 8324 KB Output is correct
18 Correct 8 ms 8404 KB Output is correct
19 Runtime error 22 ms 16612 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -