oj.uz

Submission #885146

# Submission time Handle Problem Language Result Execution time Memory
885146 2023-12-09T04:30:23 Z vjudge1 Triple Jump (JOI19_jumps) C++17
5 / 100
 13 ms 2652 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 ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 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];
int lazy[MAX];

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){
	
	//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]);
				
				//cout << get(5,5) << '\n';
				if(a[u] >= a[ri])break;
				stt.pop();
			}
			 
			stt.push(ri--);
			// cout << l << " " << ri << '\n';
			// break;
		}
		
		// cout << l << " " << ri << '\n';
		// break;
		
		//cout << get(l,r) << '\n';
		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(int, int, int)':
jumps.cpp:44:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'int get(int, int, int, int, int)':
jumps.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int m = l + r >> 1;
      |          ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:100:7: warning: unused variable 'id' [-Wunused-variable]
  100 |   int id = qry[i].id;
      |       ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2548 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2548 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 13 ms 2652 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2548 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 13 ms 2652 KB Output isn't correct
12 Halted 0 ms 0 KB -