frogsandmosquitos.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <utility>
#include <algorithm>
#include <set>

constexpr int MAXN = 200500;
constexpr int MAXM = 200500;
constexpr int MAXP = 1000000000;

int N; //num of frogs
int M; //num of mosqs

struct Frog {
	int pos;
	int id;
	int size;
};

struct Mosquito {
	int pos;
	int size;
};

Frog FROGS[MAXN];
Mosquito MOSQUITOS[MAXM];

int URANGEB;
int URANGEE;

class Node {
public:
	Node* left;
	Node* right;
	int leftest;
	int rightest;

	Node(Node* left, Node* right, int leftest, int rightest) : left{ left }, right{ right }, leftest{ leftest }, rightest{ rightest }{};

	static Node* Build(int l, int r) {
		if (l == r)
			return new Node(nullptr, nullptr, FROGS[l].pos, FROGS[l].pos + FROGS[l].size);
		int mid = (l + r) >> 1;
		Node* a = Build(l, mid);
		Node* b = Build(mid + 1, r);
		return new Node(a, b, a->leftest, std::max(a->rightest, b->rightest));
	}

	bool TryFeedMosquito(Mosquito m, int l, int r) {
		int mid = (l + r) >> 1;
		if (l==r)
		{
			if (leftest > m.pos || rightest < m.pos)
				return false;
			URANGEB = rightest;
			rightest += m.size;
			FROGS[l].size += m.size;
			URANGEE = rightest;
			return true;
		}
		if (m.pos <= left->rightest)
		{
			return left->TryFeedMosquito(m, l, mid);
		}
		else if (m.pos >= right->leftest)
		{
			return right->TryFeedMosquito(m, mid + 1, r);
		}
		else
			return false;
	}
};

int SIZE[MAXN];
int COUNT[MAXN];

std::set<Mosquito> MSET;

Node* root;

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++)
	{
		scanf("%d%d", &FROGS[i].pos, &FROGS[i].size);
		FROGS[i].id = i + 1;
	}
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &MOSQUITOS[i].pos, &MOSQUITOS[i].size);
	}
	std::sort(FROGS, FROGS + N, [](const Frog& a, const Frog& b) {return a.pos < b.pos; });
	root = Node::Build(0, N - 1);
	for (int m = 0; m < M; m++) {
		bool b = root->TryFeedMosquito(MOSQUITOS[m], 0, N - 1);
	}
}