Submission #199617

#	Time	Username	Problem	Language	Result	Execution time	Memory
199617		sjimed	Sails (IOI07_sails)	C++14	100 / 100	152 ms	3568 KiB

sails

#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 / 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