QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390188#3270. 魔塔 OLmarher0 0ms20636kbC++142.2kb2024-04-15 09:38:112024-04-15 09:38:11

Judging History

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

  • [2024-04-15 09:38:11]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:20636kb
  • [2024-04-15 09:38:11]
  • 提交

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]);
    }
    for(int i=1;i<=b[n];i++)bl[i].init();
    return 0;
    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';
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 20636kb

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
Memory Limit Exceeded

Test #33:

score: 0
Memory 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
Memory Limit Exceeded

Test #47:

score: 0
Memory 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%