Submission #1273407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273407		nthvn	Triple Jump (JOI19_jumps)	C++20	100 / 100	763 ms	104148 KiB

jumps

#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N= 5e5+5;
int n, a[N], q;
vector<pii> qr[N];
int fans[N];
int tb[N][25];

int getmx(int l, int r){
	int j = __lg(r-l+1);
	return max(tb[l][j], tb[r-(1<<j)+1][j]);
}


struct SegTree{
	int tr[4*N], lz[4*N];
	
	void app_lz(int id, int l, int r, int v){
		tr[id] = max(tr[id], v+getmx(l,r));
		lz[id] = max(lz[id], v);
	}
	void down(int id, int l, int r){
		if(!lz[id]) return;
		int mid=(l+r)>>1;
		app_lz(2*id,l,mid,lz[id]);
		app_lz(2*id+1,mid+1,r,lz[id]);
		lz[id] = 0;
	}
	void update(int id, int l, int r, int t_l, int t_r, int v){
		if(l>t_r||r<t_l) return;
		if(t_l<=l&&r<=t_r) {
			tr[id] = max(tr[id], v+getmx(l,r));
			lz[id] = max(lz[id], v);
			return;
		}
		int mid=(l+r)>>1;
		down(id,l,r);
		update(2*id,l,mid,t_l,t_r,v);
		update(2*id+1,mid+1,r,t_l,t_r,v);
		tr[id] = max(tr[2*id], tr[2*id+1]);
	}
	int get(int id, int l, int r, int t_l, int t_r){
		if(l>t_r||r<t_l) return 0;
		if(t_l<=l&&r<=t_r) return tr[id];
		int mid =(l+r)>>1;
		down(id,l,r);
		return max(get(2*id,l,mid,t_l,t_r), get(2*id+1,mid+1,r,t_l,t_r));
	}
}st;



void preprocess(){
	for(int i=n;i>=1;i--){
		tb[i][0] = a[i];
		for(int j=1;i+(1<<j)-1<=n;j++){
			tb[i][j] = max(tb[i][j-1], tb[i+(1<<(j-1))][j-1]);
		}
	}
	static int st[N];
	for(int i=1;i<=n;i++){
		while(st[0]&&a[st[st[0]]]<=a[i]){
			// cerr<<st[st[0]]<<" "<<i<<"\n";
			qr[st[st[0]--]].pb({i,0});
		}
		if(st[0]){
			qr[st[st[0]]].pb({i,0});
		}
		st[++st[0]] = i;
	}
}

void solve(){
	for(int i=1;i<=n;i++) sort(all(qr[i]),[&](pii &a, pii &b){
		return a.se < b.se;
	});
	for(int t= n; t>=1;t--){
		for(auto &x: qr[t]){
			int r= x.fi, id = x.se;
			if(!id){
				int k = 2*r-t;
				st.update(1,1,n,k,n,a[t]+a[r]);
			}
			else{
				fans[id] = st.get(1,1,n,1,r);
			}
		}
	}
	for(int i=1;i<=q;i++) cout<<fans[i]<<"\n";
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	cin>>q;
	for(int i=1;i<=q;i++) {
		int l,r; cin>>l>>r;
		qr[l].pb({r,i});
	}
	preprocess();
	solve();
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:104:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:105:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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