Submission #742695

#	Time	Username	Problem	Language	Result	Execution time	Memory
742695		myrcella	Triple Jump (JOI19_jumps)	C++17	100 / 100	666 ms	67876 KiB

jumps

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 5e5+10;

int n;
int a[maxn];
deque <int> q;
vector <int> good[maxn];
pii tree[maxn*4];
int add[maxn*4];
vector <pair<pii,int> > que;
int ans[maxn];

void init(int c,int cl,int cr) {
	if (cl==cr) tree[c] = {a[cl],a[cl]},add[c] = 0;
	else {
		int mid=cl+cr>>1;
		init(c<<1,cl,mid);
		init(c<<1|1,mid+1,cr);
		int tmp = max(tree[c<<1].fi,tree[c<<1|1].fi);
		tree[c] = {tmp,tmp};
	}
	
}

void push_down(int c) {
	tree[c<<1].fi = max(tree[c<<1].fi,tree[c<<1].se+add[c]);
	add[c<<1] = max(add[c<<1],add[c]);
	tree[c<<1|1].fi = max(tree[c<<1|1].fi,tree[c<<1|1].se+add[c]);
	add[c<<1|1] = max(add[c<<1|1],add[c]);
	add[c] = 0;
}

void update(int c,int cl,int cr,int l,int r,int val) {
	if (l<=cl and cr<=r) {
		tree[c].fi = max(tree[c].fi,tree[c].se+val);
		add[c] = max(add[c],val);
		return;
	}
	int mid=cl+cr>>1;
	if (add[c]!=0) push_down(c);
	if (l<=mid) update(c<<1,cl,mid,l,r,val);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r,val);
	tree[c].fi = max(tree[c<<1].fi,tree[c<<1|1].fi);
	return;
}

int query(int c,int cl,int cr,int l,int r) {
	if (l<=cl and cr<=r) return tree[c].fi;
	int mid=cl+cr>>1;
	if (add[c]!=0) push_down(c);
	int ret = 0;
	if (l<=mid) ret = query(c<<1,cl,mid,l,r);
	if (r>mid) ret = max(ret,query(c<<1|1,mid+1,cr,l,r));
	return ret;
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,1,n+1) cin>>a[i];
	for (int i=n;i>0;i--) {
		while (!q.empty() and a[q.back()]<=a[i]) good[i].pb(q.back()),q.pop_back();
		if (!q.empty()) good[i].pb(q.back());
		q.push_back(i);
	}
//	rep(i,1,n+1) for (auto it:good[i]) cout<<i<<" "<<it<<endl;
	init(1,1,n);
	int _;cin>>_;
	rep(i,0,_) {
		int l,r;
		cin>>l>>r;
		que.pb({{l,r},i});
	}
	sort(ALL(que));reverse(ALL(que));
	int l=n;
	rep(i,0,_) {
		while (l>=que[i].fi.fi) {
			for (auto r:good[l]) if (r+r-l<=n) update(1,1,n,r+r-l,n,a[l]+a[r]);
			l--;
		}
		ans[que[i].se] = query(1,1,n,que[i].fi.fi,que[i].fi.se);
	}
	rep(i,0,_) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, int, int)':
jumps.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=cl+cr>>1;
      |           ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid=cl+cr>>1;
      |          ~~^~~
jumps.cpp: In function 'int query(int, int, int, int, int)':
jumps.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int mid=cl+cr>>1;
      |          ~~^~~

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