ODT TLE on #30
查看原帖
ODT TLE on #30
214728
剑雪清寒楼主2022/9/28 14:09

rt,第三十个点T了,是我实现有问题吗?

#include <bits/stdc++.h>
inline int read() {
	int x;bool f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
inline void print(int x,char las) {
	if(!x) {
		putchar(48),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[10],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ;
}
struct Node_t {
	int l,r;
	mutable int v;
	Node_t(const int&ll,const int&rr,const int&vv) : l(ll),r(rr),v(vv) {}
	inline bool operator<(const Node_t &ls) const {
		return l<ls.l;
	}
};
std::set<Node_t>odt;
int n=read(),m=read(),cnt=n;
inline auto split(int x) {
	if(x>n) return odt.end();
	auto it=--odt.upper_bound(Node_t(x,0,0));
	if(it->l==x) return it;
	int l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node_t(l,x-1,v));
	return odt.insert(Node_t(x,r,v)).first;
}
inline void assign(int l,int r,int x) {
	auto itr=split(r+1),itl=split(l);
	for(register auto it=itl;it!=itr;it++) cnt-=it->v*(it->r-it->l+1);
	odt.erase(itl,itr);
	cnt+=x*(r-l+1);
	odt.insert(Node_t(l,r,x));
}
std::bitset<1001>in;
signed main() {
	odt.insert(Node_t(1,n,1));
	for(register int i=1;i<=m;i++) {
		int l=read(),r=read(),k=read();
		assign(l,r,k==1 ? 0 : 1);
		print(cnt,'\n');
	}
	return 0;
}

2022/9/28 14:09
加载中...