oj.uz

Submission #138113

# Submission time Handle Problem Language Result Execution time Memory
138113 2019-07-29T11:27:40 Z sebinkim Triple Jump (JOI19_jumps) C++14
0 / 100
 122 ms 45816 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

struct node{
	int lv, rv, mv;
	
	node() : lv(-1e9), rv(-1e9), mv(-1e9) {}
	node(int lv, int rv) : lv(lv), rv(rv), mv(-1e9) {}
	
	node operator + (node &n)
	{
		node ret;
		
		ret.lv = max(lv, n.lv);
		ret.rv = max(rv, n.rv);
		ret.mv = max(max(mv, n.mv), lv + n.rv);
		
		return ret;
	}
};

struct segtree{
	node T[1101010];
	int sz = 1 << 19;
	
	void init(int n, int *X)
	{
		int i;
		
		for(i=1; i<=n; i++){
			T[sz + i] = node(-1e9, X[i]);
		}
		
		for(i=sz-1; i; i--){
			T[i] = T[i << 1] + T[i << 1 | 1];
		}
	}
	
	void update(int p, int v)
	{
		p += sz;
		
		if(T[p].lv >= v) return;
		T[p] = node(v, T[p].rv);
		
		for(p>>=1; p; p>>=1){
			T[p] = T[p << 1] + T[p << 1 | 1];
		}
	}
	
	int getval(int l, int r)
	{
		node lv, rv;
		
		l += sz; r += sz;
		
		for(; l<=r; ){
			if(l & 1) lv = lv + T[l];
			if(~r & 1) rv = T[r] + rv;
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
		
		return (lv + rv).mv;
	}
};

segtree T;
vector <pii> V[505050], Q[505050];
vector <int> S;
int X[505050], A[505050];
int n;

int main()
{
	int q, i, j, t, l, r;
	
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		scanf("%d", X + i);
		for(; !S.empty(); S.pop_back()){
			j = S.back(); t = i + i - j - 1;
			if(t <= n) V[j].emplace_back(t, X[j] + X[i]);
			if(X[t] > X[i]) break;
		}
		S.push_back(i);
	}
	
	T.init(n, X);
	
	scanf("%d", &q);
	
	for(i=1; i<=q; i++){
		scanf("%d%d", &l, &r);
		Q[l].emplace_back(r, i);
	}
	
	for(i=n; i>=1; i--){
		for(pii &t: V[i]){
			T.update(t.first, t.second);
		}
		
		for(pii &q: Q[i]){
			A[q.second] = T.getval(i, q.first);
		}
	}
	
	for(i=1; i<=q; i++){
		printf("%d\n", A[i]);
	}
	
	return 0;
}

Compilation message

jumps.cpp: In member function 'int segtree::getval(int, int)':
jumps.cpp:63:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
jumps.cpp:64:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
jumps.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", X + i);
   ~~~~~^~~~~~~~~~~~~
jumps.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
jumps.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 45816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

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