oj.uz

Submission #366567

# Submission time Handle Problem Language Result Execution time Memory
366567 2021-02-14T14:31:17 Z cheissmart Sails (IOI07_sails) C++14
100 / 100
 166 ms 5356 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3436 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3436 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 4 ms 3436 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3564 KB Output is correct
2 Correct 5 ms 3436 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3564 KB Output is correct
2 Correct 46 ms 3948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4076 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4460 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4972 KB Output is correct
2 Correct 119 ms 4972 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5228 KB Output is correct
2 Correct 73 ms 4844 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 5356 KB Output is correct
2 Correct 127 ms 5320 KB Output is correct