oj.uz

Submission #235547

# Submission time Handle Problem Language Result Execution time Memory
235547 2020-05-28T13:43:44 Z davitmarg Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 5 ms 384 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 100005;

struct segtree
{
	int t[4 * N] = { 0 };
	void add(int v, int l, int r, int pos, int val)
	{
		if (l == r)
		{
			t[v] += val;
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m)
			add(v * 2, l, m, pos, val);
		else
			add(v * 2 + 1, m + 1, r, pos, val);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}


	int get(int v, int l, int r, int i, int j)
	{
		if (i > j)
			return 0;
		if (l == i && r == j)
			return t[v];
		int m = (l + r) / 2;
		return
			get(v * 2, l, m, i, min(m, j)) +
			get(v * 2 + 1, m + 1, r, max(m + 1, i), j);
	}

	int get(int v, int l, int r, int pos)
	{
		if (t[v] == 0)
			return mod;
		if (l == r)
			return l;
		int m = (l + r) / 2;
		if (pos <= m && t[v * 2])
			return get(v * 2, l, m, pos);
		return get(v * 2 + 1, m + 1, r, pos);
	}
};

LL n;
LL ans, a[3][N];

segtree p[2];

int main()
{
	fastIO;
	cin >> n;
	for (int i = 1; i <= n + n; i++)
	{
		LL x, y;
		cin >> x >> y;
		if (x < 1)
		{
			ans += 1ll - x;
			x = 1;
		}
		else if (x > n)
		{
			ans += x - n;
			x = n;
		}
		if (y < 1)
		{
			ans += 1ll - y;
			y = 1;
		}
		else if (y > 2)
		{
			ans += y - 2ll;
			y = 2;
		}
		a[y][x]++;
		p[y].add(1, 1, n, x, 1);
	}

	for (int i = 1; i <= n; i++)
	{
		int c[3] = { 0, p[1].get(1, 1, n, i, i), p[2].get(1, 1, n, i, i) };

		if(c[2]==0 && c[1]>=2)
		{
			p[2].add(1, 1, n, i, 1);
			c[2]++;
			p[1].add(1, 1, n, i, -1);
			c[1]--;
			ans++;
		}

		if (c[1] == 0 && c[2] >= 2)
		{
			p[1].add(1, 1, n, i, 1);
			c[1]++;
			p[2].add(1, 1, n, i, -1);
			c[2]--;
			ans++;
		}

		LL nxt[3] = { 0 };
		for (int j = 1; j <= 2; j++)
		{
			if (c[j])
				continue;
			nxt[1] = p[1].get(1, 1, n, i + 1);
			nxt[2] = p[2].get(1, 1, n, i + 1);
			if (nxt[j] < nxt[3 - j] + 1 || (nxt[j] == nxt[3 - j] + 1 && p[j].get(1, 1, n, i + 1, n) >= p[3 - j].get(1, 1, n, i + 1, n)))
			{
				p[j].add(1, 1, n, nxt[j], -1);
				ans += nxt[j] - (LL)i;
				c[j]++;
			}
			else
			{
				p[3 - j].add(1, 1, n, nxt[3 - j], -1);
				c[j]++;
				ans += nxt[3 - j] - (LL)i;
				ans++;
			}
		}
		if (i == n)
			continue;
		c[1]--;
		c[2]--;
		ans += c[1];
		ans += c[2];
		p[1].add(1, 1, n, i + 1, c[1]);
		p[2].add(1, 1, n, i + 1, c[2]);
	}

	cout << ans << endl;
	return 0;
}

/*


*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -