oj.uz

Submission #152650

# Submission time Handle Problem Language Result Execution time Memory
152650 2019-09-08T20:46:40 Z luciocf Sails (IOI07_sails) C++14
100 / 100
 229 ms 4312 KB 
#include <bits/stdc++.h>

#define mx first
#define mn second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+10;
const int inf = 1e9+10;

pii a[maxn];

pii tree[4*maxn];
int lazy[4*maxn];

void flush(int node, int l, int r)
{
	if (!lazy[node]) return;

	if (l != r)
	{
		lazy[2*node] += lazy[node];
		lazy[2*node+1] += lazy[node];
	}

	tree[node].mx += lazy[node];
	tree[node].mn += lazy[node];
	lazy[node] = 0;
}

void upd(int node, int l, int r, int a, int b, int v)
{
	flush(node, l, r);
	if (l > b || r < a) return;

	if (l >= a && r <= b)
	{
		lazy[node] = v;
		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

	tree[node].mx = max(tree[2*node].mx, tree[2*node+1].mx);
	tree[node].mn = min(tree[2*node].mn, tree[2*node+1].mn);
}

int get(int node, int l, int r, int pos)
{
	flush(node, l, r);
	if (l == r) return tree[node].mn;

	int mid = (l+r)>>1;

	if (pos <= mid) return get(2*node, l, mid, pos);
	return get(2*node+1, mid+1, r, pos);
}

int query1(int node, int l, int r, int v)
{
	flush(node, l, r);
	if (l == r) return l;

	int mid = (l+r)>>1;

	flush(2*node, l, mid); flush(2*node+1, mid+1, r);

	if (tree[2*node].mn <= v) return query1(2*node, l, mid, v);
	return query1(2*node+1, mid+1, r, v);
}

int query2(int node, int l, int r, int v)
{
	flush(node, l, r);
	if (l == r) return l;

	int mid = (l+r)>>1;

	flush(2*node, l, mid); flush(2*node+1, mid+1, r);

	if (tree[2*node+1].mx >= v) return query2(2*node+1, mid+1, r, v);
	return query2(2*node, l, mid, v);
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].first, &a[i].second);

	sort(a+1, a+n+1);

	for (int i = 1; i <= n; i++)
	{
		int h = a[i].first, k = a[i].second;

		int x = get(1, 1, maxn-1, h-k+1);

		int p1 = query1(1, 1, maxn-1, x);
		int p2 = min(h, query2(1, 1, maxn-1, x));

		if (p2 < h) upd(1, 1, maxn-1, p2+1, h, 1);

		int r = k-(h-p2);

		upd(1, 1, maxn-1, p1, p1+r-1, 1);
	}

	long long ans = 0;

	for (int i = 1; i < maxn; i++)
	{
		long long x = get(1, 1, maxn-1, i);

		ans += ((x*(x-1ll))/2ll);
	}

	printf("%lld\n", ans);
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 504 KB Output is correct
2 Correct 17 ms 3448 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1360 KB Output is correct
2 Correct 66 ms 756 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 4088 KB Output is correct
2 Correct 158 ms 4064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 4160 KB Output is correct
2 Correct 106 ms 4312 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 4228 KB Output is correct
2 Correct 154 ms 2108 KB Output is correct