oj.uz

Submission #959777

# Submission time Handle Problem Language Result Execution time Memory
959777 2024-04-09T05:13:26 Z pcc Two Antennas (JOI19_antennas) C++17
22 / 100
 491 ms 59420 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 = 0,val = -1;
		}
	};
	node seg[mxn*4];
	SEG1(){}
	node pull(node a,node b){
		node re;
		re.mn = min(a.mn,b.mn);
		re.mx = 0;
		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 = 0;
		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 = 0;
			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 = 0,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 14 ms 32856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 32856 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 440 ms 59420 KB Output is correct
2 Correct 491 ms 58040 KB Output is correct
3 Correct 331 ms 46108 KB Output is correct
4 Correct 479 ms 58064 KB Output is correct
5 Correct 207 ms 47036 KB Output is correct
6 Correct 490 ms 57788 KB Output is correct
7 Correct 417 ms 45504 KB Output is correct
8 Correct 478 ms 58648 KB Output is correct
9 Correct 70 ms 37324 KB Output is correct
10 Correct 487 ms 59136 KB Output is correct
11 Correct 278 ms 46012 KB Output is correct
12 Correct 484 ms 58904 KB Output is correct
13 Correct 400 ms 58812 KB Output is correct
14 Correct 385 ms 58556 KB Output is correct
15 Correct 389 ms 58812 KB Output is correct
16 Correct 389 ms 59324 KB Output is correct
17 Correct 396 ms 58556 KB Output is correct
18 Correct 389 ms 58556 KB Output is correct
19 Correct 385 ms 58300 KB Output is correct
20 Correct 384 ms 58076 KB Output is correct
21 Correct 396 ms 57872 KB Output is correct
22 Correct 389 ms 58304 KB Output is correct
23 Correct 386 ms 59324 KB Output is correct
24 Correct 383 ms 57876 KB Output is correct

Subtask #4
0 / 65.0

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