oj.uz

Submission #885154

# Submission time Handle Problem Language Result Execution time Memory
885154 2023-12-09T04:51:21 Z vjudge1 Triple Jump (JOI19_jumps) C++17
46 / 100
 737 ms 55580 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 << 1];
int lazy[MAX << 1];

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 6492 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 6492 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 272 ms 22084 KB Output is correct
12 Correct 267 ms 21840 KB Output is correct
13 Correct 281 ms 21712 KB Output is correct
14 Correct 269 ms 21844 KB Output is correct
15 Correct 275 ms 22100 KB Output is correct
16 Correct 276 ms 21332 KB Output is correct
17 Correct 298 ms 21192 KB Output is correct
18 Correct 275 ms 21332 KB Output is correct
19 Correct 272 ms 21720 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 18868 KB Output is correct
2 Correct 61 ms 22100 KB Output is correct
3 Correct 65 ms 20644 KB Output is correct
4 Correct 116 ms 20560 KB Output is correct
5 Correct 116 ms 20540 KB Output is correct
6 Correct 114 ms 19796 KB Output is correct
7 Correct 112 ms 19800 KB Output is correct
8 Correct 112 ms 19792 KB Output is correct
9 Correct 114 ms 20140 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 272 ms 22084 KB Output is correct
12 Correct 267 ms 21840 KB Output is correct
13 Correct 281 ms 21712 KB Output is correct
14 Correct 269 ms 21844 KB Output is correct
15 Correct 275 ms 22100 KB Output is correct
16 Correct 276 ms 21332 KB Output is correct
17 Correct 298 ms 21192 KB Output is correct
18 Correct 275 ms 21332 KB Output is correct
19 Correct 272 ms 21720 KB Output is correct
20 Correct 116 ms 18868 KB Output is correct
21 Correct 61 ms 22100 KB Output is correct
22 Correct 65 ms 20644 KB Output is correct
23 Correct 116 ms 20560 KB Output is correct
24 Correct 116 ms 20540 KB Output is correct
25 Correct 114 ms 19796 KB Output is correct
26 Correct 112 ms 19800 KB Output is correct
27 Correct 112 ms 19792 KB Output is correct
28 Correct 114 ms 20140 KB Output is correct
29 Incorrect 737 ms 55580 KB Output isn't correct
30 Halted 0 ms 0 KB -