Submission #71494

#	Time	Username	Problem	Language	Result	Execution time	Memory
71494		RezwanArefin01	Sails (IOI07_sails)	C++17	100 / 100	161 ms	8672 KiB

sails

#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 (stderr)

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