oj.uz

Submission #152648

# Submission time Handle Problem Language Result Execution time Memory
152648 2019-09-08T20:38:35 Z luciocf Sails (IOI07_sails) C++14
5 / 100
 212 ms 5380 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;

int h[maxn], k[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", &h[i], &k[i]);

	for (int i = 1; i <= n; i++)
	{
		int x = get(1, 1, maxn-1, h[i]-k[i]+1);

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

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

		int r = k[i]-(h[i]-p2);

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

	long long ans = 0;

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

		ans += 1ll*((x*(x-1))/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", &h[i], &k[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 1944 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 2920 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 4908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 5288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 5380 KB Output isn't correct
2 Halted 0 ms 0 KB -