oj.uz

Submission #71494

# Submission time Handle Problem Language Result Execution time Memory
71494 2018-08-24T23:12:30 Z RezwanArefin01 Sails (IOI07_sails) C++17
100 / 100
 161 ms 8672 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
int t[N]; ii s[N]; 

void update(int x, int v) {
	for(; x < N; x += x & -x) 
		t[x] += v; 
}
int read(int x, int ret = 0) {
	for(; x > 0; x -= x & -x) 
		ret += t[x]; 
	return ret; 
}
void update(int l, int r, int v) {
	update(l, v); update(r + 1, -v); 
}
int main(int argc, char const *argv[]) {
	int n; scanf("%d", &n); 
	for(int i = 0; i < n; i++) {
		cin >> s[i].first >> s[i].second; 
	}
	sort(s, s + n); 

	for(int i = 0; i < n; i++) {
		int h = s[i].first, k = s[i].second; 
		int l = h - k + 1, r = h; 
		int c = read(l); 

		int lo = 1, hi = h, L, R; 
		while(lo <= hi) {
			int mid = lo + hi >> 1; 
			if(read(mid) >= c) lo = mid + 1, R = mid; 
			else hi = mid - 1; 
		}

		lo = 1, hi = h;
		while(lo <= hi) {
			int mid = lo + hi >> 1; 
			if(read(mid) <= c) hi = mid - 1, L = mid; 
			else lo = mid + 1; 
		}

		update(R + 1, r, 1);
		update(L, L + k - r + R - 1, 1); 
	}

	ll ans = 0;
	for(int i = 1; i < N; i++) {
		int x = read(i);
		ans += (ll) x * (x - 1) / 2; 
	}
	
	printf("%lld\n", ans);
}

Compilation message

sails.cpp: In function 'int main(int, const char**)':
sails.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1; 
              ~~~^~~~
sails.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1; 
              ~~~^~~~
sails.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n); 
         ~~~~~^~~~~~~~~~
sails.cpp:49:23: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   update(L, L + k - r + R - 1, 1); 
             ~~~~~~~~~~^~~
sails.cpp:49:15: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
   update(L, L + k - r + R - 1, 1); 
             ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1172 KB Output is correct
2 Correct 36 ms 1472 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1888 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2688 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 3984 KB Output is correct
2 Correct 113 ms 4896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 5944 KB Output is correct
2 Correct 101 ms 6820 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 7864 KB Output is correct
2 Correct 112 ms 8672 KB Output is correct