oj.uz

Submission #170772

# Submission time Handle Problem Language Result Execution time Memory
170772 2019-12-26T10:23:32 Z moonrabbit2 Two Antennas (JOI19_antennas) C++17
22 / 100
 518 ms 28612 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=2e5+5,INF=1e9+5;
int n,q,h[N],a[N],b[N],qs[N],qe[N],ans[N];
struct node{
	int lazy,mxd,mnh;
	node(){
		lazy=-INF; mxd=-INF; mnh=INF;
	}
};
int ANS=806460109;
struct seg{
	node tree[4*N];
	void pushdown(int nd,int l,int r){
		tree[nd].mxd=max(tree[nd].mxd,tree[nd].lazy-tree[nd].mnh);
		if(l!=r){
			tree[nd<<1].lazy=max(tree[nd<<1].lazy,tree[nd].lazy);
			tree[nd<<1|1].lazy=max(tree[nd<<1|1].lazy,tree[nd].lazy);
		}
		tree[nd].lazy=-INF;
	}
	void upd1(int nd,int l,int r,int s,int e,int v){
		pushdown(nd,l,r);
		if(r<s||e<l) return;
		if(s<=l&&r<=e){
			tree[nd].lazy=v;
			pushdown(nd,l,r);
			return;
		}
		int m=(l+r)>>1;
		upd1(nd<<1,l,m,s,e,v); upd1(nd<<1|1,m+1,r,s,e,v);
		tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
	}
	void upd2(int nd,int l,int r,int x,int v){
		pushdown(nd,l,r);
		if(r<x||x<l) return;
		if(l==r){
			tree[nd].mnh=v;
			return;
		}
		int m=(l+r)>>1;
		upd2(nd<<1,l,m,x,v); upd2(nd<<1|1,m+1,r,x,v);
		tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
	}
	int qry(int nd,int l,int r,int s,int e){
		pushdown(nd,l,r);
		if(r<s||e<l) return -INF;
		if(s<=l&&r<=e) return tree[nd].mxd;
		int m=(l+r)>>1;
		return max(qry(nd<<1,l,m,s,e),qry(nd<<1|1,m+1,r,s,e));
	}
};
void solve(){
	vector<pii> events;
	vector<int> queries[N];
	seg tree;
	for(int i=1;i<=n;i++){
		events.emplace_back(i+a[i],i);
		events.emplace_back(i+b[i]+1,-i);
	}
	for(int i=1;i<=q;i++){
		queries[qe[i]].emplace_back(i);
	}
	sort(events.begin(),events.end());
	for(int i=1,j=0;i<=n;i++){
		while(j<events.size()&&events[j].fi==i){
			int p=events[j].se; j++;
			if(p>0) tree.upd2(1,1,n,p,h[p]);
			else tree.upd2(1,1,n,-p,INF);
		}
		tree.upd1(1,1,n,max(1,i-b[i]),max(1,i-a[i]),h[i]);
		for(auto &it : queries[i]) ans[it]=max(ans[it],tree.qry(1,1,n,qs[it],qe[it]));
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i]>>a[i]>>b[i];
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>qs[i]>>qe[i];
		ans[i]=-1;
	}
	solve();
	for(int i=1;i<=q;i++){
		qs[i]=n+1-qs[i];
		qe[i]=n+1-qe[i];
		swap(qs[i],qe[i]);
	}
	reverse(h+1,h+1+n); reverse(a+1,a+1+n); reverse(b+1,b+1+n);
	solve();
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message

antennas.cpp: In function 'void solve()':
antennas.cpp:76:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<events.size()&&events[j].fi==i){
         ~^~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 14468 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 459 ms 27572 KB Output is correct
2 Correct 511 ms 28604 KB Output is correct
3 Correct 347 ms 25592 KB Output is correct
4 Correct 515 ms 28604 KB Output is correct
5 Correct 223 ms 21012 KB Output is correct
6 Correct 514 ms 28612 KB Output is correct
7 Correct 442 ms 27228 KB Output is correct
8 Correct 507 ms 28552 KB Output is correct
9 Correct 80 ms 16428 KB Output is correct
10 Correct 518 ms 28596 KB Output is correct
11 Correct 304 ms 22732 KB Output is correct
12 Correct 514 ms 28540 KB Output is correct
13 Correct 406 ms 28516 KB Output is correct
14 Correct 385 ms 28484 KB Output is correct
15 Correct 392 ms 28408 KB Output is correct
16 Correct 376 ms 28432 KB Output is correct
17 Correct 406 ms 28432 KB Output is correct
18 Correct 395 ms 28520 KB Output is correct
19 Correct 408 ms 28432 KB Output is correct
20 Correct 398 ms 28436 KB Output is correct
21 Correct 362 ms 28400 KB Output is correct
22 Correct 385 ms 28500 KB Output is correct
23 Correct 395 ms 28444 KB Output is correct
24 Correct 372 ms 28460 KB Output is correct

Subtask #4
0 / 65.0

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