QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #419508 | #8718. 保区间最小值一次回归问题 | forget-star | WA | 1066ms | 73172kb | C++14 | 4.2kb | 2024-05-24 00:18:27 | 2024-05-24 00:18:29 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<deque>
#include<stack>
#include<unordered_map>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=5e5+10;
struct node
{
int l,r,v;
}q[N];
int n,m,a[N],b[N],tr[N<<2],laz[N<<2];
void build(int k,int l,int r)
{
if(l==r)
{
tr[k]=laz[k]=0;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tr[k]=laz[k]=0;
return;
}
void modify(int k,int l,int r,int al,int ar,int v)
{
if(al<=l&&r<=ar)
{
laz[k]=max(laz[k],v);
return;
}
int mid=(l+r)>>1;
if(al<=mid) modify(k<<1,l,mid,al,ar,v);
if(ar>=(mid+1)) modify(k<<1|1,mid+1,r,al,ar,v);
return;
}
int query(int k,int l,int r,int x)
{
if(l==r) return laz[k];
int mid=(l+r)>>1,res=laz[k];
if(x<=mid) res=max(res,query(k<<1,l,mid,x));
else res=max(res,query(k<<1|1,mid+1,r,x));
return res;
}
void build1(int k,int l,int r)
{
if(l==r)
{
tr[k]=b[l];
return;
}
int mid=(l+r)>>1;
build1(k<<1,l,mid);
build1(k<<1|1,mid+1,r);
tr[k]=min(tr[k<<1],tr[k<<1|1]);
return;
}
int query1(int k,int l,int r,int al,int ar)
{
if(al<=l&&r<=ar) return tr[k];
int mid=(l+r)>>1,res=1e9;
if(al<=mid) res=min(res,query1(k<<1,l,mid,al,ar));
if(ar>=(mid+1)) res=min(res,query1(k<<1|1,mid+1,r,al,ar));
return res;
}
int lsh[N];
vector<int>p1[N],p2[N];
bool cmp(int a,int b){return q[a].r==q[b].r?q[a].l<q[b].l:q[a].r<q[b].r;}
ll TR[N<<2];
void build2(int k,int l,int r)
{
if(l==r)
{
TR[k]=1e18;
return;
}
int mid=(l+r)>>1;
build2(k<<1,l,mid);
build2(k<<1|1,mid+1,r);
TR[k]=1e18;
return;
}
void modify2(int k,int l,int r,int x,ll v)
{
if(l==r)
{
TR[k]=min(TR[k],v);
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify2(k<<1,l,mid,x,v);
else modify2(k<<1|1,mid+1,r,x,v);
TR[k]=min(TR[k<<1],TR[k<<1|1]);
return;
}
ll query2(int k,int l,int r,int al,int ar)
{
if(al<=l&&r<=ar) return TR[k];
int mid=(l+r)>>1;ll res=1e18;
if(al<=mid) res=min(res,query2(k<<1,l,mid,al,ar));
if(ar>=(mid+1)) res=min(res,query2(k<<1|1,mid+1,r,al,ar));
return res;
}
void modify3(int k,int l,int r,int x)
{
if(l==r)
{
TR[k]=1e18;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify3(k<<1,l,mid,x);
else modify3(k<<1|1,mid+1,r,x);
TR[k]=min(TR[k<<1],TR[k<<1|1]);
return;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].v);
build(1,1,n);
for(int i=1;i<=m;i++)
modify(1,1,n,q[i].l,q[i].r,q[i].v);
for(int i=1;i<=n;i++) b[i]=query(1,1,n,i);
// for(int i=1;i<=n;i++) printf("b[%d]=%d ",i,b[i]);puts("");
build1(1,1,n);
bool check=1;
for(int i=1;i<=m;i++)
if(query1(1,1,n,q[i].l,q[i].r)!=q[i].v) check=0;
if(!check)
{
puts("-1");
continue;
}
ll ans=0;
for(int i=1;i<=n;i++) if(a[i]<b[i]) ans+=b[i]-a[i],a[i]=b[i];
for(int i=1;i<=m;i++) lsh[i]=q[i].v;
sort(lsh+1,lsh+m+1);int m1=unique(lsh+1,lsh+m+1)-lsh-1;
for(int i=1;i<=n;i++) b[i]=lower_bound(lsh+1,lsh+m1+1,b[i])-lsh;
for(int i=1;i<=m;i++) q[i].v=lower_bound(lsh+1,lsh+m1+1,q[i].v)-lsh;
for(int i=1;i<=m1;i++) p1[i].clear(),p2[i].clear();
for(int i=1;i<=n;i++) p1[b[i]].push_back(i);
for(int i=1;i<=m;i++) p2[q[i].v].push_back(i);
build2(1,1,n);
for(int i=1;i<=m1;i++)
{
sort(p2[i].begin(),p2[i].end(),cmp);
for(int j=0,k=0;j<p2[i].size();j++)
{
int tk=k;
while(k<p1[i].size()&&p1[i][k]<=q[p2[i][j]].r) k++;
// printf("l=%d r=%d\n",tk,k-1);
if(j==0)
{
for(int k1=tk;k1<=k-1;k1++)
{
modify2(1,1,n,p1[i][k1],a[p1[i][k1]]-lsh[i]);
// printf("x=%d d=%d\n",p1[i][k1],a[p1[i][k1]]-lsh[i]);
}
}
else
{
ll op=query2(1,1,n,q[p2[i][j-1]].l,q[p2[i][j-1]].r);
for(int k1=tk;k1<=k-1;k1++) modify2(1,1,n,p1[i][k1],op+a[p1[i][k1]]-lsh[b[p1[i][k1]]]);
}
if(j==(p2[i].size()-1)) ans+=query2(1,1,n,q[p2[i][j]].l,q[p2[i][j]].r);
}
for(int j=0;j<p1[i].size();j++) modify3(1,1,n,p1[i][j]);
}
printf("%lld\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 40748kb
input:
1 3 2 2023 40 41 1 1 2022 2 3 39
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: -100
Wrong Answer
time: 1066ms
memory: 73172kb
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:
49 45 40 39 47 47 48 46 46 47 45 56 950 53 50 54 46 61 56 46 47 50 42 55 51 57 50 43 41 43 41 53 57 45 59 45 47 43 37 48 42 51 45 50 877 945 47 50 49 50 45 40 53 52 42 46 55 51 51 48 37 48 43 41 55 41 48 47 36 51 54 46 44 47 46 47 42 48 40 45 44 35 43 45 53 45 48 45 41 45 47 40 47 54 44 43 44 47 48 ...
result:
wrong answer 2nd numbers differ - expected: '46', found: '45'