A

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=300005;
int mod=998244353;

void wumen(){
    double  r,a,b,h;
    cin>>r>>a>>b>>h;
    if(2*r<b){
        cout<<"Drop"<<endl;
        return ;
    }
    double y,x;
    x=(h*b)/(a-b);
    y=sqrt(x*x+b*b/4.0);
    double ans=2*r/b*y-x;
    cout<<"Stuck"<<endl;
    printf("%.5lf",ans);
}
signed main(void){

    int t=1;
    //cin>>t;
    while(t--){
       wumen();
    }
    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 998244353;
const int MAXN = 2000100,hsb=1045141919;
const ll Inf = 1000000000000000000ll;
#define PI pair<ll,ll>
#define PII pair<ll,pair<ll,ll>>
int n,k;
struct Node{
    int x,rk,id;
}a[MAXN];
int ans[MAXN];
bool cmp(Node x,Node y){return x.x > y.x;}
bool cmp2(Node x,Node y){return x.rk > y.rk;}
void solve(int l,int r){
    if (l == r) return;
    int mid = (l+r)/2;
    solve(l,mid);
    solve(mid+1,r);
    sort(a+l,a+r+1,cmp);
    if (r-l+1 > k) for (int i=l+k;i<=r;i++) if (!a[i].rk) a[i].x = 0,a[i].rk = r-l+1;
    // cerr << l << " " << r << "\n[a]: ";
    // for (int i=l;i<=r;i++) cerr << a[i].x << " \n"[i==r];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("gaming1.in","r",stdin);
    // freopen("gaming1.out","w",stdout);
    int Tcs=1;
    //cin >> Tcs;
    while (Tcs--){
        cin >> n >> k;
        n = (1<<n);
        for (int i=1;i<=n;i++) cin >> a[i].x,a[i].id=i;
        solve(1,n);
        // for (int i=1;i<=n;i++) cerr << a[i].rk << " \n"[i==n];
        for (int i=1;i<=n;i++) if (!a[i].rk) a[i].rk=hsb-i;
        sort(a+1,a+n+1,cmp2);
        // for (int i=1;i<=n;i++) cerr << a[i].rk << " ";
        int lst=0;
        for (int i=1;i<=n;i++){
            if (a[i].rk == a[lst].rk) ans[a[i].id] = lst;
            else {
                lst = i;
                ans[a[i].id] = i;
            }
        }
        // for (int i=1;i<=n;i++) cerr << a[i].rk << " ";
        for (int i=1;i<=n;i++) cout << ans[i] << " ";
    }
    return 0;
}

C

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)

typedef long long LL;

constexpr int N = 1e3 + 10, S = 1024, Q = 1e5 + 10, md = 1e9 + 7;

int T, n, q;
int a[N], L[Q], R[Q], s[Q];
LL f[N][S];
LL sum[N][S], res[Q];
vector<int> qry;

void initSum(int i)
{
    sum[i][0] = f[i][0];
    lop(j, 1, S)
        sum[i][j] = (sum[i][j - 1] + f[i][j]) % md;
    return;
};

LL getSum(int i, int l, int r)
{
    if (l == 0)
        return sum[i][r];
    else
        return (sum[i][r] - sum[i][l - 1]) % md;
}

int getZero(int x, int i)
{//第i位及以后都清零
    if(i < 0)
        return x;
    else {
        return x >> (i + 1) << (i + 1);
    }
}

LL work(int i, int j, int k)
{
    int j0, k0;
    LL tmp =  0;
    dwn(bit, 9, 0)
    {
        if(~k >> bit & 1)
        {//k这一位是0
            k0 = getZero(k, bit) | (1 << bit);
            j0 = getZero(j, bit - 1);
            (tmp += getSum(i, k0 ^ j0, (k0 ^ j0) + (1 << bit) - 1)) % md;
        }
    }
   return tmp;
}

void dpTrans(int i, int suf, int k)
{
    initSum(i); // O(s)预处理
    lop(j, 0, S)
    {
        f[suf][j] = sum[i][S - 1]; //给全集，然后再扣除掉
        // minus
        (f[suf][j] -= work(i, j, k)) %= md;
    }
}

