Submission #204193

#	Time	Username	Problem	Language	Result	Execution time	Memory
204193		kig9981	Fire (JOI20_ho_t5)	C++17	7 / 100	1097 ms	15352 KiB

ho_t5

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct Splay
{
	int p, l, r, v, cnt;
	long long sum;
	bool inv;
	Splay() : p(0), l(0), r(0), v(0), cnt(1), sum(0), inv(false) {}
} tree[200003];

vector<tuple<int,int,int,int>> Q;
vector<int> C, T;
int root, color[200001];
long long ans[200000];

int find_(int a)
{
	return color[a]=a==color[a] ? a:find_(color[a]);
}

void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	color[a]=color[b]=max(a,b);
}

void lazy(int c)
{
	if(tree[c].inv) {
		swap(tree[c].l,tree[c].r);
		if(tree[c].l) tree[tree[c].l].inv^=1;
		if(tree[c].r) tree[tree[c].r].inv^=1;
		tree[c].inv=false;
	}
}

void update(int c)
{
	tree[c].cnt=tree[tree[c].l].cnt+tree[tree[c].r].cnt+1;
	tree[c].sum=tree[tree[c].l].sum+tree[tree[c].r].sum+tree[c].v;
}

void rotate(int c)
{
	int p=tree[c].p;
	if(tree[p].l==c) {
		if(tree[c].r) tree[tree[c].r].p=p;
		tree[p].l=tree[c].r;
		tree[c].r=p;
	}
	else {
		if(tree[c].l) tree[tree[c].l].p=p;
		tree[p].r=tree[c].l;
		tree[c].l=p;
	}
	if(tree[p].p) (tree[tree[p].p].l==p ? tree[tree[p].p].l:tree[tree[p].p].r)=c;
	tree[c].p=tree[p].p;
	tree[p].p=c;
	update(p); update(c);
}

void splay(int c)
{
	while(tree[c].p) {
		int p=tree[c].p;
		if(tree[p].p) lazy(tree[p].p);
		lazy(p); lazy(c);
		if(tree[p].p) rotate((tree[tree[p].p].l==p)==(tree[p].l==c) ? p:c);
		rotate(c);
	}
	lazy(root=c);
}

int kth(int k)
{
	int c=root;
	for(;;) {
		lazy(c);
		if(tree[tree[c].l].cnt>k) {
			c=tree[c].l;
			continue;
		}
		k-=tree[tree[c].l].cnt;
		if(!k--) break;
		c=tree[c].r;
	}
	splay(c);
	return c;
}

int interval(int l, int r)
{
	int ret, temp;
	kth(l-1);
	temp=root;
	root=tree[root].r;
	tree[root].p=0;
	kth(r-l+1);
	tree[temp].r=root;
	ret=tree[root].l;
	tree[root].p=temp;
	update(root=temp);
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, j=0;
	cin>>N>>M; tree[0].cnt=0;
	for(int i=1;i<=N;i++) {
		cin>>tree[i+1].v;
		tree[i+1].l=i;
		tree[i].p=i+1;
		update(i+1);
		color[i]=i;
		if(tree[i].v>=tree[i+1].v) union_(i-1,i);
	}
	tree[N+2].l=N+1;
	root=tree[N+1].p=N+2;
	update(N+2);
	Q.resize(M);
	for(int i=0;i<M;i++) {
		auto &[t,l,r,idx]=Q[i];
		cin>>t>>l>>r; idx=i;
	}
	sort(Q.begin(),Q.end());
	for(int c=1;c<=N;c=find_(c)+1) {
		int n=find_(c), i, j;
		i=kth(c); j=kth(n);
		if(tree[i].v>tree[j].v) C.push_back(c);
	}
	for(int t=1;t<=N;t++) {
		for(auto c: C) {
			int n=find_(c), v, p;
			v=tree[kth(c)].v;
			tree[interval(c,n-1)].inv^=1;
			tree[interval(c,n)].inv^=1;
			tree[kth(c)].v=v;
			update(root);
			if(n<N) {
				p=kth(n); v=kth(n+1);
				if(tree[p].v>=tree[v].v) union_(n,n+1);
			}
		}
		T.clear();
		for(auto c: C) if(find_(c-1)!=find_(c) && tree[kth(c)].v>tree[kth(find_(c))].v) T.push_back(c);
		C=T;
		while(j<M && get<0>(Q[j])==t) {
			auto[t,l,r,idx]=Q[j++];
			ans[idx]=tree[interval(l,r)].sum;
		}
	}
	for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:164:18: warning: unused variable 't' [-Wunused-variable]
    auto[t,l,r,idx]=Q[j++];
                  ^

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 80