oj.uz

Submission #291139

# Submission time Handle Problem Language Result Execution time Memory
291139 2020-09-04T18:28:35 Z Plurm Triple Jump (JOI19_jumps) C++11
0 / 100
 54 ms 11160 KB 
#include <bits/stdc++.h>
using namespace std;
int a[500005];
int seg[1048576];
int argseg[1048576];
int lb[1048576];
int rb[1048576];
void build(int c, int l, int r){
	lb[c] = l;
	rb[c] = r;
	if(l == r){
		seg[c] = a[l];
		argseg[c] = l;
		return;
	}
	int k = (l+r)/2;
	build(2*c, l, k);
	build(2*c+1, k+1, r);
	if(seg[2*c] > seg[2*c+1]){
		argseg[c] = argseg[2*c];
		seg[c] = seg[2*c];
	}else{
		argseg[c] = argseg[2*c+1];
		seg[c] = seg[2*c+1];
	}
}
void update(int c, int i, int x){
	if(lb[c] == rb[c]){
		seg[c] = x;
		a[i] = x;
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(i <= k) update(2*c, i, x);
	else update(2*c+1, i, x);
	if(seg[2*c] > seg[2*c+1]){
		argseg[c] = argseg[2*c];
		seg[c] = seg[2*c];
	}else{
		argseg[c] = argseg[2*c+1];
		seg[c] = seg[2*c+1];
	}
}
int query(int c, int l, int r){
	if(l > r) return 0;
	if(lb[c] == l && rb[c] == r) return argseg[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		int q1 = query(2*c, l, k);
		int q2 = query(2*c+1, k+1, r);
		if(a[q1] > a[q2]) return q1;
		else return q2;
	}
	else if(r <= k) return query(2*c, l, r);
	else return query(2*c+1, l, r);
}
int check(int x, int y, int l, int r){
	int i1 = query(1, max(l, 2*y-x), r);
	int i2 = query(1, max(l, x+1), min((x+y)/2, r));
	int i3 = query(1, max(l, 2*x-y), min(x-1, r));
	int v1 = a[i1];
	int v2 = a[i2];
	int v3 = a[i3];
	return max({v1, v2, v3}) + a[x] + a[y];
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d", a+i);
	}
	build(1,1,n);
	int q;
	scanf("%d",&q);
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int i1 = query(1, l, r);
		int v1 = a[i1];
		update(1, i1, 0);
		int i2 = query(1, l, r);
		int v2 = a[i2];
		update(1, i2, 0);
		int i3 = query(1, l, r);
		int v3 = a[i3];
		update(1, i3, 0);
		update(1, i1, v1);
		update(1, i2, v2);
		update(1, i3, v3);
		if(i1 > i2) swap(i1, i2);
		if(i2 > i3) swap(i2, i3);
		if(i1 > i2) swap(i1, i2);
		if(i2-i1 <= i3-i2){
			printf("%d\n",v1+v2+v3);
		}else{
			int v4 = check(i1, i2, l, r);
			int v5 = check(i2, i3, l, r);
			int v6 = check(i1, i3, l, r);
			printf("%d\n", max({v4, v5, v6}));
		}
	}
	return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
jumps.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
jumps.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
jumps.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11128 KB Output is correct
2 Correct 54 ms 11004 KB Output is correct
3 Correct 37 ms 11128 KB Output is correct
4 Incorrect 42 ms 11160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -