oj.uz

Submission #959779

# Submission time Handle Problem Language Result Execution time Memory
959779 2024-04-09T05:14:41 Z pcc Two Antennas (JOI19_antennas) C++17
22 / 100
 509 ms 59324 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll

const int mxn = 2e5+10;
const ll inf = 2e9+10;

#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
	struct node{
		int mn,mx,val;
		node(){
			mn = inf,mx = -inf,val = -1;
		}
	};
	node seg[mxn*4];
	SEG1(){}
	node pull(node a,node b){
		node re;
		re.mn = min(a.mn,b.mn);
		re.mx = -inf;
		re.val = max(a.val,b.val);
		return re;
	}
	void push(int now,int l,int r){
		seg[ls].mx = max(seg[ls].mx,seg[now].mx);
		seg[rs].mx = max(seg[rs].mx,seg[now].mx);
		seg[ls].val = max(seg[ls].val,seg[ls].mx-seg[ls].mn);
		seg[rs].val = max(seg[rs].val,seg[rs].mx-seg[rs].mn);
		seg[now].mx = -inf;
		return;
	}
	void chmax(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].mx = max(seg[now].mx,v);
			seg[now].val = max(seg[now].val,seg[now].mx-seg[now].mn);
			return;
		}
		push(now,l,r);
		if(mid>=s)chmax(ls,l,mid,s,e,v);
		if(mid<e)chmax(rs,mid+1,r,s,e,v);
		seg[now].mn = min(seg[ls].mn,seg[rs].mn);
		seg[now].val = max(seg[ls].val,seg[rs].val);
		return;
	}
	void chmin(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now].mn = v;seg[now].mx = -inf;
			seg[now].val = seg[now].mx-seg[now].mn;
			return;
		}
		push(now,l,r);
		if(mid>=p)chmin(ls,l,mid,p,v);
		else chmin(rs,mid+1,r,p,v);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	node getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		push(now,l,r);
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
	void init(){
		for(auto &i:seg)i.mn = inf,i.mx = -inf,i.val = -1;
		return;
	}
};

struct SEG2{
	int seg[mxn*4];
	SEG2(){
		for(auto &i:seg)i = -1;
	}
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = max(seg[ls],seg[rs]);
		return;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
	void init(){
		for(auto &i:seg)i = -1;
		return;
	}
};

#undef ls
#undef rs
#undef mid

struct D{
	int tp,id,pos;
	D(){}
	D(int tt,int ii,int pp):tp(tt),id(ii),pos(pp){}
	bool operator<(D b)const{
		return pos == b.pos?tp<b.tp:pos<b.pos;
	}
};


SEG1 seg1;
SEG2 seg2;
pii req[mxn];
pii range[mxn];
int H[mxn];
int N,Q;
vector<D> op;
int ans[mxn];

void solve(){
	op.clear();
	seg1.init();
	seg2.init();
	for(int i = 1;i<=N;i++){
		int pl = i+range[i].fs,pr = i+range[i].sc+1;
		pl = min(pl,N),pr = min(pr,N+1);
		op.push_back(D(1,i,pr));
		op.push_back(D(2,i,pl));
		op.push_back(D(3,i,i));
	}
	for(int i = 1;i<=Q;i++){
		op.push_back(D(4,i,req[i].sc));
	}
	sort(op.begin(),op.end());
	for(auto &[tp,id,___]:op){
		//cout<<tp<<':'<<id<<' '<<___<<"::"<<seg1.seg[0].val<<endl;
		if(tp == 1){
			seg2.modify(0,0,N,id,seg1.getval(0,0,N,id,id).val);
			seg1.chmin(0,0,N,id,inf);
		}
		else if(tp == 2){
			seg1.chmin(0,0,N,id,H[id]);
		}
		else if(tp == 3){
			int pl = id-range[id].sc,pr = id-range[id].fs;
			pl = max(pl,0ll),pr = max(pr,0ll);
			seg1.chmax(0,0,N,pl,pr,H[id]);
		}
		else{
			ans[id] = max({ans[id],seg1.getval(0,0,N,req[id].fs,req[id].sc).val,seg2.getval(0,0,N,req[id].fs,req[id].sc)});
		}
	}
	//cout<<endl;
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++){
		cin>>H[i]>>range[i].fs>>range[i].sc;
	}
	cin>>Q;
	for(int i = 1;i<=Q;i++){
		cin>>req[i].fs>>req[i].sc;
	}
	memset(ans,-1,sizeof(ans));
	solve();
	reverse(H+1,H+N+1);
	reverse(range+1,range+N+1);
	for(int i = 1;i<=Q;i++){
		req[i].fs = N+1-req[i].fs,req[i].sc = N+1-req[i].sc;
		swap(req[i].fs,req[i].sc);
	}
	solve();
	for(int i = 1;i<=Q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message

antennas.cpp:169:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  169 | main(){
      | ^~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 32868 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 32868 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 447 ms 57788 KB Output is correct
2 Correct 474 ms 59320 KB Output is correct
3 Correct 344 ms 46780 KB Output is correct
4 Correct 505 ms 57532 KB Output is correct
5 Correct 210 ms 45500 KB Output is correct
6 Correct 473 ms 58128 KB Output is correct
7 Correct 412 ms 45768 KB Output is correct
8 Correct 509 ms 58044 KB Output is correct
9 Correct 70 ms 37328 KB Output is correct
10 Correct 482 ms 59324 KB Output is correct
11 Correct 290 ms 45500 KB Output is correct
12 Correct 497 ms 57532 KB Output is correct
13 Correct 389 ms 58888 KB Output is correct
14 Correct 401 ms 59324 KB Output is correct
15 Correct 387 ms 58556 KB Output is correct
16 Correct 383 ms 58552 KB Output is correct
17 Correct 387 ms 59152 KB Output is correct
18 Correct 393 ms 58044 KB Output is correct
19 Correct 380 ms 59308 KB Output is correct
20 Correct 383 ms 57788 KB Output is correct
21 Correct 384 ms 58808 KB Output is correct
22 Correct 385 ms 58300 KB Output is correct
23 Correct 387 ms 58044 KB Output is correct
24 Correct 380 ms 59068 KB Output is correct

Subtask #4
0 / 65.0

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