Submission #158234

#	Time	Username	Problem	Language	Result	Execution time	Memory
158234		ZwariowanyMarcin	Triple Jump (JOI19_jumps)	C++14	100 / 100	1142 ms	52560 KiB

jumps

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)	
	
		
using namespace std;

const int nax = 6e5 + 111;
const int inf = 1e9 + 111;
const int pod = (1 << 19);

int n;
int a[nax];
int q, l, r;
int res[nax];

struct query {
	int l, r, id;
};

vector <query> v;
vector <pair<int, int>> pairs;

stack <pair<int, int>> stos; // value, indeks

struct tree {
	int lewo, prawo, best;
	tree() {
		lewo = -inf;
		prawo = -inf;
		best = -inf;
	}
};  
					
tree t[2 * pod];

void add(int u, int c) {
	u += pod;
	t[u].lewo = max(t[u].lewo, c);
	t[u].best = max(t[u].best, t[u].lewo + t[u].prawo);
	u /= 2;
	while(u) {
		t[u].lewo = max(t[2 * u].lewo, t[2 * u + 1].lewo);
		t[u].best = max({t[2 * u].best, t[2 * u + 1].best, t[2 * u].lewo + t[2 * u + 1].prawo});
		u /= 2;
	}
}

tree merge(const tree &a, const tree &b) {
	tree c = tree();
	c.lewo = max(a.lewo, b.lewo);
	c.prawo = max(a.prawo, b.prawo);
	c.best = max({a.best, b.best, a.lewo + b.prawo});
	return c;
}

tree Query(int x, int y, int u = 1, int l = 0, int r = pod - 1) {
	if(x <= l && r <= y)  
		return t[u];
	int m = (l + r) / 2;
	tree ans = tree();
	if(x <= m)
		ans = merge(ans, Query(x, y, 2 * u, l, m));
	if(m < y)
		ans = merge(ans, Query(x, y, 2 * u + 1, m + 1, r));
	return ans;
}
					
int main() {	
	scanf("%d", &n);
	FOR(i, 1, n) 
		scanf("%d", &a[i]);
	FOR(i, 1, n) {
		while(!stos.empty() && stos.top().fi <= a[i]) {
			pairs.pb(mp(stos.top().se, i));
			stos.pop();
		}
		if(!stos.empty())
			pairs.pb(mp(stos.top().se, i));
		stos.push(mp(a[i], i));
	}
	sort(pairs.begin(), pairs.end());
			
	scanf("%d", &q);
	FOR(i, 1, q) {
		scanf("%d %d", &l, &r);
		query x = {l, r, i};
		v.pb(x);
	}
	sort(v.begin(), v.end(), [](query a, query b) {
		return a.l < b.l;
	});
	
	FOR(i, 0, pod - 1) {
		t[i] = tree();
		if(1 <= i && i <= n)
			t[i + pod].prawo = a[i];
	}
	for(int i = pod - 1; 1 <= i; --i) {
		t[i] = tree();
		t[i].prawo = max(t[2 * i].prawo, t[2 * i + 1].prawo);
	}
	int wsk = ss(v) - 1;
	int p = ss(pairs) - 1;
	for(int i = n; 1 <= i; --i) {
		while(p >= 0 && pairs[p].fi == i) {
			int c = 2 * pairs[p].se - pairs[p].fi;
			if(c <= n)
				add(c, a[pairs[p].fi] + a[pairs[p].se]);
			p -= 1;
		}
		while(wsk >= 0 && v[wsk].l == i) {
			res[v[wsk].id] = Query(v[wsk].l, v[wsk].r).best;
			wsk -= 1;
		}
	}
	FOR(i, 1, q)
		printf("%d\n", res[i]);
	
	
	
				
	return 0;
}

Compilation message (stderr)

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:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[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:97: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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54