oj.uz

Submission #103012

# Submission time Handle Problem Language Result Execution time Memory
103012 2019-03-28T15:40:50 Z DystoriaX Sails (IOI07_sails) C++14
100 / 100
 103 ms 1576 KB 
#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

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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 304 KB Output is correct
2 Correct 5 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 27 ms 640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 740 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1052 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1344 KB Output is correct
2 Correct 73 ms 1272 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1472 KB Output is correct
2 Correct 81 ms 1440 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1576 KB Output is correct
2 Correct 77 ms 1244 KB Output is correct