oj.uz

Submission #103010

# Submission time Handle Problem Language Result Execution time Memory
103010 2019-03-28T15:21:15 Z DystoriaX Sails (IOI07_sails) C++14
75 / 100
 108 ms 2676 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){
	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);
			updPos(L);
			updMin(R - l + L);
			//cout << "Updated: " << L << " " << R - l + L - 1 << endl;
		}
	}

	long long ans = 0;
	for(int i = 0; i <= 100000; 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:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sails.cpp:29: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 512 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 4 ms 384 KB Output is correct
2 Correct 3 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 4 ms 384 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Incorrect 23 ms 896 KB Output isn't correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1024 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2168 KB Output is correct
2 Correct 65 ms 2272 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2520 KB Output is correct
2 Correct 67 ms 2168 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2676 KB Output is correct
2 Incorrect 66 ms 2352 KB Output isn't correct