Submission #103012

#	Time	Username	Problem	Language	Result	Execution time	Memory
103012		DystoriaX	Sails (IOI07_sails)	C++14	100 / 100	103 ms	1576 KiB

sails

#include <bits/stdc++.h>

using namespace std;

int bit[100010];
int n;
vector<pair<int, int> > v;
const int mx = 100001;

int getVal(int x){
	if(x == 0) return 100001;
	int ret = 0;
	for(; x > 0; x -= (x & (-x))) ret += bit[x];

	return ret;
}

void updPos(int x){
	for(; x <= mx; x += (x & (-x))) bit[x]++;
}

void updMin(int x){
	for(; x <= mx; x += (x & (-x))) bit[x]--;
}

int main(){
	scanf("%d", &n);

	v.resize(n);
	for(int i = 0; i < n; i++) scanf("%d%d", &v[i].first, &v[i].second);

	sort(v.begin(), v.end());

	for(auto it : v){
		int h, k;
		tie(h, k) = it;

		int l = h - k + 1;

			// cout << "Proc: " << h << " " << k << endl;
			// cout << "with val " << l << endl;
			// cout << getVal(l - 1) << " " << getVal(l) << endl; 
			//cout << "HERE\n" << l << " " << L << " " << R << " " << R - l + L << endl;

		if(l == 1 || getVal(l - 1) > getVal(l)){
			updPos(l);
			updMin(h + 1);
			//cout << "Updated: " << l << " " << h << endl;
		} else {
			int L = 0, R = h + 1;

			int lo = 0, hi = h + 1;
			int tmp = getVal(l);

			//Find lowerbound
			while(lo <= hi){
				int mid = (lo + hi) >> 1;
				if(getVal(mid) > tmp){
					lo = mid + 1;
					L = mid;
				} else hi = mid - 1;
			}
			L++;

			lo = 0, hi = h + 1;
			//Find upperbound
			while(lo <= hi){
				int mid = (lo + hi) >> 1;

				if(getVal(mid) >= tmp){
					lo = mid + 1;
				} else R = mid, hi = mid - 1;
			}

			//cout << "Same Segments: " << L << " " << R << "\n";

			//Update [R + 1, H] and [L, L + remaining length]
			if(R <= h) updPos(R), updMin(h + 1);
				//cout << "Updated: " << R << " " << h << endl
			
			updPos(L);
			updMin(R - l + L);
			//cout << "Updated: " << L << " " << R - l + L - 1 << endl;
		}
	}

	long long ans = 0;
	for(int i = 1; i <= 100001; i++){
		long long tp = getVal(i);
		ans += tp * (tp - 1) / 2;
	}

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sails.cpp:30:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < n; i++) scanf("%d%d", &v[i].first, &v[i].second);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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