oj.uz

Submission #885155

# Submission time Handle Problem Language Result Execution time Memory
885155 2023-12-09T04:51:55 Z vjudge1 Triple Jump (JOI19_jumps) C++17
100 / 100
 757 ms 64356 KB 
#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)5e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,a[MAX];
int q;
struct node{
	int l,r,id;	
}qry[MAX];

ii st[MAX << 2];
int lazy[MAX << 2];

ii operator + (const ii &a,const ii &b){
	return {max(a.X,b.X),max(a.Y,b.Y)};
}

void lazyupdate(int id,int l,int r){
	if(lazy[id] == 0)return;
	st[id].X = max(st[id].X,st[id].Y + lazy[id]);
	if(l != r){
		lazy[id << 1] = max(lazy[id << 1],lazy[id]);
		lazy[id << 1 | 1] = max(lazy[id << 1 | 1],lazy[id]);
	}
	lazy[id] = 0;
}

void build(int id = 1,int l = 1,int r = n){
	if(l == r){
		st[id] = {a[l],a[l]};
		return;
	}
	int m = l + r >> 1;
	build(id << 1,l,m);
	build(id << 1 | 1,m + 1,r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}

void update(int u,int v,int val,int id = 1,int l = 1,int r = n){
	
	if(u > v)return;
	//cout << u << " " << v << " " << val << "\n";
	lazyupdate(id,l,r);
	if(u > r || v < l)return;
	if(u <= l && r <= v){
		lazy[id] = val;
		
		lazyupdate(id,l,r);
		
		return;
	}
	int m = l + r >> 1;
	update(u,v,val,id << 1,l,m);
	update(u,v,val,id << 1 | 1,m + 1,r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
int get(int u,int v,int id = 1,int l = 1,int r = n){
	lazyupdate(id,l,r);
	if(u > r || v < l)return 0;
	if(u <= l && r <= v)return st[id].X;
	int m = l + r >> 1;
	return max(get(u,v,id << 1,l,m),get(u,v,id << 1 | 1,m + 1,r));
}
signed main(){
	
	read();
	
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> a[i];
	
	build();
	cin >> q;
	
	for(int i = 1,l,r;i <= q;i++){
		cin >> l >> r;
		qry[i] = {l,r,i};
	}
	
	sort(qry + 1,qry + 1 + q,[&](const node &a,const node &b){
		return a.l > b.l;
	});
	
	//cout << "hi\n";
	stack<int> stt;
	int ri = n;
	
	for(int i = 1;i <= q;i++){
		int &l = qry[i].l;
		int r = qry[i].r;
		int id = qry[i].id;
		
		//cout << l << " " << r << " " << id << "\n";
		while(ri >= l){
			//cout << ri << "\n";
			while(!stt.empty()){
				int u = stt.top();
				//cout << u << " " << ri << ' ' << (u + u - ri) << " " << n << " " << a[u] + a[ri] << "\n";
				update(u + (u - ri),n,a[u] + a[ri]);
				if(a[u] >= a[ri])break;
				stt.pop();
			}
			 
			stt.push(ri--);
		}
		l = get(l,r);
	}
	
	sort(qry + 1,qry + 1 + q,[&](const node &a,const node &b){
		return a.id < b.id;
	});
	
	for(int i = 1;i <= q;i++){
		cout << qry[i].l << "\n";
	}
}

Compilation message

jumps.cpp: In function 'void build(long long int, long long int, long long int)':
jumps.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:102:7: warning: unused variable 'id' [-Wunused-variable]
  102 |   int id = qry[i].id;
      |       ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 280 ms 22264 KB Output is correct
12 Correct 271 ms 21860 KB Output is correct
13 Correct 272 ms 22100 KB Output is correct
14 Correct 270 ms 21840 KB Output is correct
15 Correct 275 ms 22100 KB Output is correct
16 Correct 274 ms 21216 KB Output is correct
17 Correct 275 ms 21332 KB Output is correct
18 Correct 275 ms 21328 KB Output is correct
19 Correct 270 ms 21852 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 20944 KB Output is correct
2 Correct 59 ms 22608 KB Output is correct
3 Correct 58 ms 20712 KB Output is correct
4 Correct 123 ms 20716 KB Output is correct
5 Correct 119 ms 20824 KB Output is correct
6 Correct 113 ms 20764 KB Output is correct
7 Correct 112 ms 20940 KB Output is correct
8 Correct 118 ms 21124 KB Output is correct
9 Correct 114 ms 20820 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 280 ms 22264 KB Output is correct
12 Correct 271 ms 21860 KB Output is correct
13 Correct 272 ms 22100 KB Output is correct
14 Correct 270 ms 21840 KB Output is correct
15 Correct 275 ms 22100 KB Output is correct
16 Correct 274 ms 21216 KB Output is correct
17 Correct 275 ms 21332 KB Output is correct
18 Correct 275 ms 21328 KB Output is correct
19 Correct 270 ms 21852 KB Output is correct
20 Correct 115 ms 20944 KB Output is correct
21 Correct 59 ms 22608 KB Output is correct
22 Correct 58 ms 20712 KB Output is correct
23 Correct 123 ms 20716 KB Output is correct
24 Correct 119 ms 20824 KB Output is correct
25 Correct 113 ms 20764 KB Output is correct
26 Correct 112 ms 20940 KB Output is correct
27 Correct 118 ms 21124 KB Output is correct
28 Correct 114 ms 20820 KB Output is correct
29 Correct 741 ms 49340 KB Output is correct
30 Correct 628 ms 64356 KB Output is correct
31 Correct 579 ms 60248 KB Output is correct
32 Correct 720 ms 60240 KB Output is correct
33 Correct 757 ms 60256 KB Output is correct
34 Correct 715 ms 58116 KB Output is correct
35 Correct 737 ms 57684 KB Output is correct
36 Correct 715 ms 57844 KB Output is correct
37 Correct 738 ms 59240 KB Output is correct
38 Correct 594 ms 60216 KB Output is correct
39 Correct 592 ms 60240 KB Output is correct
40 Correct 590 ms 56956 KB Output is correct
41 Correct 595 ms 56564 KB Output is correct
42 Correct 595 ms 56432 KB Output is correct
43 Correct 596 ms 58248 KB Output is correct
44 Correct 613 ms 60268 KB Output is correct
45 Correct 608 ms 60496 KB Output is correct
46 Correct 598 ms 57168 KB Output is correct
47 Correct 589 ms 56660 KB Output is correct
48 Correct 589 ms 56656 KB Output is correct
49 Correct 607 ms 59048 KB Output is correct
50 Correct 644 ms 60280 KB Output is correct
51 Correct 644 ms 60404 KB Output is correct
52 Correct 644 ms 57940 KB Output is correct
53 Correct 630 ms 57688 KB Output is correct
54 Correct 636 ms 57684 KB Output is correct
55 Correct 642 ms 59208 KB Output is correct