Submission #1214794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214794		nguyn	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	635 ms	49464 KiB

Main

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 5e5 + 5;
const int inf = 2e9 + 246;

struct SegTree {
	vector<pii> st;
	int n;

	SegTree() {}
	SegTree(int n) : n(n) {
		st.assign(4 * n + 5, {inf, inf}); 
	}

	void update(int id, int l, int r, int i, int x) {
		if (l == r) {
			st[id] = {x, i}; 
			return;
		}
		int mid = (l + r) / 2;
		if (i <= mid) update(id * 2, l, mid, i, x);
		else update(id * 2 + 1, mid + 1, r, i, x); 
		st[id] = min(st[id * 2], st[id * 2 + 1]); 
	}

	pii get(int id, int l, int r, int u, int v) {
		if (v < l || r < u) {
			return {inf, inf}; 
		}
		if (u <= l && r <= v) {
			return st[id]; 
		}
		int mid = (l + r) / 2;
		return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); 
	}
} st_lower, st_higher; 

int n;
pii a[N];
int x[N];
int del[N];
int pos[N];
pii b[N];
int t;

bool cmp(pii x, pii y) {
	return x.S < y.S; 
}


signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> t;
    for (int i = 1; i <= t; i++) {
    	cin >> b[i].F >> b[i].S;
    }
    sort(b + 1, b + 1 + t); 
    int n = 0;
    for (int i = 1; i <= t; i++) {
    	if (i == t || b[i].F != b[i + 1].F) a[++n] = b[i]; 
    }
    // cout << n << '\n';
    // for (int i = 1; i <= n; i++) {
    // 	cout << a[i].F << ' ' << a[i].S << '\n'; 
    // }
    vector<pii> compressed;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i].F >> a[i].S;
    	compressed.pb({a[i].F, a[i].S}); 
    }
    sort(compressed.begin(), compressed.end());  
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
    	x[i] = upper_bound(compressed.begin(), compressed.end(), a[i]) - compressed.begin(); 
    }
    for (int i = 1; i <= n; i++) {
    	pos[x[i]] = i;
    }	
    st_lower = SegTree(n);
    st_higher = SegTree(n); 
    for (int i = 1; i <= n; i++) {
    	st_lower.update(1, 1, n, x[i], a[i].S - a[i].F); 
    	st_higher.update(1, 1, n, x[i], a[i].F + a[i].S); 
    }
    int res = 0; 
    for (int i = n; i >= 1; i--) {
    	if (del[i]) continue;
    	res++;
    	del[i] = 1; 
    	st_lower.update(1, 1, n, x[i], inf);
    	st_higher.update(1, 1, n, x[i], inf); 
    	while(1) {
    		pii tmp = st_lower.get(1, 1, n, 1, x[i]); 
    		// cout << i << ' ' << tmp.F << ' ' << tmp.S << endl;
    		if (tmp.F > a[i].S - a[i].F) break;
    		del[pos[tmp.S]] = 1; 
    		st_lower.update(1, 1, n, tmp.S, inf);
    		st_higher.update(1, 1, n, tmp.S, inf); 
    	}
    	while(1) {
    		pii tmp = st_higher.get(1, 1, n, x[i], n); 
    		// cout << i << ' ' << tmp.F << ' ' << tmp.S << endl;
    		if (tmp.F > a[i].F + a[i].S) break;
    		del[pos[tmp.S]] = 1; 
    		st_lower.update(1, 1, n, tmp.S, inf);
    		st_higher.update(1, 1, n, tmp.S, inf);
    	}
    }
    cout << res;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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