Submission #151010

#	Time	Username	Problem	Language	Result	Execution time	Memory
151010		username	Triple Jump (JOI19_jumps)	C++14	100 / 100	1669 ms	122268 KiB

jumps

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define pb push_back
#define f first
#define s second
#define MAX(x,y) (x=max(x,(y)))
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)

const int lg=19,maxn=1<<lg;
int n,q,a[maxn],res[maxn],dat[2*maxn],add[2*maxn],sp[lg][maxn];
vector<pii>qrs[maxn];
vector<int>ops[maxn];

int gmx(int l,int r){
	int k=__lg(r-l);
	return max(sp[k][l],sp[k][r-(1<<k)]);
}

void init(int l,int r,int idx){
	add[idx]=0;
	if(l+1==r)dat[idx]=a[l];
	else init(l,mid,lch),init(mid,r,rch),dat[idx]=max(dat[lch],dat[rch]);
}

void ch(int l,int r,int idx,int k){MAX(add[idx],k),MAX(dat[idx],k+gmx(l,r));}

void psh(int l,int r,int idx){ch(l,mid,lch,add[idx]),ch(mid,r,rch,add[idx]);}

void ch(int l,int r,int idx,int a,int b,int k){
	if(b<=l||r<=a)return;
	else if(a<=l&&r<=b)ch(l,r,idx,k);
	else psh(l,r,idx),ch(l,mid,lch,a,b,k),ch(mid,r,rch,a,b,k),dat[idx]=max(dat[lch],dat[rch]);
}

int qr(int l,int r,int idx,int a,int b){
	if(b<=l||r<=a)return 0;
	else if(a<=l&&r<=b)return dat[idx];
	else return psh(l,r,idx),max(qr(l,mid,lch,a,b),qr(mid,r,rch,a,b));
}

main(){
	IOS;
	cin>>n;
	RREP(i,n,0)cin>>a[i],sp[0][i]=a[i];
	REP(i,1,lg)REP(j,0,n)if(j+(1<<i-1)<n)sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<i-1)]);
	cin>>q;
	REP(i,0,q){
		int l,r;cin>>r>>l,l=n-l,r=n-r;
		qrs[r].pb({l,i});
	}
	REP(d,0,2){
		stack<int>stk;
		REP(_,0,n){
			int i=d?n-1-_:_;
			while(stk.size()&&a[stk.top()]<a[i])stk.pop();
			if(stk.size())d?ops[stk.top()].pb(i):ops[i].pb(stk.top());
			stk.push(i);
		}
	}
	init(0,n,0);
	REP(i,0,n){
		REP(j,0,ops[i].size()){
			int p=ops[i][j];
			ch(0,n,0,0,2*p-i+1,a[i]+a[p]);
		}
		REP(j,0,qrs[i].size()){
			pii&qq=qrs[i][j];
			res[qq.s]=qr(0,n,0,qq.f,i+1);
		}
	}
	REP(i,0,q)cout<<res[i]<<endl;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, int, int)':
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:30:14: note: in expansion of macro 'mid'
  else init(l,mid,lch),init(mid,r,rch),dat[idx]=max(dat[lch],dat[rch]);
              ^~~
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:30:28: note: in expansion of macro 'mid'
  else init(l,mid,lch),init(mid,r,rch),dat[idx]=max(dat[lch],dat[rch]);
                            ^~~
jumps.cpp: In function 'void psh(int, int, int)':
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:35:36: note: in expansion of macro 'mid'
 void psh(int l,int r,int idx){ch(l,mid,lch,add[idx]),ch(mid,r,rch,add[idx]);}
                                    ^~~
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:35:57: note: in expansion of macro 'mid'
 void psh(int l,int r,int idx){ch(l,mid,lch,add[idx]),ch(mid,r,rch,add[idx]);}
                                                         ^~~
jumps.cpp: In function 'void ch(int, int, int, int, int, int)':
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:40:25: note: in expansion of macro 'mid'
  else psh(l,r,idx),ch(l,mid,lch,a,b,k),ch(mid,r,rch,a,b,k),dat[idx]=max(dat[lch],dat[rch]);
                         ^~~
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:40:43: note: in expansion of macro 'mid'
  else psh(l,r,idx),ch(l,mid,lch,a,b,k),ch(mid,r,rch,a,b,k),dat[idx]=max(dat[lch],dat[rch]);
                                           ^~~
jumps.cpp: In function 'int qr(int, int, int, int, int)':
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:46:36: note: in expansion of macro 'mid'
  else return psh(l,r,idx),max(qr(l,mid,lch,a,b),qr(mid,r,rch,a,b));
                                    ^~~
jumps.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
jumps.cpp:46:52: note: in expansion of macro 'mid'
  else return psh(l,r,idx),max(qr(l,mid,lch,a,b),qr(mid,r,rch,a,b));
                                                    ^~~
jumps.cpp: At global scope:
jumps.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
jumps.cpp: In function 'int main()':
jumps.cpp:53:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  REP(i,1,lg)REP(j,0,n)if(j+(1<<i-1)<n)sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<i-1)]);
                                ~^~
jumps.cpp:53:78: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  REP(i,1,lg)REP(j,0,n)if(j+(1<<i-1)<n)sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<i-1)]);
                                                                             ~^~
jumps.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
jumps.cpp:70:3: note: in expansion of macro 'REP'
   REP(j,0,ops[i].size()){
   ^~~
jumps.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
jumps.cpp:74:3: note: in expansion of macro 'REP'
   REP(j,0,qrs[i].size()){
   ^~~

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