【悬山关注】TLE on #31
查看原帖
【悬山关注】TLE on #31
999274
CNS_5t0_0r2楼主2023/11/17 16:07
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
using namespace std;
const int N = 1e5 + 9;
int read(){
	char c = getchar();
	int x = 0;
	while(c < 48 || c > 57)
		c = getchar();
	while(c >= 48 && c <= 57){
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x;
}
int n,q;
struct node{
	int val,tag,lchild,rchild;
} tree[N << 7];
int cnt;
void push_up(int root){
	tree[root].val = tree[tree[root].lchild].val + tree[tree[root].rchild].val;
}
int len(int l,int r){
	return r - l + 1;
}
bool in_range(int l,int r,int now_l,int now_r){
	return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
	return now_r < l || now_l > r;
}
void make_tag(int root,int tag,int l,int r){
	tree[root].tag = tag;
	tree[root].val = tag * len(l,r);
}
void push_down(int root,int l,int r){
	if(tree[root].tag == -1)
		return;
	int mid = (l + r) >> 1;
	make_tag(tree[root].lchild,tree[root].tag,l,mid);
	make_tag(tree[root].rchild,tree[root].tag,mid + 1,r);
	tree[root].tag = -1;
}
void update(int root,int l,int r,int now_l,int now_r,int v){
	if(in_range(l,r,now_l,now_r)){
		make_tag(root,v,now_l,now_r);
		return;
	}
	int mid = (now_l + now_r) >> 1;
	if(!out_range(l,r,now_l,now_r)){
		if(!tree[root].lchild && !tree[root].rchild){
			tree[root].lchild = ++cnt;
			tree[root].rchild = ++cnt;
		}
		push_down(root,now_l,now_r);
		update(tree[root].lchild,l,r,now_l,mid,v);
		update(tree[root].rchild,l,r,mid + 1,now_r,v);
		push_up(root);
	}
}
int last_l,last_r,last_op = -1;
int main(){
	n = read();q = read();
	int root = ++cnt;
	tree[root].tag = 1;
	for(;q;q--){
		int l,r,op;
		l = read(),r = read(),op = read() - 1;
		if(in_range(last_l,last_r,l,r) && op == last_op){
			printf("%d\n",tree[root].val);
			continue;
		}
		update(root,l,r,1,n,op);
		printf("%d\n",tree[root].val);
		last_l = l;last_r = r;last_op = op;
	}
	return 0;
}
2023/11/17 16:07
加载中...