void dfs(int l, int r, const vector<int> &qry)
{
    if (l == r)
    {
        for (auto &i : qry) //空集，外加原本这个位置
            res[i] = (a[L[i]] >= s[i]);
        return;
    }
    if (qry.size() == 0)
        return;
    //[i <- mid]或者[mid + 1 -> j] 和为j f[i][j]
    int mid = l + r >> 1;
    lop(j, 0, S)
    {
        f[mid][j] = j <= a[mid];
        f[mid + 1][j] = j <= a[mid + 1];
    }

    dwn(i, mid, l + 1)
        dpTrans(i, i - 1, a[i - 1]);
   
    lop(i, mid + 1, r)
    {
        dpTrans(i, i + 1, a[i + 1]);
    }
   
    vector<int> qryL, qryR;
    for (auto &i : qry)
    { //需要计算出在[L, R]中的点mid
        if (R[i] <= mid)
            qryL.pb(i);
        else if (L[i] > mid)
            qryR.pb(i);
        else
            lop(j, 0, S) //说明 L[i] <= mid < R[i]
                res[i] =
                    (res[i] +
                     1LL * f[L[i]][j] * f[R[i]][j ^ s[i]] % md) %
                    md;
        //[l, mid]选取j，[mid + 1, r]中选取m - j
    }
    dfs(l, mid, qryL);
    dfs(mid + 1, r, qryR);
};

int main()
{
    cin >> n >> q;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    qry.resize(q);
    iota(qry.begin(), qry.end(), 1);
    rep(i, 1, q)
        cin >> L[i] >> R[i] >> s[i];
    dfs(1, n, qry);
    rep(i, 1, q)
    {
        if (res[i] < 0)
            res[i] += md;
        cout << res[i] << '\n';
    }
}

E

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O1,O2,O3,O4,O5,Og,Os,Ofast,inline")
#define int long long
struct node{
    int nm = -1;
    int cnt = 0;
    int l,r;
}nd[200005];
int n,tmp[100005],tmp2[100005];
char ch[55];
int dfs(int x){
    if(nd[x].nm>0) return x;
    nd[x].r = x-1;
    int y = dfs(x-1);
    nd[x].l = y-1;
    y = dfs(y-1);
    return y;
}
void getcnt(int x){
    if(nd[x].nm>0) return ;
    nd[nd[x].l].cnt = nd[nd[x].r].cnt = nd[x].cnt*(-nd[x].nm);
    getcnt(nd[x].l),getcnt(nd[x].r);
}
int getans(int x){
    if(nd[x].nm>0) return nd[x].nm*nd[x].cnt;
    return getans(nd[x].l)+getans(nd[x].r);
}
signed main(){
    int T;
    cin >> n >> T;
    for(int i = 1;i<2*n;i++){
        scanf("%s",ch);
        if(ch[0]!='*') sscanf(ch,"%lld",&nd[i].nm),tmp2[++tmp2[0]] = i;
        else tmp[++tmp[0]] = i;
    }
    dfs(2*n-1);
    for(int i = 1,x;i<n;i++) cin >> x,nd[tmp[i]].nm = -x;
    nd[2*n-1].cnt = 1;
    getcnt(2*n-1);
    int ans = getans(2*n-1);
    for(int x,y;T--;){
        cin >> x >> y;
        ans+=(y-nd[tmp2[x]].nm)*nd[tmp2[x]].cnt;
        nd[tmp2[x]].nm = y;
        cout << ans << "\n";
    }
    return 0;
}

F

#include <bits/stdc++.h>
using namespace std;
long long w, h, c;
long long f[1005][1005];
long long a[1005][1005];
void solve() {
    cin >> w >> h >> c;
    long long ans = 1e17;
    long long maxn = 1e17;
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= h; ++j) cin >> a[i][j], maxn = min(maxn, a[i][j]);
    }
    memset(f, 0x3f, sizeof(f));
    f[1][0] = f[0][1] = f[0][0] = 1e15;
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= h; ++j) {
            f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), a[i][j] - 1ll * c * (i + j));
            ans = min(ans, a[i][j] + 1ll * c * (i + j) + min(f[i][j - 1], f[i - 1][j]));
        }
    }
    for (int i = 1; i <= w / 2; ++i)
        for (int j = 1; j <= h; ++j) swap(a[i][j], a[w - i + 1][j]);
    memset(f, 0x3f, sizeof(f));
    f[1][0] = f[0][1] = f[0][0] = 1e15;
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= h; ++j) {
            f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), a[i][j] - 1ll * c * (i + j));
            ans = min(ans, a[i][j] + 1ll * c * (i + j) + min(f[i][j - 1], f[i - 1][j]));
        }
    }
    printf("%lld\n", ans);
}
int main() {
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i) solve();
}

G

#include <bits/stdc++.h>
using namespace std;
int n, m;
int fa[200005];
struct node {
    int u, v, w;
} e[200005];
int find(int x) {
    if (fa[x] == x)
        return x;
    else
        return fa[x] = find(fa[x]);
}
void solve(int T) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    for (int i = 1; i <= m; ++i) {
        int x = find(e[i].u), y = find(e[i].v);
        if (x == y) continue;
        fa[x] = y;
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (find(i) == i) cnt++;
    puts(cnt == 1 ? "YES" : "NO");
}
int main() {
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; ++i) solve(i);
}