Submission #1259554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259554		_rain_	Triple Jump (JOI19_jumps)	C++20	100 / 100	736 ms	91724 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask)>>x)&(1))
#define sz(x) (int)(x).size()

template<class X,class Y>	
	bool maximize(X &x , Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x , Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class X,class Y>
	int Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 5e5;
	int a[N + 2] , ans[N + 2];
	int n , q;
	vector<pair<int,int>>block[N+2];
	vector<pair<int,int>>add[N+2];

	void insert_block(int l, int r){
		add[l].push_back({2 * r - l , a[l] + a[r]});
		return;
	}

	LL st_val[N*4+2] , st_upd[N*4+2] , st[N*4+2];
	
		void reup(int id){
			maximize(st[id] , st_val[id] + st_upd[id]);
			return;
		}
		
		void build(int id,int l,int r){
			if (l==r) st_val[id] = st[id] = a[l];
			else{
				int m = (l + r) / 2;
				build(id*2,l,m);
				build(id*2+1,m+1,r);
				st_val[id] = max(st_val[id*2] , st_val[id*2+1]);
				reup(id);
			}
			return;
		}
		
		void pushdown(int id){
			LL &t = st_upd[id];
				maximize(st_upd[id*2],t);
				maximize(st_upd[id*2+1],t);
				reup(id*2) , reup(id*2+1);
			return;
		}
		
		void upd(int id , int l, int r , int u , int v ,LL val){
			if (l > v || r < u) return;
			if (u <= l && r <= v) {
				maximize(st_upd[id] , val);
				reup(id);
				return;
			}
			int m = (l + r)/2;
			pushdown(id);
			upd(id*2,l,m,u,v,val);
			upd(id*2+1,m+1,r,u,v,val);
			st[id] = max(st[id*2] , st[id*2+1]);
		}
		LL Get(int id , int l, int r , int u , int v){
			if (l > v || r < u) return 0;
			if (u <= l && r <= v) {
				reup(id);
				return st[id];
			}
			int m = (l+r)/2;
			pushdown(id);
			return max(Get(id*2,l,m,u,v) , Get(id*2+1,m+1,r,u,v));
		}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n;
		for(int i = 1; i <= n; ++i) cin >> a[i];
		cin >> q;
		for(int i = 1; i <= q; ++i){
			int l , r; cin >> l >> r;
			block[l].push_back({r , i});
		}
		vector<int>st;
		for(int i = n; i >= 1; --i){
			while (st.size() && a[st.back()] <= a[i]){
				insert_block(i , st.back());
				st.pop_back();
			}
			if (st.size()) insert_block(i , st.back());
			st.push_back(i);
		}
		build(1,1,n);
		for(int i = n; i >= 1; --i){
			for(auto& x : add[i]) upd(1,1,n,x.first,n,x.second);
			for(auto& x : block[i]) ans[x.second] = Get(1,1,n,i,x.first);
		}
		for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:95:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:96:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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