oj.uz

Submission #200501

# Submission time Handle Problem Language Result Execution time Memory
200501 2020-02-07T01:57:15 Z arnold518 Triple Jump (JOI19_jumps) C++14
100 / 100
 1078 ms 89104 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 = 5e5;
const ll INF = 1e18;

int N, Q;
ll A[MAXN+10], B[MAXN+10], ans[MAXN+10];
vector<pii> V;

struct Query { int l, r, p; };
Query query[MAXN+10];

struct Node
{
	ll A, B, BA;
	Node() : A(-INF), B(-INF), BA(-INF) {}
};

Node add(Node lc, Node rc)
{
	Node ret;
	ret.BA=max({lc.BA, rc.BA, lc.B+rc.A});
	ret.A=max(lc.A, rc.A);
	ret.B=max(lc.B, rc.B);
	return ret;
}

Node tree[MAXN*4+10];

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		tree[node].A=A[tl];
		tree[node].B=B[tl];
		tree[node].BA=A[tl]+B[tl];
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node]=add(tree[node*2], tree[node*2+1]);
}

void update(int node, int tl, int tr, int pos)
{
	if(tl==tr)
	{
		tree[node].A=A[tl];
		tree[node].B=B[tl];
		tree[node].BA=A[tl]+B[tl];
		return;
	}
	int mid=tl+tr>>1;
	if(pos<=mid) update(node*2, tl, mid, pos);
	else update(node*2+1, mid+1, tr, pos);
	tree[node]=add(tree[node*2], tree[node*2+1]);
}

Node qquery(int node, int tl, int tr, int l, int r)
{
	if(l<=tl && tr<=r) return tree[node];
	if(r<tl || tr<l) return Node();
	int mid=tl+tr>>1;
	return add(qquery(node*2, tl, mid, l, r), qquery(node*2+1, mid+1, tr, l, r));
}

int main()
{
	int i, j, k;
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%lld", &A[i]), B[i]=-INF;
	scanf("%d", &Q);
	for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;

	vector<int> S;
	for(i=1; i<=N; i++)
	{
		while(!S.empty() && A[S.back()]<=A[i]) V.push_back({S.back(), i}), S.pop_back();
		if(!S.empty()) V.push_back({S.back(), i});
		S.push_back(i);
	}

	sort(V.begin(), V.end(), greater<pii>());
	sort(query+1, query+Q+1, [&](const Query &p, const Query &q) { return p.l>q.l; });

	init(1, 1, N);

	//for(auto it : V) printf("%d %d\n", it.first, it.second);

	for(i=N, j=0, k=1; i>=1; i--)
	{
		for(; j<V.size() && V[j].first==i; j++)
		{
			int t=V[j].second*2-V[j].first;
			if(t>N) continue;
			B[t]=max(B[t], A[V[j].first]+A[V[j].second]);
			update(1, 1, N, t);
		}
		for(; k<=Q && query[k].l==i; k++)
		{
			ans[query[k].p]=qquery(1, 1, N, query[k].l, query[k].r).BA;
		}
	}
	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message

jumps.cpp: In function 'void init(int, int, int)':
jumps.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
jumps.cpp: In function 'void update(int, int, int, int)':
jumps.cpp:59:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
jumps.cpp: In function 'Node qquery(int, int, int, int, int)':
jumps.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:98:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<V.size() && V[j].first==i; j++)
         ~^~~~~~~~~
jumps.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
jumps.cpp:77:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &A[i]), B[i]=-INF;
                      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
