QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121210#3270. 魔塔 OLzhouhuanyi0 2ms9728kbC++112.8kb2023-07-07 19:25:292023-07-07 19:25:32

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 19:25:32]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:9728kb
  • [2023-07-07 19:25:29]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 150000
#define M 10000
#define K 10
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int sgn(int x)
{
    if (x>0) return 1;
    else if (x==0) return 0;
    else return -1;
}
struct reads
{
    int x,y,z,a,b,num,snum,snum2;
    bool operator < (const reads &t)const
    {
	if (sgn(a)!=sgn(t.a)) return sgn(a)>sgn(t.a);
	else if (sgn(a)==1) return a-b<t.a-t.b;
	else return b>t.b;
    }
};
reads st[N+1];
bool cmp(reads a,reads b)
{
    return a.x<b.x;
}
bool cmp2(reads a,reads b)
{
    return a.y<b.y;
}
bool cmp3(reads a,reads b)
{
    return a.z<b.z;
}
bool cmp4(reads a,reads b)
{
    return a.num<b.num;
}
struct node
{
    long long a,b;
};
node dp[1<<K],ans[N+1];
node operator + (node x,node y)
{
    return (node){x.a+y.a,max(x.b+y.a,y.b)};
}
int Base=10,q,length,A[M+1],B[M+1],C[M+1],ps[N+1],X[N+1],Y[N+1],Z[N+1];
char c[N+1];
int main()
{
    int d,rst,res;
    q=read();
    for (int i=1;i<=q;++i)
    {
	cin>>c[i];
	if (c[i]=='+') ++length,st[length]=(reads){read(),read(),read(),read(),read(),0,i},swap(st[length].a,st[length].b),st[length].a=st[length].b-st[length].a;
	else if (c[i]=='-')  st[read()].snum2=i;
	else X[i]=read(),Y[i]=read(),Z[i]=read();
    }
    sort(st+1,st+length+1);
    for (int i=1;i<=length;++i) st[i].num=i,ps[st[i].snum]=ps[st[i].snum2]=i;
    sort(st+1,st+length+1,cmp);
    for (int i=1;i<=q;++i) X[i]=lower_bound(st+1,st+length+1,(reads){X[i]+1,0,0},cmp)-st-1;
    for (int i=1;i<=length;++i) st[i].x=i;
    sort(st+1,st+length+1,cmp2);
    for (int i=1;i<=q;++i) Y[i]=lower_bound(st+1,st+length+1,(reads){0,Y[i]+1,0},cmp2)-st-1;
    for (int i=1;i<=length;++i) st[i].y=i;
    sort(st+1,st+length+1,cmp3);
    for (int i=1;i<=q;++i) Z[i]=lower_bound(st+1,st+length+1,(reads){0,0,Z[i]+1},cmp3)-st-1;
    for (int i=1;i<=length;++i) st[i].z=i;
    sort(st+1,st+length+1,cmp4);
    for (int i=1;i<=length;i+=Base)
    {
	d=min(i+Base-1,length)-i+1;
	for (int j=0;j<(1<<d);++j)
	{
	    dp[j]=(node){0,0};
	    for (int k=1;k<=d;++k)
		if (j&(1<<(k-1)))
		    dp[j]=dp[j]+(node){st[i+k-1].a,st[i+k-1].b};
	}
	rst=0;
	for (int j=1;j<=M;++j) A[j]=B[j]=C[j]=0;
	for (int j=i;j<=min(i+Base-1,length);++j) A[st[j].x]|=(1<<(j-i)),B[st[j].y]|=(1<<(j-i)),C[st[j].z]|=(1<<(j-i));
	for (int j=2;j<=M;++j) A[j]|=A[j-1],B[j]|=B[j-1],C[j]|=C[j-1];
	for (int j=1;j<=q;++j)
	{
	    if (c[j]!='?'&&i<=ps[j]&&ps[j]<=min(i+Base-1,length)) rst^=(1<<(ps[j]-i));
	    else res=A[X[j]]&B[Y[j]]&C[Z[j]]&rst,ans[j]=ans[j]+dp[res];
	}
    }
    for (int i=1;i<=q;++i)
	if (c[i]=='?')
	    printf("%lld\n",max(ans[i].a,ans[i].b));
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

10
+ 2 1 1 3 4
+ 1 2 2 2 5
? 2 2 2
+ 1 1 1 8 2
? 2 2 1
? 1 2 2
- 1
? 2 2 2
- 3
? 1 2 2

output:

2
7
5
5
2

result:

ok 5 lines

Test #2:

score: -3
Wrong Answer
time: 2ms
memory: 7720kb

input:

24
+ 1753 1095 4823 848018166 5601858
+ 3635 2923 7293 78801729 4982097
+ 4314 6396 5125 589512425 8363663
? 8152 8403 6056
+ 9016 7943 8050 764333567 3409718
? 3516 8598 7385
? 1126 7574 1443
+ 2684 1515 2348 83534456 3012204
- 5
? 1861 8978 2163
- 4
? 480 2246 9251
- 1
+ 3844 6148 4596 110822346 7...

output:

1431928733
848018166
0
0
0
0
0
0

result:

wrong answer 1st lines differ - expected: '1429166928', found: '1431928733'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #24:

score: 0
Time Limit Exceeded

input:

150000
+ 588 392 1 640173034 0
? 7190 2026 1
? 8338 9467 1
+ 332 5522 1 648776911 0
? 650 9239 1
? 6609 1361 1
+ 6028 8919 1 315490561 0
+ 6129 3818 1 716541323 0
+ 2679 2249 1 94302018 0
? 4777 8851 1
+ 1382 186 1 295931805 0
+ 3956 7752 1 275694182 0
+ 6412 2498 1 363908456 0
+ 8317 3132 1 2800724...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #33:

score: 0
Time Limit Exceeded

input:

150000
? 5 2 1
+ 4 2 1 783649445 157723097
+ 3 4 1 281409092 43289613
+ 2 3 2 673972686 123253436
? 3 5 3
? 4 2 3
+ 5 5 2 534941804 768558960
+ 2 4 4 103433782 913423755
+ 1 2 3 99618767 608469807
+ 5 4 4 852574365 108454346
? 4 5 5
+ 1 2 4 647253960 383418735
+ 1 5 1 854207792 811999048
+ 4 2 4 995...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #47:

score: 0
Time Limit Exceeded

input:

150000
+ 9842 1 1 26088315 73696334
+ 2239 1 1 340356927 653719371
+ 349 1 1 632186088 849099938
? 908 1 1
+ 5153 1 1 487261860 697113681
? 984 1 1
+ 5694 1 1 800262114 571078829
? 1152 1 1
+ 3322 1 1 855670925 826813576
+ 8218 1 1 45843349 617723019
+ 3988 1 1 641119549 840483348
+ 3253 1 1 1654789...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

0%