QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121220 | #3270. 魔塔 OL | zhouhuanyi | 0 | 1ms | 11780kb | C++11 | 2.9kb | 2023-07-07 19:37:58 | 2023-07-07 19:38:00 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 150000
#define M 10000
#define K 20
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=14,q,length,lw[1<<K],lws[1<<K],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,pst;
for (int i=0;i<(1<<Base);++i)
for (int j=0;j<Base;++j)
if (i&(1<<j))
{
lw[i]=j,lws[j]=1<<j;
break;
}
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=1;j<(1<<d);++j) pst=i+lw[j]-1,dp[j]=dp[j-lws[j]]+(node){st[pst].a,st[pst].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: 0
Wrong Answer
time: 1ms
memory: 11780kb
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:
8 0 0 0 3
result:
wrong answer 1st lines differ - expected: '2', found: '8'
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%