oj.uz

Submission #238904

# Submission time Handle Problem Language Result Execution time Memory
238904 2020-06-13T12:34:02 Z arnold518 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 1069 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

struct Query { int l, r, k; };

int N, M, A[MAXN+10];
Query B[MAXN+10];
int ans[MAXN+10];

vector<int> tree[MAXN*4+10];
int tree2[MAXN*4+10];
vector<pii> todo[MAXN*4+10];

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		tree[node].push_back(A[tl]);
		tree2[node]=0;
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node].resize(tree[node*2].size()+tree[node*2+1].size());
	merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin());

	auto it=lower_bound(tree[node*2+1].begin(), tree[node*2+1].end(), tree[node*2].back());
	if(it!=tree[node*2+1].begin()) tree2[node]=*(--it)+tree[node*2].back();
	tree2[node]=max({tree2[node], tree2[node*2], tree2[node*2+1]});
}

void query(int node, int tl, int tr, int l, int r, vector<int> &V)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		V.push_back(node);
		return;
	}
	int mid=tl+tr>>1;
	query(node*2, tl, mid, l, r, V);
	query(node*2+1, mid+1, tr, l, r, V);
}

void solve(int node, int tl, int tr)
{
	int i, j;
	sort(todo[node].begin(), todo[node].end(), greater<pii>());

	i=tree[node].size()-1;
	for(auto it : todo[node])
	{
		for(; i>=0 && tree[node][i]>=it.first; i--);
		if(i>=0) ans[it.second]=max(ans[it.second], it.first+tree[node][i]);
	}

	if(tl==tr) return;
	int mid=tl+tr>>1;
	solve(node*2, tl, mid);
	solve(node*2+1, mid+1, tr);
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);
	for(i=1; i<=M; i++) scanf("%d%d%d", &B[i].l, &B[i].r, &B[i].k);

	init(1, 1, N);
	for(i=1; i<=M; i++)
	{
		vector<int> V;
		query(1, 1, N, B[i].l, B[i].r, V);

		int val=0;
		for(auto it : V)
		{
			ans[i]=max(ans[i], tree2[it]);
			todo[it].push_back({val, i});
			val=max(val, tree[it].back());
		}
	}

	solve(1, 1, N);

	for(i=1; i<=M; i++) printf("%d\n", ans[i]<=B[i].k);
}

Compilation message

