oj.uz

Submission #143001

# Submission time Handle Problem Language Result Execution time Memory
143001 2019-08-12T14:38:07 Z ryansee Triple Jump (JOI19_jumps) C++14
100 / 100
 1653 ms 118412 KB 
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (500006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = (ss); ii < (ll)(ee); ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define MSB(bm) (63-__builtin_clzll((bm)))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
// #define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
// #define degug(...) 42
#define cerr if(0)cout
#endif
ll n,q,A[MAXN];
spi Q[MAXN];
ll ans[MAXN]; ll pmx[MAXN];
vector<pi>v;
struct node {
	int s,e,m;
	ll v,o;ll add;
	node *l,*r;
	node(ll _S,ll _E){
		s=_S,e=_E,m=(s+e)>>1ll;
		v=o=0;add=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			o=max(l->o,r->o);
			v=max(l->v,r->v);
		} else v=o=A[s],l=r=0;
	}
	void update(ll x,ll y,ll nval){
		value();
		if(s==x&&e==y) { add=max(add,nval); return; }
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else l->update(x,m,nval),r->update(m+1,y,nval);
		v=max(l->value(),r->value());
	}
	ll value() {
		if(add) v=max(v,o+add);
		if(s^e){
			l->add=max(l->add,add);
			r->add=max(r->add,add);
		}
		// add=0;
		return v;
	}
	ll rmq(ll x,ll y){
		value();
		if(s==x&&e==y)return v;
		if(x>m)return r->rmq(x,y);
		else if(y<=m)return l->rmq(x,y);
		else return max(l->rmq(x,m),r->rmq(m+1,y));
	}
} *seg;
int main() // array size ah!!
{
	FAST
	cin>>n;
	FOR(i,1,n+1)cin>>A[i]; for(ll i=n;i>=1;--i)pmx[i]=max(pmx[i+1],A[i]);
	cin>>q;
	FOR(i,1,q+1)cin>>Q[i].s.f>>Q[i].s.s,Q[i].f=i;
	sort(Q+1,Q+q+1,[](spi x,spi y){return x.s.f>y.s.f;});
	stack<pi>stk;
	FOR(i,1,n+1){
		while(stk.size()) {
			v.eb(stk.top().s,i);
			if(stk.top().f<=A[i]) stk.pop(); else break;
		}
		stk.emplace(A[i],i);
	}
	sort(all(v)); seg=new node(1,n);
	FOR(i,1,q+1) {
		ll ind=Q[i].f,x=Q[i].s.f,y=Q[i].s.s;
		while(v.size()&&v.back().f>=x) {
			ll a,b;tie(a,b)=v.back();v.pop_back();
			if(b+b-a<=n) seg->update(b+b-a,n,A[a]+A[b]);
						// cerr<<b+b-a<<' '<<n<<' '<<A[a]+A[b]<<'\n';
		} assert(x+2<=y);
		ans[ind]=seg->rmq(x+2,y);
	}
	FOR(i,1,q+1) cout<<ans[i]<<'\n';
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
* 
* 
5
5 4 4 5 4
1
1 5
* 
*

*/

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:19:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = (ss); ii < (ll)(ee); ++ii)
                         ^
jumps.cpp:88:2: note: in expansion of macro 'FOR'
  FOR(i,1,n+1)cin>>A[i]; for(ll i=n;i>=1;--i)pmx[i]=max(pmx[i+1],A[i]);
  ^~~
jumps.cpp:88:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,1,n+1)cin>>A[i]; for(ll i=n;i>=1;--i)pmx[i]=max(pmx[i+1],A[i]);
                         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 388 KB Output is correct
10 Correct 2 ms 380 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 388 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 411 ms 26588 KB Output is correct
12 Correct 399 ms 26488 KB Output is correct
13 Correct 404 ms 26588 KB Output is correct
14 Correct 406 ms 26528 KB Output is correct
15 Correct 419 ms 26688 KB Output is correct
16 Correct 410 ms 25928 KB Output is correct
17 Correct 408 ms 25976 KB Output is correct
18 Correct 406 ms 25928 KB Output is correct
19 Correct 403 ms 26564 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 36648 KB Output is correct
2 Correct 178 ms 33508 KB Output is correct
3 Correct 185 ms 36868 KB Output is correct
4 Correct 309 ms 36692 KB Output is correct
5 Correct 308 ms 36564 KB Output is correct
6 Correct 303 ms 35924 KB Output is correct
7 Correct 301 ms 35796 KB Output is correct
8 Correct 307 ms 35792 KB Output is correct
9 Correct 304 ms 36280 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 388 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 411 ms 26588 KB Output is correct
12 Correct 399 ms 26488 KB Output is correct
13 Correct 404 ms 26588 KB Output is correct
14 Correct 406 ms 26528 KB Output is correct
15 Correct 419 ms 26688 KB Output is correct
16 Correct 410 ms 25928 KB Output is correct
17 Correct 408 ms 25976 KB Output is correct
18 Correct 406 ms 25928 KB Output is correct
19 Correct 403 ms 26564 KB Output is correct
20 Correct 308 ms 36648 KB Output is correct
21 Correct 178 ms 33508 KB Output is correct
22 Correct 185 ms 36868 KB Output is correct
23 Correct 309 ms 36692 KB Output is correct
24 Correct 308 ms 36564 KB Output is correct
25 Correct 303 ms 35924 KB Output is correct
26 Correct 301 ms 35796 KB Output is correct
27 Correct 307 ms 35792 KB Output is correct
28 Correct 304 ms 36280 KB Output is correct
29 Correct 1627 ms 118264 KB Output is correct
30 Correct 1263 ms 110292 KB Output is correct
31 Correct 1363 ms 118412 KB Output is correct
32 Correct 1636 ms 118312 KB Output is correct
33 Correct 1653 ms 118168 KB Output is correct
34 Correct 1623 ms 115844 KB Output is correct
35 Correct 1600 ms 115600 KB Output is correct
36 Correct 1600 ms 115492 KB Output is correct
37 Correct 1625 ms 116940 KB Output is correct
38 Correct 1259 ms 118340 KB Output is correct
39 Correct 1272 ms 118116 KB Output is correct
40 Correct 1248 ms 114768 KB Output is correct
41 Correct 1242 ms 114244 KB Output is correct
42 Correct 1252 ms 114368 KB Output is correct
43 Correct 1255 ms 116160 KB Output is correct
44 Correct 1321 ms 118208 KB Output is correct
45 Correct 1323 ms 118280 KB Output is correct
46 Correct 1299 ms 115104 KB Output is correct
47 Correct 1296 ms 114624 KB Output is correct
48 Correct 1296 ms 114752 KB Output is correct
49 Correct 1336 ms 116672 KB Output is correct
50 Correct 1420 ms 118336 KB Output is correct
51 Correct 1406 ms 118308 KB Output is correct
52 Correct 1386 ms 115772 KB Output is correct
53 Correct 1401 ms 115492 KB Output is correct
54 Correct 1383 ms 115352 KB Output is correct
55 Correct 1398 ms 117028 KB Output is correct