Submission #191505

#	Time	Username	Problem	Language	Result	Execution time	Memory
191505		sealnot123	Triple Jump (JOI19_jumps)	C++14	100 / 100	1576 ms	67188 KiB

jumps

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 500005;
vector<int> Q[N];
int ANS[N], L[N], R[N];
LL seg[4*N], lazy[4*N], MA[4*N], num[N];
vector<int> sta;
int n, q;

void build(int l = 1, int r = n, int now = 1){
	if(l == r){
		seg[now] = MA[now] = num[l];
		return ;
	}
	int m = (l+r)>>1;
	build(l, m, now<<1); build(m+1, r, now<<1|1);
	seg[now] = MA[now] = max(MA[now<<1], MA[now<<1|1]);
}

void push(int l, int r, int now){
	if(lazy[now]){
		seg[now] = max(seg[now], MA[now] + lazy[now]);
		if(l!=r){
			lazy[now<<1] = max(lazy[now<<1], lazy[now]);
			lazy[now<<1|1] = max(lazy[now<<1|1], lazy[now]);
		}
		lazy[now] = 0;
	}
}

void add(int ll, int rr, int v, int l = 1, int r = n, int now = 1){
	push(l, r, now);
	if(ll > rr || l > rr || r < ll) return ;
	if(l >= ll && r <= rr){
		lazy[now] = v;
		push(l, r, now);
		return ;
	}
	int m = (l+r)>>1;
	add(ll, rr, v, l, m, now<<1);
	add(ll, rr, v, m+1, r, now<<1|1);
	seg[now] = max(seg[now<<1], seg[now<<1|1]);
}

int get(int ll, int rr, int l = 1, int r = n, int now = 1){
	push(l, r, now);
	if(ll > rr || l > rr || r < ll) return 0;
	if(l >= ll && r <= rr) return seg[now];
	int m = (l+r)>>1;
	return max(get(ll, rr, l, m, now<<1), get(ll, rr, m+1, r, now<<1|1));
}	

int main(){
	int i,j,k,l,a,b,c,d;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%lld",&num[i]);
	build();
	scanf("%d",&q);
	for(i=1;i<=q;i++){
		scanf("%d%d",&L[i],&R[i]);
		Q[L[i]].pb(i);
	}
	for(i = n; i > 0; i--){
		while(!sta.empty()){
			a = sta.back();
			add(2*a-i, n, num[sta.back()]+num[i]);
			if(num[sta.back()] < num[i]) sta.pop_back();
			else break;
		}
		sta.pb(i);
		for(int it : Q[i]){
			ANS[it] = get(i, R[it]);
		}
	}
	for(i=1;i<=q;i++) printf("%d\n",ANS[i]);
    return 0;
}
/*
5
5 4 4 5 4
1
1 5

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13
*/

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:65:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
        ^
jumps.cpp:65:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
jumps.cpp:65:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
jumps.cpp:65:16: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                ^
jumps.cpp:65:18: warning: unused variable 'c' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                  ^
jumps.cpp:65:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
jumps.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
jumps.cpp:67:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld",&num[i]);
                    ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
jumps.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&L[i],&R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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