Submission #197399

#	Time	Username	Problem	Language	Result	Execution time	Memory
197399		arnold518	Sails (IOI07_sails)	C++14	100 / 100	365 ms	4328 KiB

sails

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

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