oj.uz

Submission #242371

# Submission time Handle Problem Language Result Execution time Memory
242371 2020-06-27T12:09:33 Z errorgorn Triple Jump (JOI19_jumps) C++14
27 / 100
 148 ms 35428 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,q;
ll arr[200005];
 
vector<int> stk;

vector<ii> good;

struct Q{
	int l,r;
	int idx;
	
	Q(int a,int b,int c){
		l=a,r=b,idx=c;
	}
};

vector<Q> queries;

int ans[200005];

struct dat{
	ll ab=-1e18,c=0,abc=0;
	
	void merge(dat i,dat j){
		c=max(i.c,j.c);
		ab=max(i.ab,j.ab);
		abc=MAX(i.abc,j.abc,i.ab+j.c);
	}
	
	void reset(){
		ab=-1e18;
		c=0;
		ab=0;
	}
};

dat glob;

struct node{
	int s,e,m;
	dat val;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			val.merge(l->val,r->val);
		}
		else{
			val.c=arr[s];
		}
	}
	
	void update(int i,ll j){
		if (s==e) val.ab=max(val.ab,j);
		else{
			if (i<=m) l->update(i,j);
			else r->update(i,j);
			
			val.merge(l->val,r->val);
		}
	}
	
	void query(int i,int j){
		if (s==i && e==j) glob.merge(glob,val);
		else if (j<=m) l->query(i,j);
		else if (m<i) r->query(i,j);
		else l->query(i,m),r->query(m+1,j);
	}
} *root;
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x];
	
	root=new node(0,200005);
	
	rep(x,0,n){
		while (!stk.empty() && arr[stk.back()]<=arr[x]){
			good.push_back({stk.back(),x});
			stk.pop_back();
		}
		
		if (!stk.empty()) good.push_back({stk.back(),x});
		stk.push_back(x);
	}
	
	cin>>q;
	int a,b;
	rep(x,0,q){
		cin>>a>>b;
		a--,b--;
		queries.push_back(Q(a,b,x));
	}
	
	sort(all(good),[](ii i,ii j){
		return i.fi<j.fi;
	});
	
	sort(all(queries),[](Q &i,Q &j){
		return i.l>j.l;
	});
	
	for (auto &it:queries){
		while (!good.empty() && it.l<=good.back().fi){
			int pos=good.back().se*2-good.back().fi-1;
			
			//cout<<pos<<" "<<good.back().fi<<" "<<good.back().se<<endl;
			if (pos<200005) root->update(pos,arr[good.back().fi]+arr[good.back().se]);
			
			good.pop_back();
		}
		
		glob.reset();
		root->query(0,it.r);
		ans[it.idx]=glob.abc;
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message

jumps.cpp: In constructor 'node::node(int, int)':
jumps.cpp:78:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Incorrect 28 ms 25428 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 148 ms 35428 KB Output is correct
2 Correct 95 ms 31336 KB Output is correct
3 Correct 100 ms 32104 KB Output is correct
4 Correct 145 ms 35304 KB Output is correct
5 Correct 146 ms 35300 KB Output is correct
6 Correct 131 ms 35300 KB Output is correct
7 Correct 132 ms 35300 KB Output is correct
8 Correct 131 ms 35300 KB Output is correct
9 Correct 137 ms 35300 KB Output is correct

Subtask #4
0 / 54.0

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