oj.uz

Submission #199617

# Submission time Handle Problem Language Result Execution time Memory
199617 2020-02-02T09:02:43 Z sjimed Sails (IOI07_sails) C++14
100 / 100
 152 ms 3568 KB 
#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;  
const int inf = 1e9;

int n;
vector<pii> v;
vector<int> x;
int tree[101010];
ll ans;

void update(int i, int x) {
	while(i <= 100010) {
		tree[i] += x;
		i += i & -i;
	}
}

int get(int i) {
	if(i == 0) return inf;
	
	int ret = 0;
	while(i) {
		ret += tree[i];
		i -= i & -i;
	}

	return ret;
}

int f(int x) {
	return -x*x;
}

int main() {
	fast;

	cin >> n;

	for(int i=0; i<n; i++) {
		int h, k;
		cin >> h >> k;

		v.eb(h, k);
	}

	for(int i=0; i<=100010; i++) {
		x.eb(i);
	}

	sort(all(v));

	for(auto i : v) {
		int lb = lower_bound(all(x), i.fi - i.se + 1, [](int a, int b) { return get(a) > get(b); }) - x.begin();
		int ub = upper_bound(all(x), i.fi - i.se + 1, [](int a, int b) { return get(a) > get(b); }) - x.begin();

		int k = i.se;

		if(ub <= i.fi) {
			update(ub, 1);
			update(i.fi+1, -1);
			k -= i.fi + 1 - ub;
		}

		update(lb, 1);
		update(lb + k, -1);
	}

	for(int i=1; i<=100010; i++) {
		ll t = get(i);
		ans += t * (t-1)/2;
	}

	cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1020 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1012 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1032 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1144 KB Output is correct
2 Correct 39 ms 1528 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2036 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 3180 KB Output is correct
2 Correct 107 ms 3180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3436 KB Output is correct
2 Correct 111 ms 3056 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3568 KB Output is correct
2 Correct 116 ms 3308 KB Output is correct