?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
229693639 |
Practice: chenyifanlx |
780G - 17 | C++17 (GCC 9-64) | Accepted | 202 ms | 18196 KB | 2023-10-25 15:56:05 | 2023-10-25 15:56:05 |
// LUOGU_RID: 131588942 #include<bits/stdc++.h> #define ri register LL using namespace std; typedef long long LL; inline LL rd(){ LL x=0,y=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1; for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48); return x*y; } const LL p=1000000007; LL n,m,h,mn[400005],an;priority_queue<pair<LL,LL> >q[100005]; struct nd{LL u,l,r,s;}a[100005]; bool cmp(nd p,nd q){return p.u>q.u;} void bd(LL rt,LL l,LL r){ mn[rt]=h+1;if(l==r){q[l].push({-(h+1),1});return;}ri md=l+r>>1; bd(rt<<1,l,md);bd(rt<<1|1,md+1,r); } void upd(LL rt,LL l,LL r,LL x,LL y,LL z){ if(l==r){q[l].push({-y,z});mn[rt]=min(mn[rt],y);return;}ri md=l+r>>1; if(x<=md)upd(rt<<1,l,md,x,y,z);else upd(rt<<1|1,md+1,r,x,y,z);mn[rt]=min(mn[rt<<1],mn[rt<<1|1]); } LL qr(LL rt,LL l,LL r,LL x,LL y,LL z){ if(mn[rt]>z)return 0; if(l==r){ ri o=0;while(q[l].size()&&-q[l].top().first<=z)(o+=q[l].top().second)%=p,q[l].pop(); mn[rt]=q[l].size()?-q[l].top().first:2e9+1;return o; } ri md=l+r>>1,o=((x<=md?qr(rt<<1,l,md,x,y,z):0)+(y>md?qr(rt<<1|1,md+1,r,x,y,z):0))%p; mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);return o; } int main(){ h=rd();n=rd();m=rd(); for(ri i=1;i<=m;++i)a[i].u=rd(),a[i].l=rd(),a[i].r=rd(),a[i].s=rd(); sort(a+1,a+1+m,cmp);bd(1,1,n); for(ri i=1;i<=m;++i){ ri o=qr(1,1,n,a[i].l,a[i].r,min(h+1,a[i].u+a[i].s)); if(a[i].l==1)upd(1,1,n,a[i].r+1,a[i].u,2*o%p); else if(a[i].r==n)upd(1,1,n,a[i].l-1,a[i].u,2*o%p); else upd(1,1,n,a[i].l-1,a[i].u,o),upd(1,1,n,a[i].r+1,a[i].u,o); } for(ri i=1;i<=n;++i)while(q[i].size())(an+=q[i].top().second)%=p,q[i].pop();cout<<an;return 0; }
?
?
?
?