QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473058#1272. Dynamic Convex Hullgrass8cowWA 585ms76728kbC++172.1kb2024-07-11 21:31:252024-07-11 21:31:27

Judging History

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

  • [2024-07-11 21:31:27]
  • 评测
  • 测评结果:WA
  • 用时:585ms
  • 内存:76728kb
  • [2024-07-11 21:31:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
int L[200100],R[201000];
#define ll long long
#define fi first
#define se second
ll a[200010],b[201000],ans[101000],X[100100];
#define pi pair<ll,ll>
#define pb push_back
vector<pi>g[400100],g2[401000];
void up(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){g[p].pb({a[z],b[z]});return;}
    int mi=(l+r)>>1;
    if(x<=mi)up(p<<1,l,mi,x,y,z);
    if(y>mi)up(p<<1|1,mi+1,r,x,y,z);
}
void up2(int p,int l,int r,int x){
    g2[p].pb({X[x],1ll*x});if(l==r)return;int mi=(l+r)>>1;
    if(x<=mi)up2(p<<1,l,mi,x);
    else up2(p<<1|1,mi+1,r,x);
}
ll p4(ll x){
    return x*x*x*x;
}
const ll INF=4e18;
ll F(pi a,ll x){
    return p4(a.fi-x)+a.se;
}
void cdq(int pl,int pr,int l,int r,vector<pi>&a,vector<pi>&b){
    if(pl>pr||l>r)return;
    int mi=(l+r)>>1,jr=-1;ll nf=INF;
    for(int i=pl;i<=pr;i++){
        if(a[i].fi>b[mi].fi)break;
        ll fe=F(a[i],b[mi].fi);
        if(nf>fe)nf=fe,jr=i;
    }
    //assert(jr!=-1);
    ans[b[mi].se]=min(ans[b[mi].se],nf);
    cdq(pl,jr,l,mi-1,a,b),cdq(jr,pr,mi+1,r,a,b);
}
void sol(vector<pi>&a,vector<pi>&b){
    sort(a.begin(),a.end());sort(b.begin(),b.end());
    int z=0;while(z<b.size()&&b[z].fi<a[0].fi)z++;
    if(z==b.size())return;
    cdq(0,a.size()-1,z,b.size()-1,a,b);
}
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),L[i]=1,R[i]=m;
    for(int i=1;i<=m*4;i++)g[i].clear(),g2[i].clear();
    for(int i=1,op;i<=m;i++){
        scanf("%d",&op);
        X[i]=0;
        if(op==1){n++;scanf("%lld%lld",&a[n],&b[n]);L[n]=i,R[n]=m;}
        if(op==2){int x;scanf("%d",&x);R[x]=i;}
        if(op==3)scanf("%lld",&X[i]),up2(1,1,m,i),ans[i]=INF;
    }
    for(int i=1;i<=n;i++)up(1,1,m,L[i],R[i],i);
    for(int p=1;p<=m*4;p++)if(!g[p].empty()&&!g2[p].empty()){
        sol(g[p],g2[p]);
        for(pi &a:g[p])a.fi=-a.fi;
        for(pi &b:g2[p])b.fi=-b.fi;
        sol(g[p],g2[p]);
    }
    for(int i=1;i<=m;i++)if(X[i]){
        if(ans[i]==INF)puts("-1");
        else printf("%lld\n",ans[i]);
    }
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 27892kb

input:

1
2 8
3 9
6 100
3 4
2 1
3 4
1 1 1
3 4
2 2
2 3
3 4

output:

10
116
82
-1

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 585ms
memory: 76728kb

input:

5
100000 100000
39858 403048304064108142
6205 947055477496917683
788 911049878617783635
4261 626046370039242987
25008 685663359245704160
2202 848160200813297060
6216 289413959649340862
13189 722639235230562920
14820 749131972848517338
40221 716370580825502902
43025 222416883111096081
239 67541747335...

output:

105232514047244
112754306318445
54986177051691
74963972949549
118945174103964
69834459127665
33854058398778
275290771453117
65113537128811
45299248387930
51716327598553
68877950911521
135565157115804
288717635366668
10159612877616
161717641191962
161420883029513
72741135915164
109027638283771
179113...

result:

wrong answer 2396th lines differ - expected: '30790702249495', found: '28770951188769'