QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121320#6718. Масив i частковi сумиzhouhuanyi49 6ms10372kbC++111.9kb2023-07-07 22:40:212023-07-07 22:40:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 22:40:22]
  • 评测
  • 测评结果:49
  • 用时:6ms
  • 内存:10372kb
  • [2023-07-07 22:40:21]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 200000
using namespace std;
int read()
{
    char c=0;
    int sum=0,f=1;
    while (c!='-'&&(c<'0'||c>'9')) c=getchar();
    if (c=='-') c=getchar(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum*f;
}
struct reads
{
    int op,l,r;
};
reads tong[N+1];
int n,g,length;
long long a[N+1],maxn=(long long)(1e18),minn;
__int128 s[N+1];
long long F(__int128 x)
{
    if (x>maxn) x=maxn;
    if (x<-maxn) x=-maxn;
    return x;
}
void solve(int op,int l,int r)
{
    if (op==1)
    {
	for (int i=1;i<=n;++i) a[i]=-a[i];
    }
    else if (op==2)
    {
	s[l]=a[l];
	for (int i=l+1;i<=r;++i) s[i]=s[i-1]+a[i];
	for (int i=l;i<=r;++i) a[i]=F(s[i]);
    }
    else
    {
	s[r]=a[r];
	for (int i=r-1;i>=l;--i) s[i]=s[i+1]+a[i];
	for (int i=l;i<=r;++i) a[i]=F(s[i]);
    }
    tong[++length]=(reads){op,l,r};
    return;
}
int main()
{
    int ps,res;
    bool op;
    n=read(),g=read();
    for (int i=1;i<=n;++i) a[i]=read();
    if (g==1)
    {
	op=1;
	for (int i=1;i<=n;++i) op&=(a[i]>=0);
	if (op) puts("0");
	else
	{
	    puts("1"),op=1;
	    for (int i=1;i<=n;++i) op&=(a[i]<=0);
	    if (op) puts("1");
	    else
	    {
		for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
		op=1;
		for (int i=1;i<=n;++i) op&=(s[i]>=0);
		if (op) printf("2 %d %d\n",1,n);
		else printf("3 %d %d\n",1,n);
	    }
	}
    }
    else
    {
	res=ps=0,minn=maxn;
        for (int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
	for (int i=0;i<=n;++i)
	    if (s[i]<minn)
		minn=s[i],ps=i;
	for (int i=1;i<=n;++i) res+=a[i];
	if (res>=0) solve(2,ps+1,n),solve(3,1,n);
	else solve(3,1,ps),solve(2,1,n),solve(1,0,0);
	printf("%d\n",length);
	for (int i=1;i<=length;++i)
	{
	    if (tong[i].op==1) puts("1");
	    else if (tong[i].op==2) printf("2 %d %d\n",tong[i].l,tong[i].r);
	    else printf("3 %d %d\n",tong[i].l,tong[i].r);
	}
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 3ms
memory: 7432kb

input:

200000 1
1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0...

output:

0

result:

ok OK: 0 operations

Test #2:

score: 0
Accepted
time: 5ms
memory: 7488kb

input:

200000 1
-1 0 0 0 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 -1 0 0 0 -1 -1 0 -1 0 -1 0 -1 0 -1 -1 0 0 -1 -1 0 0 -1 -1 0 -1 -1 -1 -1 0 -1 -1 0 0 0 -1 0 -1 -1 -1 0 -1 -1 0 0 0 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 0 -1 0 -1 -1 -1 0 -1 -1 0 0 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 -...

output:

1
1

result:

ok OK: 1 operations

Test #3:

score: 0
Accepted
time: 6ms
memory: 10260kb

input:

200000 1
0 0 1 -1 1 1 -1 -1 0 1 -1 0 0 1 0 0 1 1 1 1 0 -1 -1 0 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 1 0 -1 -1 0 1 0 0 0 0 1 1 -1 0 0 -1 -1 -1 0 0 0 1 1 1 -1 1 1 0 0 1 1 -1 1 0 0 1 1 1 1 -1 0 1 0 0 0 0 1 0 0 -1 0 -1 1 -1 0 1 -1 -1 0 0 0 -1 0 0 1 1 1 0 -1 0 1 1 1 0 1 0 0 0 -1 -1 0 -1 -1 1 -1 -1 1 1 0 1 1 1 -1...

output:

1
2 1 200000

result:

ok OK: 1 operations

Test #4:

score: 0
Accepted
time: 2ms
memory: 8496kb

input:

200000 1
-1 -1 -1 -1 0 1 0 -1 -1 0 -1 -1 1 0 0 -1 0 1 -1 0 -1 1 -1 0 1 1 0 1 1 1 0 0 1 -1 0 1 0 0 0 0 1 1 1 1 1 0 1 -1 1 1 0 -1 0 1 0 0 0 1 1 0 1 0 -1 -1 0 0 -1 -1 0 1 -1 -1 -1 0 1 0 0 -1 0 1 0 1 1 1 1 0 1 -1 -1 -1 0 0 0 -1 1 1 -1 -1 -1 1 0 0 -1 -1 0 -1 -1 -1 0 1 1 1 1 0 1 -1 -1 0 -1 0 0 0 -1 -1 -1 ...

output:

1
3 1 200000

result:

ok OK: 1 operations

Subtask #2:

score: 17
Accepted

Test #5:

score: 17
Accepted
time: 2ms
memory: 8364kb

input:

200000 2
1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0...

output:

2
2 1 200000
3 1 200000

result:

ok OK: 2 operations

Test #6:

score: 0
Accepted
time: 6ms
memory: 8468kb

input:

200000 2
0 0 -1 -1 0 -1 0 0 -1 -1 0 -1 -1 0 -1 0 -1 -1 -1 -1 -1 0 0 -1 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 -1 -1 0 -1 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 -1 0 0 0 -1 -1 0 0 -1 -1 -1 0 -1 -1 0 -1 -1 -1 -1 0 -1 -1 -1 0 0 -1 0 0 0 -1 -1 -1 0 0 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 0 0 -1 -1...

output:

3
3 1 199999
2 1 200000
1

result:

ok OK: 3 operations

Test #7:

score: 0
Accepted
time: 6ms
memory: 8612kb

input:

200000 2
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

3
3 1 199999
2 1 200000
1

result:

ok OK: 3 operations

Test #8:

score: 0
Accepted
time: 4ms
memory: 8388kb

input:

200000 2
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

3
3 1 167932
2 1 200000
1

result:

ok OK: 3 operations

Test #9:

score: 0
Accepted
time: 3ms
memory: 9448kb

input:

200000 2
1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 -1 0 0 0 0 -1 0 -1 0 -1 0 0 0 0 -1 0 0 0 -1 0 0 0 -1 0 -1 0 0 0 0 0 0 0 -1 -1 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 1 0 0 -1 0 -1 0 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 -1 0 -1 0 0 0 0 0 0 ...

output:

3
3 1 199995
2 1 200000
1

result:

ok OK: 3 operations

Test #10:

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

input:

200000 2
-1 0 1 -1 0 1 1 0 1 0 0 1 0 1 -1 1 1 -1 1 -1 -1 0 -1 -1 0 -1 0 0 0 1 1 0 -1 1 -1 0 1 0 1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 0 1 -1 0 -1 1 -1 0 -1 1 -1 0 1 1 1 0 -1 0 -1 -1 -1 -1 0 0 -1 1 -1 -1 0 1 -1 0 0 0 0 0 0 1 1 1 0 -1 0 -1 1 -1 1 -1 1 1 0 0 1 1 -1 1 1 -1 -1 1 0 -1 1 -1 0 0 0 -1 0 0 1 1 -1 ...

output:

3
3 1 154811
2 1 200000
1

result:

ok OK: 3 operations

Subtask #3:

score: 18
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 18
Accepted
time: 5ms
memory: 10152kb

input:

200000 3
0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 0...

output:

2
2 1 200000
3 1 200000

result:

ok OK: 2 operations

Test #12:

score: 0
Accepted
time: 6ms
memory: 10064kb

input:

200000 3
0 -1 0 -1 -1 -1 0 0 -1 0 -1 -1 0 0 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 -1 -1 0 0 -1 0 0 0 -1 -1 0 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 -1 -1 -1 -1 0 -1 -1 0 0 0 -1 -1 -1 0 -1 -1 0 -1 0 -1 -1 -1 0 -1 0 -1 -1 0 -1 0 0 0 -1 -1 -1 -1 0 0 -1 -1 0 0 0 -1 0 0 -1 -1 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0 -1 -1 0 -1...

output:

3
3 1 199998
2 1 200000
1

result:

ok OK: 3 operations

Test #13:

score: 0
Accepted
time: 6ms
memory: 8696kb

input:

200000 3
-1 -1 -1 -1 1 -1 0 1 -1 0 -1 -1 -1 1 1 0 -1 0 1 -1 1 0 -1 0 0 1 -1 0 -1 0 0 -1 1 -1 1 1 -1 -1 0 -1 1 1 0 0 1 0 1 1 1 -1 0 -1 0 1 1 1 -1 -1 -1 1 -1 0 -1 0 1 -1 1 -1 -1 -1 1 0 1 1 -1 0 0 -1 1 -1 1 1 1 1 0 -1 1 -1 0 -1 -1 1 0 0 1 -1 1 -1 0 1 0 0 0 1 0 -1 -1 1 -1 -1 0 1 -1 1 1 0 0 1 0 1 0 1 1 -...

output:

2
2 20910 200000
3 1 200000

result:

ok OK: 2 operations

Test #14:

score: 0
Accepted
time: 6ms
memory: 10068kb

input:

193638 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1...

output:

3
3 1 193637
2 1 193638
1

result:

ok OK: 3 operations

Test #15:

score: 0
Accepted
time: 3ms
memory: 8800kb

input:

200000 3
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

3
3 1 199999
2 1 200000
1

result:

ok OK: 3 operations

Test #16:

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

input:

200000 3
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1...

output:

3
3 1 199999
2 1 200000
1

result:

ok OK: 3 operations

Test #17:

score: 0
Accepted
time: 6ms
memory: 9316kb

input:

200000 3
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...

output:

3
3 1 168773
2 1 200000
1

result:

ok OK: 3 operations

Test #18:

score: 0
Accepted
time: 6ms
memory: 9440kb

input:

200000 3
1 1 1 0 0 0 0 0 0 0 -1 0 0 0 1 0 0 0 -1 0 -1 0 0 -1 0 -1 0 0 -1 0 0 0 0 0 -1 0 0 -1 0 0 -1 0 0 0 0 -1 0 -1 0 -1 0 -1 0 0 0 -1 0 0 1 0 0 0 1 0 0 0 0 0 0 -1 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 -1 0 0 0 -1 -1 0 0 0 -1 0 0 0 -1 0 0 0 0 0 -1 1 0 0 0 -1 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0...

output:

3
3 1 199994
2 1 200000
1

result:

ok OK: 3 operations

Test #19:

score: 0
Accepted
time: 6ms
memory: 8892kb

input:

200000 3
0 -1 1 1 0 0 0 1 -1 0 1 0 -1 -1 1 -1 -1 0 -1 -1 -1 0 0 1 0 0 0 -1 0 1 -1 -1 0 0 1 1 1 0 -1 1 1 0 -1 0 -1 0 1 0 1 0 0 -1 -1 -1 0 1 -1 0 1 -1 0 0 0 0 1 0 1 1 0 -1 0 1 0 1 1 -1 -1 -1 0 0 1 0 0 -1 0 -1 1 0 0 -1 1 1 1 0 0 0 1 -1 1 -1 0 -1 1 -1 1 0 -1 1 -1 0 1 -1 1 -1 0 0 0 0 -1 1 0 1 0 -1 -1 1 -...

output:

2
2 23840 200000
3 1 200000

result:

ok OK: 2 operations

Subtask #4:

score: 0
Wrong Answer

Dependency #3:

100%
Accepted

Test #20:

score: 0
Wrong Answer
time: 2ms
memory: 9288kb

input:

200000 4
1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1 0...

output:

2
2 1 200000
3 1 200000

result:

wrong answer Too many operations

Subtask #5:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 1ms
memory: 7648kb

input:

2891 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 ...

output:

3
3 1 2890
2 1 2891
1

result:

wrong answer Too many operations

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #5:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%