60分调不动,求大佬帮调
查看原帖
60分调不动,求大佬帮调
396974
Buried_Dream楼主2022/7/13 15:10

/**
 *	author: TLE_Automation
 *	creater: 2022.7.9
**/
#include<cmath>
#include<queue>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gc getchar 
using namespace std;
typedef long long ll;
//#define int long long
const int N = 1e6 + 10;
const int MAXN = 2e5 + 10;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline int ksm(int a, int b) {int base = a % mod, res = 1; while(b){if(b & 1) res = (res * base) % mod; base = (base * base) % mod, b >>= 1;}return res % mod;}
inline int mul(int a, int b) {int base = a % mod, res = 0; while(b){if(b & 1) res = (res + base) % mod; base = (base + base) % mod, b >>= 1;}return res % mod;}
inline char readchar() {static char buf[100000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;}
inline int read() { int res = 0, f = 0; char ch = gc();for (; !isdigit(ch); ch = gc()) f |= (ch == '-'); for (; isdigit(ch); ch = gc()) res = (res << 1) + (res << 3) + (ch ^ '0'); return f ? -res : res;}

int n, m;
int lsh[N];

struct Node {
	int date, bh, change;
	bool operator < (const Node &x) const {return date < x.date;}
}a[N << 2];

namespace Seg {
	#define lson rt << 1
	#define rson rt << 1 | 1
	struct Node { int l, r, max, rk, cnt;} tree[N << 2];
	void pushup(int rt) {
		if(tree[lson].max > tree[rson].max) {
			tree[rt].max = tree[lson].max;
			tree[rt].cnt = tree[lson].cnt; 
			tree[rt].rk = tree[lson].rk;
		}
		if(tree[lson].max < tree[rson].max) {
			tree[rt].max = tree[rson].max;
			tree[rt].cnt = tree[rson].cnt; 
			tree[rt].rk = tree[rson].rk;
		}
		if(tree[lson].max == tree[rson].max) {
			tree[rt].max = tree[lson].max;
			tree[rt].rk = tree[lson].rk;
			tree[rt].cnt = tree[lson].cnt + tree[rson].cnt;
		}
	}
	void build(int rt, int l, int r) {
		tree[rt].l = l, tree[rt].r = r;
		if(l == r) {
			tree[rt].max = m, tree[rt].cnt = 1, tree[rt].rk = a[l].bh;
			return;
		} int mid = (l + r) >> 1;
		build(lson, l, mid), build(rson, mid + 1, r); 
		pushup(rt);
	}
	void change(int rt, int x, int k) {
		if(tree[rt].l > x || tree[rt].r < x) return;
		if(tree[rt].l == tree[rt].r && tree[rt].l == x) {
			tree[rt].max += k; return;
		} change(lson, x, k), change(rson, x, k);
		pushup(rt);
	}
}

using namespace Seg;

ll ans = 0;

signed main() 
{
	n = read(), m = read();
	for(int i = 1; i <= n; i++) 
		a[i].date = read(), a[i].bh = lsh[i] = read(), a[i].change = read();
	a[++n].date = 0, a[n].bh = 0, a[n].change = 0;
	std::sort(lsh + 1, lsh + n + 1);
	int tot = unique(lsh + 1, lsh + n + 1) - (lsh + 1);
	for(int i = 1; i <= n; i++) a[i].bh = std::lower_bound(lsh + 1, lsh + tot + 1, a[i].bh) - lsh;
	sort(a + 1, a + n + 1);
//	for(int i = 1; i <= n; i++) printf("%d %d %d\n", a[i].date, a[i].bh, a[i].change);
	Seg::build(1, 1, tot);
//	printf("%d %d %d %d %d\n", tree[1].l, tree[1].r, tree[1].max, tree[1].cnt, tree[1].rk);
	for(register int i = 2; i <= n; i++) {
		int Rk = tree[1].rk, num = tree[1].cnt;
		change(1, a[i].bh, a[i].change);
		if(tree[1].rk != Rk) ans++;
		else if(tree[1].cnt != num) ans++;
	}
	cout << ans;
	return 0;
}
2022/7/13 15:10
加载中...