oj.uz

Submission #414322

# Submission time Handle Problem Language Result Execution time Memory
414322 2021-05-30T10:33:05 Z CSQ31 Triple Jump (JOI19_jumps) C++14
100 / 100
 1091 ms 108428 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 5e5+5;
vector<ll>a(MAXN);
int n,Q;
vector<ll>t(4*MAXN),amx(4*MAXN),lazy(4*MAXN,-INF);
void upd(int v,int l,int r,int tl,int tr,ll val){
	if(l > r)return;
	if(l == tl && tr == r){
		lazy[v] = max(lazy[v],val);
		t[v] = max(t[v],amx[v]+lazy[v]);
		return;
	}
	int tm = (tl+tr)/2;
    upd(2*v,l,min(r,tm),tl,tm,val),
    upd(2*v+1,max(tm+1,l),r,tm+1,tr,val);
	t[v] = max({t[2*v],t[2*v+1],lazy[v]+amx[v]});
}
PII query(int v,int l,int r,int tl,int tr){
	if(l > r)return {0,0};
	if(l == tl && r == tr)return {t[v],amx[v]};
	int tm = (tl+tr)/2;
	PII a = query(2*v,l,min(r,tm),tl,tm);
	PII b = query(2*v+1,max(tm+1,l),r,tm+1,tr);
	PII res;
	res.fi = max({a.fi,b.fi,max(a.se,b.se)+lazy[v]});
	res.se = max(a.se,b.se);
	return res;
}
void build(int v,int l,int r){
	if(l == r){
		amx[v] = a[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	amx[v] = max(amx[2*v],amx[2*v+1]);
}
struct que{
	int l,r,idx;
	bool operator<(const que &z){return z.l < l;}
	que(){}
};
int main()
{
	owo
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>Q;
	vector<que>q(Q);
	vii can(n+1);
	for(int i=0;i<Q;i++){
		cin>>q[i].l>>q[i].r;
		q[i].idx = i;
	}
	stack<pii>stk;
	build(1,1,n);
	for(int i=1;i<=n;i++){
		while(!stk.empty() && stk.top().fi < a[i])stk.pop();
		if(!stk.empty())can[stk.top().se].pb(i);
		stk.push({a[i],i});
	}
	while(!stk.empty())stk.pop();
	for(int i=n;i;i--){
		while(!stk.empty() && stk.top().fi < a[i])stk.pop();
		if(!stk.empty())can[i].pb(stk.top().se);
		stk.push({a[i],i});
	}
	vector<ll>ans(Q);
	int ptr = 0;
	sort(all(q));
	for(int i=n;i>0;i--){
		int st = ptr;
		while(ptr<sz(q) && q[ptr].l >= i)ptr++;
		for(int x:can[i]){
			int rg = 2*x-i;
			if(rg<=n)upd(1,rg,n,1,n,a[i]+a[x]);
		}
		for(int j=st;j<ptr;j++){
			ans[q[j].idx] = query(1,q[j].l,q[j].r,1,n).fi;
		}
	}
	for(int i=0;i<Q;i++)cout<<ans[i]<<'\n';
	
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51116 KB Output is correct
2 Correct 23 ms 51112 KB Output is correct
3 Correct 23 ms 51124 KB Output is correct
4 Correct 23 ms 51196 KB Output is correct
5 Correct 24 ms 51148 KB Output is correct
6 Correct 23 ms 51192 KB Output is correct
7 Correct 23 ms 51100 KB Output is correct
8 Correct 24 ms 51124 KB Output is correct
9 Correct 23 ms 51172 KB Output is correct
10 Correct 23 ms 51180 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51116 KB Output is correct
2 Correct 23 ms 51112 KB Output is correct
3 Correct 23 ms 51124 KB Output is correct
4 Correct 23 ms 51196 KB Output is correct
5 Correct 24 ms 51148 KB Output is correct
6 Correct 23 ms 51192 KB Output is correct
7 Correct 23 ms 51100 KB Output is correct
8 Correct 24 ms 51124 KB Output is correct
9 Correct 23 ms 51172 KB Output is correct
10 Correct 23 ms 51180 KB Output is correct
11 Correct 355 ms 66256 KB Output is correct
12 Correct 360 ms 66280 KB Output is correct
13 Correct 353 ms 66148 KB Output is correct
14 Correct 360 ms 66288 KB Output is correct
15 Correct 356 ms 66372 KB Output is correct
16 Correct 360 ms 65616 KB Output is correct
17 Correct 349 ms 65604 KB Output is correct
18 Correct 361 ms 65532 KB Output is correct
19 Correct 367 ms 66244 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 62276 KB Output is correct
2 Correct 122 ms 63696 KB Output is correct
3 Correct 120 ms 63732 KB Output is correct
4 Correct 186 ms 62364 KB Output is correct
5 Correct 186 ms 62472 KB Output is correct
6 Correct 184 ms 62332 KB Output is correct
7 Correct 180 ms 62300 KB Output is correct
8 Correct 194 ms 62404 KB Output is correct
9 Correct 185 ms 62344 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51116 KB Output is correct
2 Correct 23 ms 51112 KB Output is correct
3 Correct 23 ms 51124 KB Output is correct
4 Correct 23 ms 51196 KB Output is correct
5 Correct 24 ms 51148 KB Output is correct
6 Correct 23 ms 51192 KB Output is correct
7 Correct 23 ms 51100 KB Output is correct
8 Correct 24 ms 51124 KB Output is correct
9 Correct 23 ms 51172 KB Output is correct
10 Correct 23 ms 51180 KB Output is correct
11 Correct 355 ms 66256 KB Output is correct
12 Correct 360 ms 66280 KB Output is correct
13 Correct 353 ms 66148 KB Output is correct
14 Correct 360 ms 66288 KB Output is correct
15 Correct 356 ms 66372 KB Output is correct
16 Correct 360 ms 65616 KB Output is correct
17 Correct 349 ms 65604 KB Output is correct
18 Correct 361 ms 65532 KB Output is correct
19 Correct 367 ms 66244 KB Output is correct
20 Correct 185 ms 62276 KB Output is correct
21 Correct 122 ms 63696 KB Output is correct
22 Correct 120 ms 63732 KB Output is correct
23 Correct 186 ms 62364 KB Output is correct
24 Correct 186 ms 62472 KB Output is correct
25 Correct 184 ms 62332 KB Output is correct
26 Correct 180 ms 62300 KB Output is correct
27 Correct 194 ms 62404 KB Output is correct
28 Correct 185 ms 62344 KB Output is correct
29 Correct 1091 ms 103108 KB Output is correct
30 Correct 902 ms 108356 KB Output is correct
31 Correct 913 ms 108428 KB Output is correct
32 Correct 1086 ms 104908 KB Output is correct
33 Correct 1081 ms 104988 KB Output is correct
34 Correct 1073 ms 102644 KB Output is correct
35 Correct 1071 ms 102340 KB Output is correct
36 Correct 1071 ms 102352 KB Output is correct
37 Correct 1074 ms 103912 KB Output is correct
38 Correct 862 ms 104916 KB Output is correct
39 Correct 869 ms 105044 KB Output is correct
40 Correct 845 ms 101700 KB Output is correct
41 Correct 851 ms 101092 KB Output is correct
42 Correct 888 ms 101036 KB Output is correct
43 Correct 885 ms 102816 KB Output is correct
44 Correct 919 ms 104908 KB Output is correct
45 Correct 920 ms 104932 KB Output is correct
46 Correct 989 ms 101764 KB Output is correct
47 Correct 890 ms 101464 KB Output is correct
48 Correct 882 ms 101408 KB Output is correct
49 Correct 916 ms 103444 KB Output is correct
50 Correct 962 ms 105028 KB Output is correct
51 Correct 992 ms 104988 KB Output is correct
52 Correct 940 ms 102508 KB Output is correct
53 Correct 949 ms 102288 KB Output is correct
54 Correct 947 ms 102208 KB Output is correct
55 Correct 945 ms 103900 KB Output is correct