Submission #940870

#	Time	Username	Problem	Language	Result	Execution time	Memory
940870		qin	Triple Jump (JOI19_jumps)	C++17	100 / 100	773 ms	87892 KiB

jumps

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int base = 1;
struct seg{
		struct Node{
				int val, p, a;
				Node(){ val = 0, p = 0, a = 0; }
		};
		vv<Node> t;
		void init(int n, vv<int> &tt){
				while(base < n) base <<= 1;
				t.resize(base<<1);
				for(int i = 1; i <= n; ++i) t[i+base-1].a = tt[i];
				for(int i = base-1; i; --i) t[i].a = max(t[i<<1].a, t[i<<1|1].a);
		}
		void add(int i, int val){ t[i].val = max(t[i].val, t[i].a+val), t[i].p = max(t[i].p, val); }
		void push(int i){ if(t[i].p) add(i<<1, t[i].p), add(i<<1|1, t[i].p), t[i].p = 0; }
		void update(int i, int s, int e, int x, int y, int val){
				if(x <= s && e <= y) return void(add(i, val));
				int mid = (s+e)>>1; push(i);
				if(x <= mid) update(i<<1, s, mid, x, y, val);
				if(mid < y) update(i<<1|1, mid+1, e, x, y, val);
				t[i].val = max(t[i<<1].val, t[i<<1|1].val);
		}
		int query(int i, int s, int e, int x, int y){
				if(x <= s && e <= y) return t[i].val;
				int mid = (s+e)>>1, result = 0; push(i);
				if(x <= mid) result = max(result, query(i<<1, s, mid, x, y));
				if(mid < y) result = max(result, query(i<<1|1, mid+1, e, x, y));
				t[i].val = max(t[i<<1].val, t[i<<1|1].val);
				return result;
		}
};
void answer(){
		int n; scanf("%d", &n);
		vv<int> t(n+1);
		for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
		
		vv<vv<int>> v(n+1); //valid
		vv<int> st; st.emplace_back(n-1);
		for(int i = n-2; i; --i){
				while(ssize(st) && t[st.back()] <= t[i]) v[i].emplace_back(st.back()), st.pop_back();
				if(ssize(st)) v[i].emplace_back(st.back());
				st.emplace_back(i);
		}
		int q; scanf("%d", &q);
		vv<vv<pii>> qr(n+1);
		vv<int> result(q);
		for(int i = 0, a, b; i < q; ++i) scanf("%d%d", &a, &b), qr[a].emplace_back(b, i);
		
		seg seg; seg.init(n, t);
		for(int i = n-2; i; --i){
				for(int &j : v[i]) if(2*j-i <= n) seg.update(1, 1, base, 2*j-i, n, t[i]+t[j]);//, printf("%d %d\n", i, j);
				for(pii &u : qr[i]) result[u.se] = seg.query(1, 1, base, i, u.fi);
		}
		for(int i = 0; i < q; ++i) printf("%d\n", result[i]);
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void answer()':
jumps.cpp:59:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jumps.cpp:61:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
      |                               ~~~~~^~~~~~~~~~~~~
jumps.cpp:70:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
jumps.cpp:73:41: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   for(int i = 0, a, b; i < q; ++i) scanf("%d%d", &a, &b), qr[a].emplace_back(b, i);
      |                                    ~~~~~^~~~~~~~~~~~~~~~

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