Submission #944289

#	Time	Username	Problem	Language	Result	Execution time	Memory
944289		beepbeepsheep	Triple Jump (JOI19_jumps)	C++17	27 / 100	149 ms	46212 KiB

jumps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
        
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=5e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll arr[maxn];
stack<ll> s;
vector<ii> v;
struct node{
	ll s,e,m,ab,c,abc;
	node *l, *r;
	node(ll _s, ll _e){
		s=_s,e=_e,m=(s+e)>>1,ab=-inf,c=-inf,abc=2*-inf;
		if (s!=e) l=new node(s,m),r=new node(m+1,e);
	}
	void upd(ll x, ll v, ll type){
		if (s==e){
			if (type==1){
				ab=v;
			} else c=v;
			abc=ab+c;
			return;
		}
		if (x>m) r->upd(x,v,type);
		else l->upd(x,v,type);
		ab=max(l->ab,r->ab),c=max(l->c,r->c);
		abc=max({l->abc,r->abc,l->ab+r->c});
	}
	ll query(ll x, ll y){
		iii t=process(x,y);
		return get<2>(t);
	}
	iii process(ll x, ll y){
		if (x<=s && e<=y) return {ab,c,abc};
		if (x>m) return r->process(x,y);
		if (y<=m) return l->process(x,y);
		ll lab,lc,labc,rab,rc,rabc;
		tie(lab,lc,labc)=l->process(x,y);
		tie(rab,rc,rabc)=r->process(x,y);
		iii t={max(lab,rab),max(lc,rc),max({labc,rabc,lab+rc})};
		return t;
	}
}*root;
ll ans[maxn];
vector<iii> q;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	cin>>n;
	root=new node(1,n);
	for (int i=1;i<=n;i++){
		cin>>arr[i];
		root->upd(i,arr[i],2);
	}
	for (int i=1;i<=n;i++){
		while (s.size() && arr[s.top()]<=arr[i]){
			if (2*i-s.top()<=n) //check that it is in range
				v.emplace_back(s.top(),i);
			s.pop();
		}
		if (s.size()){
			if (2*i-s.top()<=n)
				v.emplace_back(s.top(),i);
		}
		s.emplace(i);
	}
	sort(v.rbegin(),v.rend());
	ll qu,l,r;
	cin>>qu;
	for (int i=1;i<=qu;i++){
		cin>>l>>r;
		q.emplace_back(l,r,i);
	}
	sort(q.rbegin(),q.rend());
	ll ptr=0;
	for (auto [l,r,idx]:q){
		cerr<<l<<' '<<r<<'x'<<endl;
		while (ptr!=v.size() && l<=v[ptr].first){
			ll a,b;
			tie(a,b)=v[ptr];
			cerr<<a<<' '<<b<<endl;
			root->upd(2*b-a,arr[a]+arr[b],1);
			ptr++;
		}
		ans[idx]=root->query(1,r);
	}
	for (int i=1;i<=qu;i++) cout<<ans[i]<<endl;
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:99:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   while (ptr!=v.size() && l<=v[ptr].first){
      |          ~~~^~~~~~~~~~

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