Submission #235545

#	Time	Username	Problem	Language	Result	Execution time	Memory
235545		davitmarg	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	5 ms	384 KiB

joi2019_ho_t4

/*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 + (j != 1));
			nxt[2] = p[2].get(1, 1, n, i + (j != 2));
			if (nxt[j] <= nxt[3 - j] + 1)
			{
				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
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63