Submission #54359

#	Time	Username	Problem	Language	Result	Execution time	Memory
54359		khsoo01	Sails (IOI07_sails)	C++11	100 / 100	218 ms	6268 KiB

sails

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 100005, inf = 1e18;

ll n;
pll a[N];

struct segtree {
	ll v[4*N+4], l[4*N+4];
	void lazydown (ll P) {
		v[2*P] += l[P];
		v[2*P+1] += l[P];
		l[2*P] += l[P];
		l[2*P+1] += l[P];
		l[P] = 0;
	}
	void upd (ll S, ll E, ll V, ll SS = 1, ll SE = N, ll P = 1) {
		if(S <= SS && SE <= E) {
			v[P] += V;
			l[P] += V;
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		ll M = (SS+SE)/2;
		upd(S, E, V, SS, M, 2*P);
		upd(S, E, V, M+1, SE, 2*P+1);
		v[P] = min(v[2*P], v[2*P+1]);
	}
	ll get (ll S, ll E, ll SS = 1, ll SE = N, ll P = 1) {
		if(S <= SS && SE <= E) return v[P];
		if(E < SS || SE < S) return inf;
		lazydown(P);
		ll M = (SS+SE)/2;
		return min(get(S,E,SS,M,2*P), get(S,E,M+1,SE,2*P+1));
	}
	ll get (ll P) {return get(P, P);}
	ll lb (ll K, ll SS = 1, ll SE = N, ll P = 1) {
		if(SS == SE) return SS;
		lazydown(P);
		ll M = (SS+SE)/2;
		if(v[2*P] <= K) return lb(K, SS, M, 2*P);
		return lb(K, M+1, SE, 2*P+1);
	}
} seg;

int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
	}
	sort(a+1, a+1+n);
	for(int i=1;i<=n;i++) {
		ll V = seg.get(a[i].X-a[i].Y+1);
		ll L = seg.lb(V), R = seg.lb(V-1);
		ll C = max(0ll, a[i].X - R + 1);
		seg.upd(R, a[i].X, 1);
		seg.upd(L, L + a[i].Y-C - 1, 1);
	}
	ll ans = 0;
	for(int i=1;i<=N;i++) {
		ll T = seg.get(i);
		ans += T * (T-1) / 2;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
sails.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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