General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
165262296 Practice:
lndjy
780G - 17 C++20 (GCC 11-64) Accepted 389 ms 22668 KB 2022-07-22 07:20:01 2022-07-22 07:20:01
→ Source
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int mod=1000000007;
int h,w,n,to[100001][2],num[100005],maxh;
vector<int>t[400001];
struct ban
{
	int u,l,r,h;
}a[100001];
bool cmp(ban a,ban b)
{
	return a.u<b.u;
}
void add(int l,int r,int rt,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		t[rt].push_back(k);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)add(l,mid,rt<<1,L,R,k);
	if(R>mid)add(mid+1,r,rt<<1|1,L,R,k);
}
int ask(int l,int r,int rt,int x)
{
	while(t[rt].size()&&a[t[rt].back()].h<maxh)t[rt].pop_back();
	int now=t[rt].size()?t[rt].back():0;
	if(l==r)return now;
	int mid=(l+r)>>1;
	if(x<=mid)return max(now,ask(l,mid,rt<<1,x));
	else return max(now,ask(mid+1,r,rt<<1|1,x));
}
int main()
{
// 	freopen("fall.in","r",stdin);
// 	freopen("fall.out","w",stdout);
	scanf("%d%d%d",&h,&w,&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].u,&a[i].l,&a[i].r,&a[i].h),a[i].h+=a[i].u;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		maxh=a[i].u;
		if(a[i].l==1&&a[i].r==w)
		to[i][0]=to[i][1]=n+1;
		else if(a[i].l==1)
		to[i][0]=to[i][1]=ask(1,w,1,a[i].r+1);
		else if(a[i].r==w)
		to[i][0]=to[i][1]=ask(1,w,1,a[i].l-1);
		else to[i][0]=ask(1,w,1,a[i].l-1),to[i][1]=ask(1,w,1,a[i].r+1);
		add(1,w,1,a[i].l,a[i].r,i);
//		printf("(%d %d)",to[i][0],to[i][1]);
	}
	maxh=h+1;
	for(int i=1;i<=w;i++)num[ask(1,w,1,i)]++;
	for(int i=n;i;i--)
		num[to[i][0]]=(num[to[i][0]]+num[i])%mod,num[to[i][1]]=(num[to[i][1]]+num[i])%mod;
	printf("%d",num[0]);
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details