QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#672848	#8718. 保区间最小值一次回归问题	ucup-team4479	WA	315ms	24656kb	C++14	2.2kb	2024-10-24 19:30:05	2024-10-24 19:30:08

Judging History

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

[2024-10-24 19:30:08]
评测

测评结果：WA
用时：315ms
内存：24656kb

查看

[2024-10-24 19:30:05]
提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=500005;
constexpr long long INF=1e18;
int n,m;
int a[N];
struct Seg
{
    int l,r,v;
}s[N];
int pos[N],tot;
int nxt[N];
int getf(int v)
{
    if(v==nxt[v]) return v;
    else return nxt[v]=getf(nxt[v]);
}
int pre[N];
long long f[N];
long long solve(vector<pair<int,int>>seg,int v)
{
    tot=0;
    for(auto [l,r]:seg)
    {
        for(int x=getf(l);x<=r;x=nxt[x])
        {
            pos[++tot]=x;
            nxt[x]=getf(x+1);
        }
    }
    sort(pos+1,pos+tot+1);
    for(int i=1;i<=tot;i++)
        pre[i]=0;
    for(auto [l,r]:seg)
    {
        int ll=lower_bound(pos+1,pos+tot+1,l)-pos;
        int rr=upper_bound(pos+1,pos+tot+1,r)-pos-1;
        if(ll>rr) return INF;
        pre[rr]=max(pre[rr],ll);
    }
    int lst=0;
    f[0]=0;
    deque<int>q;
    q.emplace_back(0);
    for(int i=1;i<=tot;i++)
    {
        lst=max(lst,pre[i-1]);
        while(!q.empty()&&q.front()<lst) q.pop_front();
        if(!q.empty()) f[i]=f[q.front()]+abs(a[pos[i]]-v);
        else f[i]=INF;
        while(!q.empty()&&f[q.back()]<=f[i]) q.pop_back();
        q.emplace_back(i);
        if(a[pos[i]]<v) lst=i;
    }
    lst=max(lst,pre[tot]);
    long long res=INF;
    for(int i=lst;i<=tot;i++)
        res=min(res,f[i]);
    return res;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>s[i].l>>s[i].r>>s[i].v;
    for(int i=1;i<=n+1;i++)
        nxt[i]=i;
    sort(s+1,s+m+1,[](const Seg &x,const Seg &y){return x.v<y.v;});
    long long ans=0;
    for(int i=1,j=1;i<=m;i=j)
    {
        while(j<=m&&s[i].v==s[j].v) j++;
        vector<pair<int,int>>seg;
        for(int k=i;k<j;k++)
            seg.emplace_back(s[k].l,s[k].r);
        long long sum=solve(seg,s[i].v);
        if(sum>=INF)
        {
            cout<<-1<<"\n";
            return;
        }
        ans+=sum;
    }
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 11732kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: -100

Wrong Answer

time: 315ms

memory: 24656kb

input:

1000
100 100
1 35141686 84105222 84105220 7273527 178494861 178494861 112519027 77833654 77833656 261586535 278472336 278472336 261586536 416361017 416361017 426649080 323519513 278472337 420127821 420127823 420127823 482516531 434108818 420127821 631535744 615930922 546346921 546346920 546346920 70...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 1st numbers differ - expected: '49', found: '-1'