D - Long Waiting
三个优先队列
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
#define piii pair<pii,int>
const int N=300010;
int n,k;int a[N],b[N],c[N],ans[N];
void solve(){cin>>n>>k;priority_queue<int,vector<int>,greater<int>> pq;priority_queue<piii,vector<piii>,greater<piii>> wat;//等待，数量priority_queue<pii,vector<pii>,greater<pii>> lev;for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];pq.push(a[i]);wat.push({{a[i],c[i]},i});}int sum=0;while(!pq.empty()){int t=pq.top();pq.pop();while(!lev.empty()){auto [t1,id]=lev.top();if(t1>t)break;sum-=c[id];lev.pop();}while(!wat.empty()){auto tem=wat.top();int t1=tem.ft.ft;int num=tem.ft.se;int id=tem.se;if(a[id]>t)break;if(num+sum>k)break;sum+=num;ans[id]=t;lev.push({t+b[id],id});pq.push(t+b[id]);wat.pop();}}for(int i=1;i<=n;i++){cout<<ans[i]<<'\n';}
}
signed main(){std::ios::sync_with_stdio(false);int T;T=1;while(T--){solve();}
}
E - Sum of Subarrays
数学，推式子，前缀和
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long longconst int N=300010;
int n,q;int a[N],s1[N],s2[N],s3[N];void solve(){cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){s1[i]=s1[i-1]-i*i*a[i];s2[i]=s2[i-1]+i*a[i];s3[i]=s3[i-1]+a[i];}while(q--){int l,r;cin>>l>>r;int ans=0;ans+=s1[r]-s1[l-1];ans+=(l+r)*(s2[r]-s2[l-1]);ans+=(-l*r-l+r+1)*(s3[r]-s3[l-1]);cout<<ans<<'\n';}}
signed main(){std::ios::sync_with_stdio(false);int T;T=1;while(T--){solve();}
}
F - Loud Cicada
类似百度之星的跑步,每个i前y年爆发年数y/a[i]取地板
每个集合前y年爆发年数y/lcm
枚举集合，
sz<m，忽略
sz>=m,
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define int long longint n,m,y;int a[21];
int C[21][21];int gcd(int x,int y){return y?gcd(y,x%y):x;
}
__int128 lcm(int x,int y){int gcdd=gcd(x,y);return x/gcd(x,y)*y;
}
int get(int sta){int res=0;for(int i=0;i<n;i++){if(sta&(1<<i)){res++;}}
return res;
}ll C(ll a,ll b){if (b > a) return 0;ll res = 1;
for (ll i = 1, j = a; i <= b; i ++, j -- ){res = res * j ;res = res /i;}
return res;
}
void solve(){cin>>n>>m>>y;for(int i = 0; i <= n; i++){C[i][0] = C[i][i] = 1;for(int j = 1; j < i; j++)C[i][j] = C[i-1][j-1] + C[i-1][j];}for(int i=0;i<n;i++)cin>>a[i];int ans=0;
for(int sta=0;sta<(1<<n);sta++){int sz=get(sta);if(sz<m)continue;else {__int128 lcmm=1;for(int i=0;i<n;i++){if(sta&(1<<i))lcmm=lcm(lcmm,a[i]);}int cnt=(int)((__int128)y/lcmm);if((sz-m)&1)ans-=C[sz][m]*cnt;else ans+=C[sz][m]*cnt;}
}
cout<<ans<<'\n';
}
signed main(){std::ios::sync_with_stdio(false);int T;T=1;while(T--){solve();}
}