jumps.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
jumps.cpp:79:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47328 KB Output is correct
2 Correct 28 ms 47352 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47352 KB Output is correct
5 Correct 29 ms 47352 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 29 ms 47248 KB Output is correct
8 Correct 30 ms 47352 KB Output is correct
9 Correct 29 ms 47352 KB Output is correct
10 Correct 29 ms 47352 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47328 KB Output is correct
2 Correct 28 ms 47352 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47352 KB Output is correct
5 Correct 29 ms 47352 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 29 ms 47248 KB Output is correct
8 Correct 30 ms 47352 KB Output is correct
9 Correct 29 ms 47352 KB Output is correct
10 Correct 29 ms 47352 KB Output is correct
11 Correct 434 ms 67168 KB Output is correct
12 Correct 430 ms 66936 KB Output is correct
13 Correct 427 ms 67120 KB Output is correct
14 Correct 424 ms 67168 KB Output is correct
15 Correct 415 ms 67260 KB Output is correct
16 Correct 438 ms 66552 KB Output is correct
17 Correct 432 ms 66424 KB Output is correct
18 Correct 434 ms 66428 KB Output is correct
19 Correct 419 ms 66936 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 54628 KB Output is correct
2 Correct 102 ms 52588 KB Output is correct
3 Correct 115 ms 53860 KB Output is correct
4 Correct 176 ms 54628 KB Output is correct
5 Correct 165 ms 54628 KB Output is correct
6 Correct 158 ms 54628 KB Output is correct
7 Correct 161 ms 54628 KB Output is correct
8 Correct 152 ms 54756 KB Output is correct
9 Correct 159 ms 54700 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47328 KB Output is correct
2 Correct 28 ms 47352 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47352 KB Output is correct
5 Correct 29 ms 47352 KB Output is correct
6 Correct 30 ms 47352 KB Output is correct
7 Correct 29 ms 47248 KB Output is correct
8 Correct 30 ms 47352 KB Output is correct
9 Correct 29 ms 47352 KB Output is correct
10 Correct 29 ms 47352 KB Output is correct
11 Correct 434 ms 67168 KB Output is correct
12 Correct 430 ms 66936 KB Output is correct
13 Correct 427 ms 67120 KB Output is correct
14 Correct 424 ms 67168 KB Output is correct
15 Correct 415 ms 67260 KB Output is correct
16 Correct 438 ms 66552 KB Output is correct
17 Correct 432 ms 66424 KB Output is correct
18 Correct 434 ms 66428 KB Output is correct
19 Correct 419 ms 66936 KB Output is correct
20 Correct 161 ms 54628 KB Output is correct
21 Correct 102 ms 52588 KB Output is correct
22 Correct 115 ms 53860 KB Output is correct
23 Correct 176 ms 54628 KB Output is correct
24 Correct 165 ms 54628 KB Output is correct
25 Correct 158 ms 54628 KB Output is correct
26 Correct 161 ms 54628 KB Output is correct
27 Correct 152 ms 54756 KB Output is correct
28 Correct 159 ms 54700 KB Output is correct
29 Correct 1050 ms 88924 KB Output is correct
30 Correct 852 ms 84960 KB Output is correct
31 Correct 859 ms 88796 KB Output is correct
32 Correct 1046 ms 89040 KB Output is correct
33 Correct 1025 ms 88868 KB Output is correct
34 Correct 1032 ms 86704 KB Output is correct
35 Correct 1078 ms 86300 KB Output is correct
36 Correct 1059 ms 86240 KB Output is correct
37 Correct 1030 ms 87784 KB Output is correct
38 Correct 837 ms 88804 KB Output is correct
39 Correct 794 ms 88972 KB Output is correct
40 Correct 805 ms 85616 KB Output is correct
41 Correct 812 ms 85076 KB Output is correct
42 Correct 817 ms 85068 KB Output is correct
43 Correct 820 ms 86896 KB Output is correct
44 Correct 858 ms 89036 KB Output is correct
45 Correct 825 ms 89048 KB Output is correct
46 Correct 825 ms 85864 KB Output is correct
47 Correct 813 ms 85420 KB Output is correct
48 Correct 801 ms 85420 KB Output is correct
49 Correct 851 ms 87520 KB Output is correct
50 Correct 934 ms 89104 KB Output is correct
51 Correct 869 ms 88964 KB Output is correct
52 Correct 855 ms 86368 KB Output is correct
53 Correct 881 ms 86144 KB Output is correct
54 Correct 862 ms 86076 KB Output is correct
55 Correct 894 ms 87788 KB Output is correct