| 比赛 |
2026.5.30 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
雨和卡布奇诺 |
最终得分 |
100 |
| 用户昵称 |
djyqjy |
运行时间 |
1.399 s |
| 代码语言 |
C++ |
内存使用 |
27.66 MiB |
| 提交时间 |
2026-05-30 09:46:52 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=300010;
int n,m;
vector<int> ys;
vector<pir> g[N],spn[N],spc[N],t;
int nt[N];
int p[N];
int c[N];
int ans;
bool mk[N];
void add(int now)
{
if(mk[now]) return;
ans++;
mk[now]=1;
for(pir tmp:spc[now])
{
nt[tmp.fi]+=tmp.se;
while(p[tmp.fi]!=g[tmp.fi].size()-1&&g[tmp.fi][p[tmp.fi]+1].fi<=nt[tmp.fi])
{
p[tmp.fi]++;
int nxt=g[tmp.fi][p[tmp.fi]].se;
c[nxt]--;
if(c[nxt]==0) add(nxt);
}
}
return;
}
signed main()
{
freopen("Cappuccino.in","r",stdin);
freopen("Cappuccino.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
pir tmp;
scanf("%lld%lld",&tmp.fi,&tmp.se);
t.pb(tmp);
ys.pb(tmp.fi);
}
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
int l;
scanf("%lld",&l);
for(int j=1;j<=l;j++)
{
pir tmp;
scanf("%lld%lld",&tmp.fi,&tmp.se);
spn[i].pb(tmp);
ys.pb(tmp.fi);
}
int k;
scanf("%lld",&k);
for(int j=1;j<=k;j++)
{
pir tmp;
scanf("%lld%lld",&tmp.fi,&tmp.se);
spc[i].pb(tmp);
ys.pb(tmp.fi);
}
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
for(int i=1;i<=m;i++)
{
for(int j=0;j<spn[i].size();j++) spn[i][j].fi=lower_bound(ys.begin(),ys.end(),spn[i][j].fi)-ys.begin()+1;
for(int j=0;j<spc[i].size();j++) spc[i][j].fi=lower_bound(ys.begin(),ys.end(),spc[i][j].fi)-ys.begin()+1;
}
for(int i=1;i<=m;i++)
{
c[i]=spn[i].size();
for(pir tmp:spn[i]) g[tmp.fi].pb(mp(tmp.se,i));
}
for(int i=1;i<=ys.size();i++)
{
sort(g[i].begin(),g[i].end());
p[i]=-1;
}
for(int i=1;i<=m;i++) if(c[i]==0) add(i);
for(pir tmp:t)
{
tmp.fi=lower_bound(ys.begin(),ys.end(),tmp.fi)-ys.begin()+1;
nt[tmp.fi]+=tmp.se;
while(p[tmp.fi]!=g[tmp.fi].size()-1&&g[tmp.fi][p[tmp.fi]+1].fi<=nt[tmp.fi])
{
p[tmp.fi]++;
int now=g[tmp.fi][p[tmp.fi]].se;
c[now]--;
if(c[now]==0) add(now);
}
}
printf("%lld\n",ans);
return 0;
}