Submission #366567

#	Time	Username	Problem	Language	Result	Execution time	Memory
366567		cheissmart	Sails (IOI07_sails)	C++14	100 / 100	166 ms	5356 KiB

sails

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

struct node {
	int mx, lz;
	node(int val = 0) {
		mx = val;
		lz = 0;
	}
};

node t[N * 4];

void apply(int v, int val) {
	t[v].mx += val;
	t[v].lz += val;
}

void push(int v) {
	apply(v * 2, t[v].lz);
	apply(v * 2 + 1, t[v].lz);
	t[v].lz = 0;
}

void add(int l, int r, int val, int v = 1, int tl = 0, int tr = N) {
	if(l <= tl && tr <= r) {
		apply(v, val);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(l < tm) add(l, r, val, v * 2, tl, tm);
	if(r > tm) add(l, r, val, v * 2 + 1, tm, tr);
	t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}

int qry(int pos, int v = 1, int tl = 0, int tr = N) {
	if(tr - tl == 1)
		return t[v].mx;
	push(v);
	int tm = (tl + tr) / 2;
	if(pos < tm) return qry(pos, v * 2, tl, tm);
	else return qry(pos, v * 2 + 1, tm, tr);
}

int find_first_geq(int val, int v = 1, int tl = 0, int tr = N) {
	if(tr - tl == 1) {
		if(t[v].mx >= val) return tl;
		else {
			assert(tl == N - 1);
			return N;
		}
	}
	push(v);
	int tm = (tl + tr) / 2;
	if(t[v * 2].mx >= val) return find_first_geq(val, v * 2, tl, tm);
	else return find_first_geq(val, v * 2 + 1, tm, tr);
}

ll c(int n) {
	return (ll) n * (n - 1) / 2;
}

ll ans(int v = 1, int tl = 0, int tr = N) {
	if(tr - tl == 1) {
		return c(t[v].mx);
	}
	push(v);
	int tm = (tl + tr) / 2;
	return ans(v * 2, tl, tm) + ans(v * 2 + 1, tm, tr);
}

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	V<pi> v(n);
	for(int i = 0; i < n; i++) cin >> v[i].F >> v[i].S;
	sort(ALL(v));
	for(int i = 0; i < n; i++) {
		int L = N - v[i].F;
		int R = L + v[i].S - 1;
		int val_r = qry(R);
		int l = max(find_first_geq(val_r), L);
		int r = max(find_first_geq(val_r + 1), L);
		int take_r = R - l + 1;
		if(L < l) add(L, l, 1);
		add(r - take_r, r, 1);
	}
	cout << ans() << '\n';

}

• 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