Submission #528890

#	Time	Username	Problem	Language	Result	Execution time	Memory
528890		AriaH	Triple Jump (JOI19_jumps)	C++17	100 / 100	1265 ms	133952 KiB

jumps

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

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

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, q, A[N];

vector < int > vec[N];

vector < pii > Q[N];

ll Ans[N], Mn[N << 2], Mx[N << 2], seg[N << 2], lz[N << 2];

void build(int v = 1, int tl = 1, int tr = n)
{
	if(tl == tr)
	{
		seg[v] = A[tl];
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

void Push(int v, ll x)
{
	Mn[v] += x;
	Mx[v] += x;
	lz[v] += x;
	seg[v] += x;
}

void S(int v, int tl, int tr)
{
	if(tl == tr) return;
	Push(v << 1, lz[v]);
	Push(v << 1 | 1, lz[v]);
	lz[v] = 0;
}

void upd(int l, int r, ll x, int v = 1, int tl = 1, int tr = n)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r || Mn[v] >= x) return;
	if(l <= tl && tr <= r && Mn[v] == Mx[v])
	{
		Push(v, x - Mn[v]);
		return;
	}
	int mid = (tl + tr) >> 1;
	upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr);
	seg[v] = max({seg[v << 1], seg[v << 1 | 1]});
	Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
	Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
	S(v, tl, tr);
	if(l > tr || r < tl || l > r) return -inf;
	if(l <= tl && tr <= r) return seg[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v << 1, tl, mid), get(l, r, v << 1 | 1, mid + 1, tr));
}

int main()
{
	fast_io;
	vector < int > S;
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> A[i];
		while(SZ(S) && A[S.back()] < A[i])
		{
			vec[S.back()].push_back(i);
			S.pop_back();
		}
		if(SZ(S))
		{
			vec[S.back()].push_back(i);
		}
		S.push_back(i);
	}
	cin >> q;
	for(int i = 1; i <= q; i ++)
	{
		int fir, sec;
		cin >> fir >> sec;
		Q[fir].push_back({sec, i});
	}
	build();
	for(int i = n; ~(i - 1); i --)
	{
		for(auto id : vec[i])
		{
			///printf("i = %d id = %d\n", i, id);
			upd(id * 2 - i, n, A[i] + A[id]);
		}
		for(auto cu : Q[i])
		{
			int id = cu.S, r = cu.F;
			Ans[id] = get(i + 2, r);
		}
		/*printf("i = %d\n", i);
		for(int j = 1; j <= n; j ++)
		{
			for(int k = j; k <= n; k ++)
			{
				printf("j = %d k = %d get = %lld\n", j, k, get(j, k));
			}
		}
		printf("\n");
		*/
	}
	for(int i = 1; i <= q; i ++)
	{
		cout << Ans[i] << endl;
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54