oj.uz

Submission #197399

# Submission time Handle Problem Language Result Execution time Memory
197399 2020-01-21T01:02:22 Z arnold518 Sails (IOI07_sails) C++14
100 / 100
 365 ms 4328 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;

struct Data { int H, K; };

int N;
Data A[MAXN+10];

ll tree[4*MAXN+10], ans;

ll getval(int node, int tl, int tr, int pos)
{
	if(tl==tr) return tree[node];
	int mid=tl+tr>>1;
	if(pos<=mid) return tree[node]+getval(node*2, tl, mid, pos);
	else return tree[node]+getval(node*2+1, mid+1, tr, pos);
}

void update(int node, int tl, int tr, int l, int r)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r) { tree[node]++; return; }
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r);
	update(node*2+1, mid+1, tr, l, r);
}

int main()
{
	int i, j;
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d%d", &A[i].H, &A[i].K);

	sort(A+1, A+N+1, [&](const Data &p, const Data &q) { return p.H<q.H; });

	for(i=1; i<=N; i++)
	{
		int lo, hi, l, r;
		ll val=getval(1, 1, MAXN, A[i].H-A[i].K+1);

		lo=0, hi=A[i].H-A[i].K+1;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(val==getval(1, 1, MAXN, mid)) hi=mid;
			else lo=mid;
		}
		l=hi;

		lo=A[i].H-A[i].K+1, hi=A[i].H+1;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(val==getval(1, 1, MAXN, mid)) lo=mid;
			else hi=mid;
		}
		r=lo;

		update(1, 1, MAXN, r+1, A[i].H);
		update(1, 1, MAXN, l, l+A[i].K-A[i].H+r-1);

		//printf("%d %d\n", l, r);

		//for(j=1; j<=10; j++) printf("%lld ", getval(1, 1, MAXN, j)); printf("\n");
	}

	for(i=1; i<=MAXN; i++)
	{
		ll t=getval(1, 1, MAXN, i);
		ans+=t*(t-1)/2;
	}
	printf("%lld", ans);
}

Compilation message

sails.cpp: In function 'll getval(int, int, int, int)':
sails.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sails.cpp: In function 'void update(int, int, int, int, int)':
sails.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
sails.cpp: In function 'int main()':
sails.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
sails.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
sails.cpp:36:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sails.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
sails.cpp:38:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d", &A[i].H, &A[i].K);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1144 KB Output is correct
2 Correct 71 ms 1044 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2376 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 3980 KB Output is correct
2 Correct 225 ms 3804 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 4168 KB Output is correct
2 Correct 115 ms 3164 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 4328 KB Output is correct
2 Correct 172 ms 2808 KB Output is correct