oj.uz

Submission #941707

# Submission time Handle Problem Language Result Execution time Memory
941707 2024-03-09T10:25:11 Z emptypringlescan Triple Jump (JOI19_jumps) C++17
27 / 100
 112 ms 49600 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long arr[500005];
struct node{
	int s,e,m;
	long long val,con,suf;
	node *l, *r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=con=0;
		suf=arr[s];
		if(s!=e){
			l=new node(S,m);
			r=new node(m+1,E);
			suf=max(l->suf,r->suf);
		}
	}
	void update(int S, long long V){
		if(s==e){
			con=max(con,V);
			val=con+suf;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		con=max(l->con,r->con);
		val=max({l->val,r->val,l->con+r->suf});
	}
	pair<long long,pair<long long,long long> > query(int S, int E){
		if(S<=s&&e<=E) return {val,{con,suf}};
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else{
			pair<long long,pair<long long,long long> > a=l->query(S,m),b=r->query(m+1,E),ret;
			ret.first=max({a.first,b.first,a.second.first+b.second.second});
			ret.second.first=max(a.second.first,b.second.first);
			ret.second.second=max(a.second.second,b.second.second);
			return ret;
		}
	}
} *root;
int32_t main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    root=new node(0,n-1);
    int q;
    cin >> q;
    vector<pair<long long,int> > mono;
    vector<pair<pair<int,int>,long long> > yay;
    for(int i=0; i<n; i++){
		while(!mono.empty()&&mono.back().first<=arr[i]){
			int a=mono.back().second;
			if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
			mono.pop_back();
		}
		if(!mono.empty()){
			int a=mono.back().second;
			if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
		}
		mono.push_back({arr[i],i});
	}
	sort(yay.begin(),yay.end());
	pair<pair<int,int>,int> qu[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first.first >> qu[i].first.second;
		qu[i].first.first--; qu[i].first.second--;
		qu[i].second=i;
	}
	sort(qu,qu+q,greater<pair<pair<int,int>,int> >());
	long long ans[q];
	for(int i=0; i<q; i++){
		while(!yay.empty()&&yay.back().first.first>=qu[i].first.first){
			root->update(yay.back().first.second,yay.back().second);
			yay.pop_back();
		}
		ans[qu[i].second]=root->query(0,qu[i].first.second).first;
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 48372 KB Output is correct
2 Correct 70 ms 43204 KB Output is correct
3 Correct 71 ms 44640 KB Output is correct
4 Correct 110 ms 48572 KB Output is correct
5 Correct 108 ms 49600 KB Output is correct
6 Correct 104 ms 47548 KB Output is correct
7 Correct 107 ms 47984 KB Output is correct
8 Correct 108 ms 47564 KB Output is correct
9 Correct 108 ms 47900 KB Output is correct

Subtask #4
0 / 54.0

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