oj.uz

Submission #54290

# Submission time Handle Problem Language Result Execution time Memory
54290 2018-07-03T05:54:04 Z 진화론자(#2049) Sails (IOI07_sails) C++11
100 / 100
 201 ms 9332 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 22 ms 4472 KB Output is correct
2 Correct 20 ms 4472 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4800 KB Output is correct
2 Correct 66 ms 5472 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5620 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 5832 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 6260 KB Output is correct
2 Correct 150 ms 7216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 7444 KB Output is correct
2 Correct 133 ms 8072 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 8428 KB Output is correct
2 Correct 148 ms 9332 KB Output is correct