Submission #1207518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207518		nguyn	Triple Jump (JOI19_jumps)	C++20	100 / 100	633 ms	46700 KiB

jumps

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 5e5 + 5;

int n, a[N], q, res[N];

struct Query {
	int l, r, id;

	bool operator < (const Query &o) const {
		return l > o.l; 
	}
} que[N];

bool cmp(pii x, pii y) {
	return x.F > y.F; 
}

struct Node {
	int res, lef, rig; 

	Node() {
		res = lef = rig = 0;
	}

	Node operator + (const Node &o) const {
		Node ret = *this;
		ret.res = max({ret.res, o.res, lef + o.rig}); 
		ret.lef = max({ret.lef, o.lef}); 
		ret.rig = max({ret.rig, o.rig}); 	
		return ret;
	}
} st[4 * N];

void build(int id, int l, int r) {
	if (l == r) {
		st[id].res = st[id].rig = a[l]; 
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = st[id * 2] + st[id * 2 + 1]; 
}

void update(int id, int l, int r, int pos, int val) {
	if (l == r) {
		st[id].lef = max(st[id].lef, val); 
		st[id].res = st[id].lef + st[id].rig; 
		return;
	}
	int mid = (l + r) / 2;
	if (pos <= mid) update(id * 2, l, mid, pos, val); 
	else update(id * 2 + 1, mid + 1, r, pos, val);
	st[id] = st[id * 2] + st[id * 2 + 1]; 
}

Node get(int id, int l, int r, int u, int v) {
	if (l > v || r < u) return Node(); 
	if (u <= l && r <= v) {
		return st[id]; 
	}
	int mid = (l + r) / 2;
	return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    }
    cin >> q; 
    for (int i = 1; i <= q; i++) {
    	cin >> que[i].l >> que[i].r; 
    	que[i].id = i;
    }
    stack<int> s;
    vector<pii> vec;
    for (int i = 1; i <= n; i++) {
    	while(!s.empty() && a[i] >= a[s.top()]) {
    		vec.pb({s.top(), i}); 
    		s.pop(); 
    	}
    	if (!s.empty()) {
    		vec.pb({s.top(), i}); 
    	}
    	s.push(i);
    }
    build(1, 1, n);
    sort(que + 1, que + 1 + q);
    sort(vec.begin(), vec.end(), cmp);  
    int j = 0;
    for (int i = 1; i <= q; i++) {
    	while(j < (int)vec.size() && vec[j].F >= que[i].l) {
    		int x = vec[j].F; 
    		int y = vec[j].S; 
    		int z = y + y - x;
    		if (z <= n) update(1, 1, n, z, a[x] + a[y]); 
    		j++;
    	}
    	res[que[i].id] = get(1, 1, n, que[i].l, que[i].r).res;
    }
    for (int i = 1; i <= q; i++) {
    	cout << res[i] << '\n';
    }
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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