sortbooks.cpp: In function 'void init(int, int, int)':
sortbooks.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp: In function 'void query(int, int, int, int, int, std::vector<int>&)':
sortbooks.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp: In function 'void solve(int, int, int)':
sortbooks.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sortbooks.cpp:54:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:72:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sortbooks.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:75:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:76:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d%d", &B[i].l, &B[i].r, &B[i].k);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188228 KB Output is correct
2 Correct 110 ms 188152 KB Output is correct
3 Correct 111 ms 188280 KB Output is correct
4 Correct 106 ms 188280 KB Output is correct
5 Correct 108 ms 188280 KB Output is correct
6 Correct 108 ms 188280 KB Output is correct
7 Correct 116 ms 188408 KB Output is correct
8 Correct 122 ms 188280 KB Output is correct
9 Correct 105 ms 188280 KB Output is correct
10 Correct 106 ms 188328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188228 KB Output is correct
2 Correct 110 ms 188152 KB Output is correct
3 Correct 111 ms 188280 KB Output is correct
4 Correct 106 ms 188280 KB Output is correct
5 Correct 108 ms 188280 KB Output is correct
6 Correct 108 ms 188280 KB Output is correct
7 Correct 116 ms 188408 KB Output is correct
8 Correct 122 ms 188280 KB Output is correct
9 Correct 105 ms 188280 KB Output is correct
10 Correct 106 ms 188328 KB Output is correct
11 Correct 117 ms 188792 KB Output is correct
12 Correct 113 ms 189324 KB Output is correct
13 Correct 120 ms 189480 KB Output is correct
14 Correct 118 ms 189816 KB Output is correct
15 Correct 126 ms 189688 KB Output is correct
16 Correct 119 ms 189560 KB Output is correct
17 Correct 113 ms 189336 KB Output is correct
18 Correct 128 ms 189504 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 815 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 219736 KB Output is correct
2 Correct 448 ms 222788 KB Output is correct
3 Correct 495 ms 223712 KB Output is correct
4 Correct 515 ms 222064 KB Output is correct
5 Correct 454 ms 221556 KB Output is correct
6 Correct 357 ms 225412 KB Output is correct
7 Correct 349 ms 225268 KB Output is correct
8 Correct 455 ms 217320 KB Output is correct
9 Correct 196 ms 195440 KB Output is correct
10 Correct 386 ms 217392 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188228 KB Output is correct
2 Correct 110 ms 188152 KB Output is correct
3 Correct 111 ms 188280 KB Output is correct
4 Correct 106 ms 188280 KB Output is correct
5 Correct 108 ms 188280 KB Output is correct
6 Correct 108 ms 188280 KB Output is correct
7 Correct 116 ms 188408 KB Output is correct
8 Correct 122 ms 188280 KB Output is correct
9 Correct 105 ms 188280 KB Output is correct
10 Correct 106 ms 188328 KB Output is correct
11 Correct 117 ms 188792 KB Output is correct
12 Correct 113 ms 189324 KB Output is correct
13 Correct 120 ms 189480 KB Output is correct
14 Correct 118 ms 189816 KB Output is correct
15 Correct 126 ms 189688 KB Output is correct
16 Correct 119 ms 189560 KB Output is correct
17 Correct 113 ms 189336 KB Output is correct
18 Correct 128 ms 189504 KB Output is correct
19 Correct 1069 ms 255868 KB Output is correct
20 Correct 1058 ms 255708 KB Output is correct
21 Correct 865 ms 259056 KB Output is correct
22 Correct 842 ms 258960 KB Output is correct
23 Correct 889 ms 258852 KB Output is correct
24 Correct 736 ms 259440 KB Output is correct
25 Correct 856 ms 259576 KB Output is correct
26 Correct 879 ms 261312 KB Output is correct
27 Correct 909 ms 261180 KB Output is correct
28 Correct 920 ms 258592 KB Output is correct
29 Correct 937 ms 255952 KB Output is correct
30 Correct 908 ms 255960 KB Output is correct
31 Correct 952 ms 256708 KB Output is correct
32 Correct 920 ms 256596 KB Output is correct
33 Correct 937 ms 256572 KB Output is correct
34 Correct 653 ms 262144 KB Output is correct
35 Correct 667 ms 262144 KB Output is correct
36 Correct 666 ms 262144 KB Output is correct
37 Correct 648 ms 262144 KB Output is correct
38 Correct 684 ms 262144 KB Output is correct
39 Correct 814 ms 249804 KB Output is correct
40 Correct 558 ms 229484 KB Output is correct
41 Correct 773 ms 247552 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 188228 KB Output is correct
2 Correct 110 ms 188152 KB Output is correct
3 Correct 111 ms 188280 KB Output is correct
4 Correct 106 ms 188280 KB Output is correct
5 Correct 108 ms 188280 KB Output is correct
6 Correct 108 ms 188280 KB Output is correct
7 Correct 116 ms 188408 KB Output is correct
8 Correct 122 ms 188280 KB Output is correct
9 Correct 105 ms 188280 KB Output is correct
10 Correct 106 ms 188328 KB Output is correct
11 Correct 117 ms 188792 KB Output is correct
12 Correct 113 ms 189324 KB Output is correct
13 Correct 120 ms 189480 KB Output is correct
14 Correct 118 ms 189816 KB Output is correct
15 Correct 126 ms 189688 KB Output is correct
16 Correct 119 ms 189560 KB Output is correct
17 Correct 113 ms 189336 KB Output is correct
18 Correct 128 ms 189504 KB Output is correct
19 Runtime error 815 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -