比赛 |
2024暑期C班集训1 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
雨和卡布奇诺 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
1.568 s |
代码语言 |
C++ |
内存使用 |
28.67 MiB |
提交时间 |
2024-07-01 09:05:30 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("Cappuccino.in");
ofstream fout("Cappuccino.out");
auto mread = [](){
int x;
fin >> x;
return x;
};
const int N = 1e5 + 5;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q[3 * N];
queue<int> q2;
int n = mread(), t[N], u[N], m, l[N], k[N], idx, s[N], now[3 * N], ans;
vector<int> a[N], b[N], c[N], d[N];
map<int, int> ap;
void add(int x, int k){
// printf("*** %lld %lld\n", x, k);
now[x] += k;
while(q[x].size()){
auto t = q[x].top();
if(t.fi <= now[x]){
s[t.se] ++;
// printf("--- %lld\n", t.se);
if(s[t.se] == l[t.se])
q2.push(t.se);
q[x].pop();
}
else
break;
}
}
signed main(){
for(int i = 1; i <= n; i ++){
t[i] = mread(), u[i] = mread();
ap[t[i]] = 1;
}
m = mread();
for(int i = 1; i <= m; i ++){
l[i] = mread();
for(int j = 1; j <= l[i]; j ++){
a[i].push_back(mread());
ap[a[i].back()] = 1;
b[i].push_back(mread());
}
k[i] = mread();
for(int j = 1; j <= k[i]; j ++){
c[i].push_back(mread());
ap[c[i].back()] = 1;
d[i].push_back(mread());
}
if(l[i] == 0)
q2.push(i);
}
for(auto &t : ap){
t.se = ++idx;
}
for(int i = 1; i <= n; i ++)
t[i] = ap[t[i]];
for(int i = 1; i <= m; i ++){
for(int &x : a[i])
x = ap[x];
for(int &x : c[i])
x = ap[x];
}
for(int i = 1; i <= m; i ++){
for(int j = 0; j < l[i]; j ++)
q[a[i][j]].push(mp(b[i][j], i));
}
for(int i = 1; i <= n; i ++){
add(t[i], u[i]);
}
while(q2.size()){
ans ++;
int i = q2.front();
q2.pop();
for(int j = 0; j < k[i]; j ++)
add(c[i][j], d[i][j]);
}
fout << ans;
return 0;
}