oj.uz

Submission #54366

# Submission time Handle Problem Language Result Execution time Memory
54366 2018-07-03T09:04:39 Z 김세빈(#1473) Sails (IOI07_sails) C++11
100 / 100
 130 ms 3956 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

pll K[101010];
ll T[303030];
ll n, sz, max_h, ans;

void add(ll l, ll r)
{
	l += sz, r += sz;
	for(;l<r;){
		if(l & 1) T[l] ++;
		if(~r & 1) T[r] ++;
		
		l = l+1 >> 1;
		r = r-1 >> 1;
	}
	if(l == r) T[l] ++;
}

ll get_val(ll p)
{
	ll ret = 0;
	p += sz;
	
	for(;p;p>>=1){
		ret += T[p];
	}
	
	return ret;
}

int main()
{
	ll i, j, k, t, s, e, mid, use;
	
	scanf("%lld", &n);
	
	for(i=0;i<n;i++){
		scanf("%lld%lld", &K[i].first, &K[i].second);
		max_h = max(max_h, K[i].first);
	}
	
	for(sz=1;sz<max_h;sz<<=1);
	
	sort(K, K+n);
	
	for(i=0;i<n;i++){
		k = get_val(K[i].first - K[i].second);
		
//		printf("%d %d\n",K[i].first, K[i].second);
		
		s = K[i].first - K[i].second, e = K[i].first - 1;
		for(;s<=e;){
			mid = s+e >> 1;
			t = get_val(mid);
			if(t < k) e = mid - 1;
			else s = mid + 1;
		}
		use = min(K[i].second, K[i].first - (e+1));
		add(e + 1, e + use);
		
		s = 0, e = K[i].first - K[i].second;
		for(;s<=e;){
			mid = s+e >> 1;
			t = get_val(mid);
			if(t <= k) e = mid - 1;
			else s = mid + 1;
		}
		use = K[i].second - use;
		add(e + 1, e + use);
		
//		for(int j=0;j<max_h;j++) printf("%lld ",get_val(j));
//		printf("\n");
	}
	
	for(i=2;i<sz+max_h;i++) T[i] += T[i>>1];
	
	for(i=0;i<max_h;i++) ans += T[sz+i] * (T[sz+i] - 1) / 2;
	
	printf("%lld\n",ans);
	
	return 0;
}

Compilation message

sails.cpp: In function 'void add(ll, ll)':
sails.cpp:19:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l+1 >> 1;
       ~^~
sails.cpp:20:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r-1 >> 1;
       ~^~
sails.cpp: In function 'int main()':
sails.cpp:59:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
sails.cpp:69:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
sails.cpp:39:8: warning: unused variable 'j' [-Wunused-variable]
  ll i, j, k, t, s, e, mid, use;
        ^
sails.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
sails.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &K[i].first, &K[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 544 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2352 KB Output is correct
2 Correct 25 ms 2352 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2352 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 3676 KB Output is correct
2 Correct 99 ms 3676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3804 KB Output is correct
2 Correct 57 ms 3804 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3956 KB Output is correct
2 Correct 81 ms 3956 KB Output is correct