제출 #1278922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278922		g4yuhg	Sails (IOI07_sails)	C++20	100 / 100	67 ms	1412 KiB

sails

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 100005
#define LOG 18
using namespace std;

const ll inf = 1e9;

bool ghuy4g;

ll n, m;
pii a[N];

ll st[4 * N], f[4 * N];

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] += f[id];
	if (id * 2 < 4 * N) {
		f[id * 2] += f[id];
	}
	if (id * 2 + 1 < 4 * N) {
		f[id * 2 + 1] += f[id];
	}
	f[id] = 0;
}

ll bit[N];

void upd(ll u, ll v) {
	ll idx = u;
	while (idx <= m) {
		bit[idx] += v;
		idx += idx & (-idx);
	}
}

ll ge(ll u) {
	ll idx = u, ans = 0;
	while (idx > 0) {
		ans += bit[idx];
		idx -= idx & (-idx);
	}
	return ans;
}

void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	upd(L, 1);
	upd(R + 1, -1);
	return;
	if (L > R) return;
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = min(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll i) {
	return ge(i);
	lazy(id);
	if (i > r || i < l) return inf;
	if (l == r) {
		return st[id];
	}
	ll mid = (l + r) / 2;
	return min(get(id * 2, l, mid, i), get(id * 2 + 1, mid + 1, r, i));
}

ll find(ll u, ll gh) { // vi tri pos nho nhat ma a[pos] <= u
	if (u < 0) return gh + 1;
	ll l = 1, r = gh, ans = gh + 1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (get(1, 1, m, mid) <= u) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return ans;
}

void solve() {
	for (int i = 1; i <= n; i ++) {
		//cout << "i " << a[i].fi << " " << a[i].se << endl;
		ll l = a[i].fi, r = l - a[i].se + 1;
		ll u = get(1, 1, m, r);
		ll kt = find(u, a[i].fi), bd = find(u - 1, a[i].fi) - 1;
		ll len = bd - r + 1;
		//cout << " " << l << " " << r << " " << bd << " " << kt << " " << len << endl;
		if (bd + 1 <= l) {
			upd(bd + 1, 1);
			upd(l + 1, -1);
			//update(1, 1, m, bd + 1, l, 1);
			//cout << " -" << "upd " << bd + 1 << " " << l << endl;
		}
		//update(1, 1, m, kt, kt + len - 1, 1);
		upd(kt, 1);
		upd(kt + len, -1);
		//cout << " -" << "upd " << kt << " " << kt + len - 1 << endl;
		/*for (int j = 1; j <= m; j ++) {
			//cout << get(1, 1, m, j) << " ";
		}*/
		//cout << endl;
	}
	long long ans = 0;
	for (int i = 1; i <= m; i ++) {
		ll xet = get(1, 1, m, i);
		ans += (long long)xet * (long long)(xet - 1) / 2;
	}
	cout << ans;
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].fi >> a[i].se;
		m = max(m, a[i].fi);
	}
	sort(a + 1, a + 1 + n);
	
	solve();
	
		
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10