oj.uz

Submission #231615

# Submission time Handle Problem Language Result Execution time Memory
231615 2020-05-14T07:43:48 Z oolimry Two Antennas (JOI19_antennas) C++14
22 / 100
 319 ms 26540 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf = 1e9;

int n, Q;

///SEGMENT TREE BEGIN
static int lazy[400005]; ///smallest height of the right antenna

static int tree[400005]; ///Max Hi if active, else -INF.
static int histMax[400005]; ///histMax = max(tree[i] - lazy[i]);

inline void reset(){
	fill(tree,tree+2*n,-inf);
	fill(lazy,lazy+2*n,inf);
	fill(histMax,histMax+2*n,-inf);
}

inline void relax(int i){
	if(i < n) histMax[i] = max(histMax[i<<1], histMax[i<<1|1]);
	histMax[i] = max(tree[i] - lazy[i], histMax[i]);
}

void prop(int i){
	if(i != 1) prop(i >> 1);
	lazy[i<<1] = min(lazy[i<<1], lazy[i]);
	relax(i<<1);
	lazy[i<<1|1] = min(lazy[i<<1|1], lazy[i]);
	relax(i<<1|1);
	lazy[i] = inf;
}

inline void ptupdate(int i, int v){
	//cout << "Pt: " << i << " " << v << "\n";
	i += n; 
	prop(i >> 1); lazy[i] = inf;
	tree[i] = v; relax(i);
	for(i >>= 1;i > 0;i >>= 1) tree[i] = max(tree[i<<1], tree[i<<1|1]), relax(i);
}

inline void update(int L, int R, int v){
	//cout << "Lazy: " << L << " " << R-1 << " " << v << "\n";
	for(int l = L + n, r = R + n;l < r;l >>= 1,r >>= 1){
		if(l&1){
			lazy[l] = min(lazy[l], v);
			relax(l);
			l++;
		}
		if(r&1){
			r--;
			lazy[r] = min(lazy[r], v);
			relax(r);
		}
	}
	
	for(L += n;L > 0;L >>= 1) relax(L);
	for(R += n-1;R > 0;R >>= 1) relax(R);
}

inline int query(int l, int r){	
	int ans = -inf;
	prop((l+n) >> 1);
	prop((r-1+n) >> 1);
	
	for(l += n,r += n;l < r;l >>= 1,r >>= 1){
		if(l&1){
			//if(l == 5 && r == 8) cout << histMax[l] << "FUNNYTHING\n";
			ans = max(ans,histMax[l]);
			l++;
		}
		if(r&1){
			r--;
			ans = max(ans,histMax[r]);
		}
	}
	return ans;
}
///SEGMENT TREE END

int H[200005];
int A[200005];
int B[200005];
int ans[200005];
ii QQ[200005];
vector<ii> queries[200005];
vector<ii> events[200005];

void solve(){
	for(int i = 0;i < n;i++) events[i].clear();
	for(int i = 0;i < Q;i++) queries[i].clear();
	reset();
	
	for(int i = 0;i < n;i++){
		int start = i + A[i], end = i + B[i] + 1;
		if(start < n) events[start].push_back(ii(i, 1)); ///1 is start
		if(end < n) events[end].push_back(ii(i, -1)); ///-1 is end
	}
	
	for(int i = 0;i < Q;i++){
		queries[QQ[i].second].push_back(ii(QQ[i].first, i));
	}
	
	for(int r = 0;r < n;r++){
		//cout << r << ":\n";
		for(ii e : events[r]){
			if(e.second == 1) ptupdate(e.first, H[e.first]);
			else ptupdate(e.first, -inf);
		}
		
		if(r - A[r] >= 0){
			int R = r - A[r];
			int L = max(0, r - B[r]);
			update(L, R+1, H[r]);
		}
		
		for(ii q : queries[r]){
			int res = query(q.first, r+1);
			//cout << q.first << " " << r << " " << res << "\n";
			ans[q.second] = max(ans[q.second],res);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 0;i < n;i++) cin >> H[i] >> A[i] >> B[i];
	
	cin >> Q;
	fill(ans,ans+Q, -inf);
	
	for(int i = 0;i < Q;i++){
		int l, r; cin >> l >> r; l--; r--;
		QQ[i] = ii(l,r);
	}
	
	solve();
	
	reverse(H,H+n);
	reverse(A,A+n);
	reverse(B,B+n);
	for(int i = 0;i < Q;i++){
		QQ[i].first = n - 1 - QQ[i].first;
		QQ[i].second = n - 1 - QQ[i].second;
		swap(QQ[i].first,QQ[i].second);
	}
	
	solve();
	
	for(int i = 0;i < Q;i++) cout << max(-1,ans[i]) << "\n";
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 24312 KB Output is correct
2 Correct 319 ms 25976 KB Output is correct
3 Correct 198 ms 21112 KB Output is correct
4 Correct 298 ms 25976 KB Output is correct
5 Correct 118 ms 17144 KB Output is correct
6 Correct 298 ms 25948 KB Output is correct
7 Correct 273 ms 23928 KB Output is correct
8 Correct 309 ms 25976 KB Output is correct
9 Correct 43 ms 12288 KB Output is correct
10 Correct 308 ms 25848 KB Output is correct
11 Correct 174 ms 19960 KB Output is correct
12 Correct 295 ms 25976 KB Output is correct
13 Correct 247 ms 26092 KB Output is correct
14 Correct 229 ms 25780 KB Output is correct
15 Correct 221 ms 24980 KB Output is correct
16 Correct 214 ms 25020 KB Output is correct
17 Correct 253 ms 26540 KB Output is correct
18 Correct 227 ms 25412 KB Output is correct
19 Correct 232 ms 25708 KB Output is correct
20 Correct 228 ms 25708 KB Output is correct
21 Correct 236 ms 25708 KB Output is correct
22 Correct 235 ms 25712 KB Output is correct
23 Correct 232 ms 25804 KB Output is correct
24 Correct 221 ms 24304 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -