QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140794#6733. Moniphant SleepA_zjzjTL 8ms129548kbC++141.9kb2023-08-16 20:29:132023-09-05 22:11:06

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 22:11:06]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:8ms
  • 内存:129548kb
  • [2023-08-16 20:29:15]
  • 评测
  • 测评结果:0
  • 用时:16ms
  • 内存:130448kb
  • [2023-08-16 20:29:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10,M=4;
struct matrix{
	int a[M][M];
	matrix(){
		memset(a,0,sizeof a);
	}
	matrix operator * (const matrix &x)const{
		matrix b;
		for(int k=0;k<M;k++)
			for(int i=0;i<=k;i++)
				for(int j=k;j<M;j++)
					b.a[i][j]+=a[i][k]*x.a[k][j];
		return b;
	}
}base,T[5];
struct vec{
	int a[M];
	vec(){
		memset(a,0,sizeof a);
	}
	vec operator * (const matrix &x)const{
		vec b;
		for(int i=0;i<M;i++)
			for(int j=i;j<M;j++)
				b.a[j]+=a[i]*x.a[i][j];
		return b;
	}
}ans;
int n,m;
bool laz[N<<2];
matrix t[N<<2];
void pushadd(int rt,matrix x){
	t[rt]=t[rt]*x,laz[rt]=1;
}
void pushdown(int rt){
	if(laz[rt]){
		pushadd(rt<<1,t[rt]);
		pushadd(rt<<1|1,t[rt]);
		t[rt]=base,laz[rt]=0;
	}
}
void build(int l=1,int r=n,int rt=1){
	t[rt]=base;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
void update(int L,int R,matrix x,int l=1,int r=n,int rt=1){
	if(L<=l&&r<=R)return pushadd(rt,x);
	int mid=(l+r)>>1;
	pushdown(rt);
	if(L<=mid)update(L,R,x,l,mid,rt<<1);
	if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
}
void query(int x,int l=1,int r=n,int rt=1){
	if(l==r){
		printf("%d\n",(ans*t[rt]).a[3]);
		return;
	}
	int mid=(l+r)>>1;
	pushdown(rt);
	if(x<=mid)query(x,l,mid,rt<<1);
	else query(x,mid+1,r,rt<<1|1);
}
void read(int &x){
	char c;
	for(x=0;!isdigit(c=getchar()););
	for(;x=(x<<3)+(x<<1)+(c^48),isdigit(c=getchar()););
}
int main(){
	read(n),read(m);
	ans.a[0]=1,ans.a[3]=5e5;
	for(int i=0;i<M;i++)base.a[i][i]=1;
	build();
	for(int i=1;i<=4;i++)T[i].a[0][0]=1;
	T[1].a[1][1]=T[1].a[1][2]=T[1].a[2][2]=T[1].a[3][3]=T[1].a[0][3]=1;
	T[2].a[0][3]=-1,T[2].a[3][3]=1;
	T[3].a[0][1]=T[3].a[2][2]=T[3].a[3][3]=1;
	T[4].a[2][3]=-1,T[4].a[3][3]=1;
	for(int op,l,r;m--;){
		read(op),read(l),read(r);
		if(op<=4)update(l,r,T[op]);
		else query(l);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 129548kb

input:

1 9
1 1 1
1 1 1
1 1 1
3 1 1
2 1 1
1 1 1
1 1 1
4 1 1
5 1 1

output:

500004

result:

ok 1 number(s): "500004"

Test #2:

score: 0
Accepted
time: 0ms
memory: 129080kb

input:

3 7
2 1 3
3 1 3
1 1 3
1 1 3
5 1 1
4 1 3
5 1 1

output:

500001
499999

result:

ok 2 number(s): "500001 499999"

Test #3:

score: -100
Time Limit Exceeded

input:

500000 500000
2 132991 371170
5 15281 15281
1 278642 397098
2 152103 176573
2 13797 47775
3 139320 370045
3 79054 432340
3 82556 212775
4 270171 469418
5 148000 148000
3 371255 401414
5 71051 71051
2 358945 473071
2 231663 265401
2 20243 58131
1 247710 313373
5 154549 154549
1 17317 233265
5 37602 3...

output:

500000
499999
500000
499998
499999
500000
500000
499997
500000
499997
499997
499999
499998
500000
499997
500000
499999
500001
499999
499999
499997
499998
499997
499998
500000
500001
500001
499996
499998
500000
499998
499999
500001
500005
500003
500002
500002
500000
500001
499998
500000
499999
500004...

result: