oj.uz

Submission #54359

# Submission time Handle Problem Language Result Execution time Memory
54359 2018-07-03T08:17:32 Z khsoo01 Sails (IOI07_sails) C++11
100 / 100
 218 ms 6268 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4436 KB Output is correct
2 Correct 22 ms 4456 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4508 KB Output is correct
2 Correct 23 ms 4580 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4656 KB Output is correct
2 Correct 21 ms 4656 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4656 KB Output is correct
2 Correct 22 ms 4660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4824 KB Output is correct
2 Correct 63 ms 5156 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 5464 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 5960 KB Output is correct
2 Correct 171 ms 5960 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 6252 KB Output is correct
2 Correct 111 ms 6252 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 6252 KB Output is correct
2 Correct 146 ms 6268 KB Output is correct