QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419508#8718. 保区间最小值一次回归问题forget-starWA 1066ms73172kbC++144.2kb2024-05-24 00:18:272024-05-24 00:18:29

Judging History

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

  • [2024-05-24 00:18:29]
  • 评测
  • 测评结果：WA
  • 用时：1066ms
  • 内存：73172kb
查看
  • [2024-05-24 00:18:27]
  • 提交

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;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

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'
English 繁體中文 简体中文

Server Time: 2025-01-20 20:03:29 | OpenSource Project