oj.uz

Submission #560665

# Submission time Handle Problem Language Result Execution time Memory
560665 2022-05-11T19:50:58 Z aryan12 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 16364 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;
	Update(l, mid, pos * 2, qpos, qval);
	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, cmp2);
	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)
		{
			queries[pos].ans = Query(1, n, 1, queries[pos].l, queries[pos].r);
			pos++;
		}
	}
	sort(queries.begin() + 1, queries.begin() + 1 + q, cmp);
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8056 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8056 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 16364 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 3087 ms 13300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8056 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8056 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -