Submission #1067629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067629		_rain_	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	500 ms	27592 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false

const int maxn = 5'00'000;
const int INF = (int)1e9+7;
struct CBL{
	int x , e;
	void read(){
		cin >> x >> e;
	}
	bool operator < (const CBL& other) const{
		return e > other.e;
	}
} p[maxn+2];
int st1[maxn*4+2] , st2[maxn*4+2];
int n;
vector<int> value;

void update_min(int id , int l , int r , int pos , int val){
	if (l>pos||r<pos) return;
	if (l==r) st1[id] = val;
	else {
		int m = l + r >> 1;
		update_min(id*2,l,m,pos,val);
		update_min(id*2+1,m+1,r,pos,val);
		st1[id] = min(st1[id*2],st1[id*2+1]);
	}
	return;
}
int getmn(int id , int l , int r , int u , int v){
	if (l > v || r < u) return INF;
	if (u <= l && r <= v) return st1[id];
	int m = l + r >> 1;
	return min(getmn(id*2,l,m,u,v),getmn(id*2+1,m+1,r,u,v));
}

void update_max(int id , int l , int r , int pos , int val){
	if (l > pos || r < pos) return;
	if (l==r) st2[id] = val;
	else {
		int m = l+r>>1;
		update_max(id*2,l,m,pos,val);
		update_max(id*2+1,m+1,r,pos,val);
		st2[id] = max(st2[id*2],st2[id*2+1]);
	}
	return;
}
int getmx(int id , int l , int r , int u , int v){
	if (l>v||r<u) return -INF;
	if (u <= l && r <= v) return st2[id];
	int m = l + r >> 1;
	return max(getmx(id*2,l,m,u,v),getmx(id*2+1,m+1,r,u,v));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i){
		p[i].read();
		value.push_back(p[i].x);
	}
	sort(value.begin(),value.end()); 
	value.resize(unique(value.begin(),value.end())-value.begin());	
	for (int i = 1; i <= n; ++i) p[i].x = upper_bound(value.begin(),value.end(),p[i].x)-value.begin();
	sort(p+1,p+n+1);
	memset(st1,0x3f,sizeof st1); // min
	int ans = 0;	
	for (int i = 1; i <= n; ++i){
		int xx = value[p[i].x - 1];
		int mx = getmx(1,1,maxn,1,p[i].x);
		int mn = getmn(1,1,maxn,p[i].x,maxn);
		int v1 = xx - p[i].e , v2 = xx + p[i].e;
		if (debug){
			cout << "( DEBUG )\n";
			cout << p[i].x << ' ' << p[i].e << '\n';
			cout << mx << ' ' << mn << ' ' << v1 << ' ' << v2 << '\n';
		}
		if (v1 < mn && v2 > mx){
			++ans;
			update_max(1,1,maxn,p[i].x,v2);
			update_min(1,1,maxn,p[i].x,v1);
		}
	}
	cout << ans;	
}

Compilation message (stderr)

Main.cpp: In function 'void update_min(int, int, int, int, int)':
Main.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In function 'int getmn(int, int, int, int, int)':
Main.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int m = l + r >> 1;
      |          ~~^~~
Main.cpp: In function 'void update_max(int, int, int, int, int)':
Main.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int m = l+r>>1;
      |           ~^~
Main.cpp: In function 'int getmx(int, int, int, int, int)':
Main.cpp:53:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31