Submission #1308517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308517		thuhienne	Two Antennas (JOI19_antennas)	C++20	100 / 100	603 ms	31804 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

const int maxn = 200009;
const int cut = 1e9 + 1;

int n,q;
int h[maxn],a[maxn],b[maxn];

vector <pair <int,int>> ask[maxn];
vector <int> event[maxn];
int answer[maxn];

//segment tree
//{min,max}
pair <int,int> st[maxn * 4],lazy[maxn * 4];
int res[maxn * 4];

void init(int id,int l,int r) {
	res[id] = -1;
	st[id] = lazy[id] = {cut,-cut};
	
	if (l == r) return;
	
	int mid = (l + r) >> 1;
	
	init(id*2,l,mid);
	init(id*2+1,mid+1,r);
}

pair <int,int> merge(pair <int,int> a,pair <int,int> b) {
	return {min(a.first,b.first),max(a.second,b.second)};
}

void changeres(int id,pair <int,int> dk) {
	lazy[id] = merge(lazy[id],dk);
	if (st[id].first == cut) return;
	
	int h = dk.first;
	res[id] = max({res[id],abs(h - st[id].first),abs(h - st[id].second)});
	h = dk.second;
	res[id] = max({res[id],abs(h - st[id].first),abs(h - st[id].second)});
	
}

void push_down(int id) {
	if (abs(lazy[id].first) == cut) return;
	
	changeres(id*2,lazy[id]);
	changeres(id*2+1,lazy[id]);
	
	lazy[id] = {cut,-cut};
}

void modify(int id,int l,int r,int pos,int bitch) {
	if (l > pos || r < pos) return;
	if (l == r) {
		if (bitch == 1) st[id] = {h[l],h[l]};
		else st[id] = {cut,-cut};
		
		return;
	}
	
	int mid = (l + r) >> 1;
	push_down(id);
	
	modify(id*2,l,mid,pos,bitch);
	modify(id*2+1,mid+1,r,pos,bitch);
	
	st[id] = merge(st[id*2],st[id*2+1]);
	res[id] = max(res[id*2],res[id*2+1]);
}

void update(int id,int l,int r,int u,int v,int h) {
	if (l > v || r < u) return;
	if (l >= u && r <= v) {
		changeres(id,{h,h});
//		cout << res[id] << " " << l << " " << r << '\n';
		return;
	}
	
	int mid = (l + r) >> 1;
	push_down(id);
	
	update(id*2,l,mid,u,v,h);
	update(id*2+1,mid+1,r,u,v,h);
	
	res[id] = max(res[id*2],res[id*2+1]);
}

int get(int id,int l,int r,int u,int v) {
	if (l > v || r < u) return -1;
	if (l >= u && r <= v) return res[id];
	
	int mid = (l + r) >> 1;
	push_down(id);
	
	return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

int main() {
//  ios_base::sync_with_stdio(0);
//  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}
	
	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> h[i] >> a[i] >> b[i];
		
		if (i + a[i] <= n) event[i + a[i]].push_back(i);
		if (i + b[i] + 1 <= n) event[i + b[i] + 1].push_back(-i);
		
	}
	
	cin >> q;
	for (int i = 1;i <= q;i++) {
		int u,v;cin >> u >> v;
		ask[v].push_back({u,i});
	}
	
	init(1,1,n);
	
	for (int i = 1;i <= n;i++) {
//		cout << "TIMES: " << i << '\n';
		for (int a : event[i]) {
			
			modify(1,1,n,abs(a),(a > 0 ? 1 : -1));
			
		}
		
		if (i - a[i] >= 1) update(1,1,n,max(1,i - b[i]),i - a[i],h[i]);
		
		for (pair <int,int> query : ask[i]) {
			answer[query.second] = get(1,1,n,query.first,i);
		}
		
	}
	
	for (int i = 1;i <= q;i++) cout << answer[i] << "\n";

}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:110:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:111:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65