QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390189 | #3270. 魔塔 OL | marher | 0 | 78ms | 107596kb | C++14 | 2.2kb | 2024-04-15 09:38:32 | 2024-04-15 09:38:33 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+50,M=1e4+50;
struct ask
{
char opt;int x,y,z;
}Q[N];
int n,q,m=1e4,w[N],c[N],mb[N],B=12,x[N],y[N],z[N],dfn[N],p[N],b[N];
struct node
{
ll mi,now;
};
struct block
{
vector<int>a;
int px[M],py[M],pz[M],n,now;
node f[M];
void init()
{
n=a.size();
for(int i=0;i<n;i++)px[x[a[i]]]|=(1<<i),py[y[a[i]]]|=(1<<i),pz[z[a[i]]]|=(1<<i);
for(int i=1;i<=m;i++)px[i]|=px[i-1],py[i]|=py[i-1],pz[i]|=pz[i-1];
for(int i=1;i<(1<<n);i++)
{
int x=mb[i];f[i]=f[i^(1<<x)];
x=a[x];f[i].mi=min(f[i].mi,f[i].now-c[x]);f[i].now+=w[x]-c[x];
}
}
node find(int x,int y,int z)
{
return f[px[x]&py[y]&pz[z]&now];
}
void ex(int x)
{
for(int i=0;i<n;i++)if(a[i]==x)
{
now^=(1<<i);
return;
}
}
}bl[M*5/12+10];
int cmp(int a,int b)
{
if((w[a]>=c[a])!=(w[b]>=c[b]))return w[a]>=c[a];
if(w[a]>=c[a])return c[a]<=c[b];
return w[a]>=w[b];
}
main()
{
// freopen("in.txt","r",stdin);
for(int i=1;i<=(1<<B);i++)for(int j=0;j<B;j++)if((i>>j)&1)mb[i]=j;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>Q[i].opt;
if(Q[i].opt=='+')
{
++n;p[n]=n;Q[i].x=n;
cin>>x[n]>>y[n]>>z[n]>>c[n]>>w[n];
}
if(Q[i].opt=='-')cin>>Q[i].x;
if(Q[i].opt=='?')cin>>Q[i].x>>Q[i].y>>Q[i].z;
}
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++)
{
dfn[p[i]]=i;b[i]=(i-1)/B+1;
bl[b[i]].a.push_back(p[i]);
}
return 0;
for(int i=1;i<=b[n];i++)bl[i].init();
for(int i=1;i<=q;i++)
{
if(Q[i].opt!='?')
{
bl[b[dfn[Q[i].x]]].ex(Q[i].x);
continue;
}
ll ans=0,now=0;
for(int j=1;j<=b[n];j++)
{
node p=bl[j].find(Q[i].x,Q[i].y,Q[i].z);
if(now+p.mi<0)ans+=-(now+p.mi),now=-p.mi;
now+=p.now;
}
cout<<ans<<'\n';
}
// cout<<bl[1].n<<' '<<bl[1].now<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 105392kb
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:
result:
wrong answer 1st lines differ - expected: '2', found: ''
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #24:
score: 0
Runtime Error
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
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 66ms
memory: 107596kb
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:
wrong answer 1st lines differ - expected: '0', found: ''
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 78ms
memory: 99448kb
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:
wrong answer 1st lines differ - expected: '632186088', found: ''
Subtask #6:
score: 0
Skipped
Dependency #1:
0%