QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#592379 | #6692. Building Company | yinyuqin | TL | 0ms | 0kb | C++14 | 1.9kb | 2024-09-26 22:10:20 | 2024-09-26 22:10:21 |
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=1e5+5;
int cnt,t[maxn],u[maxn],num[maxn],m[maxn],ans;
map<int,int> ma;
priority_queue<pii> q[maxn];
struct node{
int k;
vector<int> c,d;
}a[maxn];
void check(int i){
while(!q[i].empty()&&-q[i].top().fi<=num[i]){
int id=q[i].top().se;
q[i].pop();
m[id]--;
if(!m[id]){
// cout<<ans<<" : "<<id<<endl;
// for(int kkk=1;kkk<=3;kkk++) cout<<kkk<<' '<<num[ma[kkk]]<<endl;
ans++;
for(int j=0;j<a[id].k;j++){
if(ma.find(a[id].c[j])==ma.end()) ma[a[id].c[j]]=++cnt;
int tp=ma[a[id].c[j]];
num[tp]+=a[id].d[j];
check(tp);
}
// for(int kkk=1;kkk<=3;kkk++) cout<<kkk<<' '<<num[ma[kkk]]<<endl;
}
}
}
signed main()
{
//ios::sync_with_stdio(false);
freopen("1.in","r",stdin);
int g=read();
for(int i=1;i<=g;i++){
t[i]=read(),u[i]=read();
if(ma.find(t[i])==ma.end()) ma[t[i]]=++cnt;
num[ma[t[i]]]=u[i];
}
int n=read();
for(int i=1;i<=n;i++){
m[i]=read();
for(int j=1;j<=m[i];j++){
int a=read(),b=read();
if(ma.find(a)==ma.end()) ma[a]=++cnt;
q[ma[a]].push(mp(-b,i));
}
a[i].k=read();
for(int j=1;j<=a[i].k;j++){
a[i].c.push_back(read());
a[i].d.push_back(read());
}
if(m[i]==0){
ans++;
for(int j=0;j<a[i].k;j++){
int tp=ma[a[i].c[j]];
num[tp]+=a[i].d[j];
}
}
}
// for(int i=1;i<=n;i++){
// cout<<a[i].k<<endl;
// }
// cout<<ans<<endl;
for(int i=1;i<=cnt;i++){
check(i);
}
cout<<ans<<endl;
// cout<<cnt<<' '<<ans<<endl;
// cout<<endl<<q[ma[2]].top().se<<" "<<m[4]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
2 2 1 1 2 5 1 3 1 0 2 1 1 2 1 2 3 2 2 1 3 1 5 2 3 3 4 1 2 5 3 2 1 1 1 3 4 1 1 3 0 1 3 2