蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）线段树（

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
	#include <bits/stdc++.h>
#endif

typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) < '0' || o > '9'); return o;
	}
	inline double reod() {
		double o = read(), f = 1; char c;
		while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
		return o;
	}
}
using namespace IO;

const int SIZE = 2E5 + 7, Mod = 1E9 + 7;

struct Node {
	int L, R, w, e, Lazy;
} Node[SIZE << 2]; int ans = 0;
vector<int> vec[SIZE];


void BUILD(int now, int L, int R) {
	Node[now].L = L, Node[now].R = R;
	if (L == R) return;
	int M = (L + R) >> 1;
	BUILD(now << 1, L, M), BUILD(now << 1 | 1, M + 1, R);
}

void pushdown(int now) {
	if (Node[now].Lazy) {
		Node[now << 1].Lazy += Node[now].Lazy;
		Node[now << 1 | 1].Lazy += Node[now].Lazy;
		Node[now].Lazy = 0;
	}
}

void Add(int now, int pos, int w) {
	if (Node[now].L == Node[now].R) {
		Node[now].w = Node[now].w + Node[now].Lazy;
		if (Node[now].e && Node[now].w <= 3) Node[now].e = 0;
		w -= (Node[now].w < 0);
		Node[now].w = max(0, Node[now].w);
		Node[now].w += w;
		if (Node[now].e == 0 && Node[now].w >= 6) Node[now].e = 1;
		Node[now].Lazy = 0;
		return;
	} pushdown(now);
	int M = (Node[now].L + Node[now].R) >> 1;
	if (pos > M) Add(now << 1 | 1, pos, w);
	else Add(now << 1, pos, w);
	Node[now].e = Node[now << 1].e + Node[now << 1 | 1].e;
}

void DFS(int now) {
	if (Node[now].L == Node[now].R) {
		if (Node[now].Lazy) {
			Node[now].w = max(Node[now].w + Node[now].Lazy, 0);
			if (Node[now].e && Node[now].w <= 3) Node[now].e = 0;
			Node[now].Lazy = 0;
		}
		return;
	} pushdown(now);
	DFS(now << 1 | 1), DFS(now << 1);
	Node[now].e = Node[now << 1].e + Node[now << 1 | 1].e;
}

int main() {
	int N = read(), M = read(), T = read();
	for (int pos = 1, e; pos <= M; pos++) e = read(), vec[e].push_back(read());
	BUILD(1, 1, N);
	int pos = 1; while (vec[pos].size() == 0) pos++;
	while (pos <= T) {
		Node[1].Lazy += -1;
		sort(vec[pos].begin(), vec[pos].end());
		for (int e = 0, v = 1, R = vec[pos].size(); e < R; e++) {
			while (e + v < R && vec[pos][e + v] == vec[pos][e]) v++;
			Add(1, vec[pos][e], 1 + (v << 1));
			e = e + v - 1, v = 1;
		}
		pos++;
	} DFS(1), printf("%d\n", Node[1].e);
}