Contest 25

contest

A 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int a,b,h; 
int main(){
    cin>>h>>a>>b;
    int ans=0;
    if(a>=h){
        puts("YES 1");
        return 0;
    }
    if(a<=b){
        puts("NO");
        return 0;
    }
    while(1){
        h-=a;
        ans++;
        if(h<=0)    break;
        h+=b;
    }
    printf("YES %d\n",ans); 
    return 0;
}

B 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,x,y;
int a[2000010];
int main(){
    cin>>n>>x>>y;
    rep(i,1,n)  scanf("%d",a+i);
    if(x>y){
        printf("%d\n",n);
        return 0;
    }
    int ans=0;
    rep(i,1,n){
        if(a[i]<=x) ans++;
    }
    ans=(ans+1)/2;
    printf("%d\n",ans);
    return 0;
}

C lnkkerst

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        if(is_sorted(s.begin(), s.end(), less<char>())) {
            cout << "0 0\n";
            continue;
        }
        int tmn = s.back(), pos = s.length() - 1;
        for(int i = (int)s.length() - 1; i >= 0; --i) {
            if(s[i] > tmn) pos = i;
            tmn = min(tmn, (int)s[i]);
        }
        // cout << pos << endl;
        string smin = s;
        int ansx = 0, ansy = 0;
        for(int i = pos + 1; i < (int)s.length(); ++i) {
            auto t = s;
            reverse(t.begin() + pos, t.begin() + i + 1);
            if(smin > t) {
                smin = t;
                ansx = pos;
                ansy = i;
            }
        }
        cout << ansx << ' ' << ansy << endl;
    }
    return 0;
}

D 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
vector<int> g[1010];
int n,u,v,siz[1010];
int dfs(int now,int fa){
    int cnt=0;
    for(auto to:g[now]){
        if(to==fa)  continue;
        cnt+=dfs(to,now);
    }
    return siz[now]=cnt+1;  
}
int main(){
    cin>>n;
    rep(i,1,n-1){
        scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);
    }
    int ans=0;
    dfs(1,1);
    rep(i,1,n)  ans+=siz[i];
    cout<<ans<<endl;
    return 0;
}

E 1292224662

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,a[500010],vis[500010];
int main(){
    scanf("%d",&n);
    rep(i,1,n)  scanf("%d",a+i);
//  srand(time(0));
//  n=500000;
//  rep(i,1,n)  a[i]=i%2;
    rep(i,2,n-1){
        if(a[i-1]!=a[i]&&a[i+1]!=a[i]){
            vis[i]=1;
        }
    }
    int to,ans=0;
    rep(i,1,n){
        if(vis[i]){
            to=i;
            while(vis[to]&&to<=n)   to++;   
            to--;
            int len=to-i+1;
            if(len%2){
                ans=max(ans,(len+1)/2);
                assert(a[i-1]==a[to+1]);
                rep(o,i,to) a[o]=a[i-1];
            }
            else{
                ans=max(ans,len/2);
//              assert(a[i-1]!=a[to+1]);
                rep(o,i,i+len/2-1)  a[o]=a[i-1];
                rep(o,i+len/2,to)   a[o]=a[to+1];
            }
            i=to;
        }
    }
    printf("%d\n",ans);
    rep(i,1,n){
        putchar(a[i]+'0');
        if(i!=n)    putchar(' ');
    }putchar('\n');
    return 0;
}

F tiandaochouqin

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+1; 
ll ans[maxn],a[maxn];
bool check(ll x)
{
    ll t=sqrt(x);
    return t*t!=x;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n/2;++i) scanf("%lld",&a[i]);
    ll cnt=0;
    for(int i=1;i<=n/2;++i)
    {
        cnt++;
        while(check(cnt*cnt+a[i])&&cnt<maxn) cnt++;
        if(cnt>=maxn){
            puts("No");return 0;
        }
        ans[2*i-1]=cnt*cnt;
        ans[2*i]=cnt*cnt+a[i];
        cnt=sqrt(ans[2*i]);
    }
    puts("Yes");
    for(int i=1;i<=n;++i)
    printf("%lld ",(i%2==0)?a[i/2]:ans[i]-ans[i-1]);
}

G yingyingying777

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FAST_IO
{
    static int sc_ret = 0;
    struct pt_nl {};
    struct sc
    {
        sc& operator>>(char& v) { sc_ret = scanf(" %c", &v); return *this; }
        sc& operator>>(int& v) { /*sc_ret = read(v);*/ sc_ret = scanf("%d", &v); return *this; }
        sc& operator>>(unsigned& v) { sc_ret = scanf("%u", &v); return *this; }
        sc& operator>>(double& v) { sc_ret = scanf("%lf", &v); return *this; }
        sc& operator>>(char* v) { sc_ret = scanf("%s", v); return *this; }
        sc& operator>>(string& v) { sc_ret = (bool)(cin >> v); return *this; }
        sc& operator>>(ll& v) { sc_ret = read(v); return *this; }
        sc& ch(char& v) { v = sc_ret = getchar(); return *this; }
        sc& gets(char* v) { sc_ret = fgets(v, INT_MAX, stdin) != 0; v[strlen(v) - 1] = 0; return *this; }
        operator bool() const { return sc_ret > 0; }
        template <typename T>
        int read(T& v)
        {
            T x = 0, k = 1;
            int c = getchar();
            while (c < '0' || c > '9')
            {
                if (c == '-') k = -1;
                c = getchar();
            }
            while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c - 48), c = getchar();
            v = x * k;
            return c;
        }
    }SC;
    struct pr
    {
        pr& ln() { putchar('\n'); return *this; }
        pr& operator<<(const pt_nl& nl) { putchar('\n'); return *this; }
        pr& operator<<(char v) { putchar(v); return *this; }
        pr& operator<<(int v) { write(v); return *this; }
        pr& operator<<(double v) { printf("%.2f", v); return *this; }
        pr& operator()(const char* fmt, double v) { printf(fmt, v); return *this; }
        pr& operator<<(const char* v) { printf("%s", v); return *this; }
        pr& operator<<(string v) { printf("%s", v.c_str()); return *this; }
        pr& operator<<(ll v) { write(v); return *this; }
        template <typename T>
        void write(T v)
        {
            int cnt = 0; char c[23];
            if (v == 0)
            {
                putchar('0');
                return;
            }
            if (v < 0) putchar('-'), v = -v;
            while (v) c[++cnt] = (v % 10) + 48, v /= 10;
            while (cnt > 0) putchar(c[cnt--]);
        }
        template <typename T>
        void ln(T* arr, int size)
        {
            if (size > 0)
            {
                (*this) << arr[0];
                for (int i = 1; i < size; ++i)
                {
                    putchar(' ');
                    (*this) << arr[i];
                }
                putchar('\n');
            }
        }
        template <typename T>
        void muln(T* arr, int size)
        {
            for (int i = 0; i < size; ++i)
            {
                (*this) << arr[i];
                putchar('\n');
            }
        }
    }PR;
    #define cin SC
    #define cout PR
    #define endl pt_nl()
}
using namespace FAST_IO;
ll mulit(ll a,ll b,ll m){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%m;
        a=(a<<1)%m;
        b>>=1;
    }
    return ans;
}
ll quick_mod(ll a,ll b,ll m){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mulit(ans,a,m);
        }
        a=mulit(a,a,m);
        b>>=1;
    }
    return ans;
}
ll comp(ll a,ll b,ll m){
    if(a<b) return 0;
    if(a==b) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0;i<b;i++){
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*quick_mod(cb,m-2,m)%m;
    return ans;
}
ll lucas(ll a,ll b,ll m){
    ll ans=1;
    while(a&&b){
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
const ll mod=1e9+7;
ll n,m;
int main()
{
    cin>>n>>m;
    if(n<m)
        swap(n,m);
    cout<<lucas(n+m-3-1,m-2,mod)<<endl;
    return 0;
}

H tiandaochouqin

#include<bits/stdc++.h> 
using namespace std; 
typedef long long ll;
const int maxn=(1<<21)+5;
int T,h,g,a[maxn];
vector<int>ans;
int getdeep(int pos)
{
    if(!a[pos<<1]&&!a[pos<<1|1]) return pos;
    return a[pos<<1]>a[pos<<1|1]?getdeep(pos<<1):getdeep(pos<<1|1);
}
void dfs(int x)
{
    if(!a[x<<1]&&!a[x<<1|1]) {a[x]=0;return ;}
    if(a[x<<1]>a[x<<1|1]){
        a[x]=a[x<<1];dfs(x<<1);
    }
    else {
        a[x]=a[x<<1|1];dfs(x<<1|1);
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans.clear();
        scanf("%d %d",&h,&g);
        for(int i=0;i<=(1<<(h+1));++i) a[i]=0;
        for(int i=1;i<(1<<h);++i) scanf("%d",&a[i]);
        for(int i=1;i<(1<<g);++i)
        while(getdeep(i)>(1<<g)-1) ans.push_back(i),dfs(i);
        ll sum=0;
        for(int i=1;i<(1<<g);++i) sum+=a[i];
        printf("%lld\n",sum);
        for(int i:ans) printf("%d ",i);
        puts("");
    }
}

I

J _Wallace_

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int K = 1e6 + 5;
int n, q, k;
int belong[N], b;
int ary[N];
struct Query {
    int l, r, t;
    inline bool operator < (const Query &temp) const {
        return belong[l] == belong[temp.l] ? r < temp.r : belong[l] < belong[temp.l];
    }
} qry[N];
int cnt[K << 1], L = 0, R = -1;
long long total = 0;
inline void inc(int p) {
    total += cnt[ary[p] ^ k];
    ++ cnt[ary[p]];
}
inline void dec(int p) {
    -- cnt[ary[p]];
    total -= cnt[ary[p] ^ k];
}
inline void select(int l, int r) {
    while(L < l) dec(L ++);
    while(L > l) inc(-- L);
    while(R < r) inc(++ R);
    while(R > r) dec(R --);
}
long long ans[N];
signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> q >> k;
    for (register int i = 1; i <= n; i ++)
        cin >> ary[i], ary[i] ^= ary[i - 1];
    for (register int i = 1; i <= q; i ++)
        cin >> qry[i].l >> qry[i].r, -- qry[i].l, qry[i].t = i;
    b = sqrt(n);
    for (register int i = 0; i <= n; i ++)
        belong[i] = i / b + 1;
    sort(qry + 1, qry + 1 + q);
    for (register int i = 1; i <= q; i ++) {
        select(qry[i].l, qry[i].r);
        ans[qry[i].t] = total;
    }
    for (register int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
    return 0;
}

K _Wallace_

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int S = N << 5;
int lc[S], rc[S], sum[S], total = 0;
int root[N], wei[N];
int n, q;
vector<int> G[N];
#define mid ((l + r) >> 1)
int build(int l, int r) {
    int rt = ++ total;
    if (l == r) return rt;
    lc[rt] = build(l, mid);
    rc[rt] = build(mid + 1, r);
    return rt;
}
int update(int pre, int pos, int l, int r) {
    int rt = ++ total;
    lc[rt] = lc[pre], rc[rt] = rc[pre];
    sum[rt] = sum[pre] + 1;
    if (l == r) return rt;
    if (pos <= mid) lc[rt] = update(lc[pre], pos, l, mid);
    else rc[rt] = update(rc[pre], pos, mid + 1, r);
    return rt;
}
int findKth(int a, int b, int c, int d, int k, int l, int r) {
    if (l == r) return l;
    int x = sum[lc[a]] + sum[lc[b]] - sum[lc[c]] - sum[lc[d]];
    if (k <= x) return findKth(lc[a], lc[b], lc[c], lc[d], k, l, mid);
    else return findKth(rc[a], rc[b], rc[c], rc[d], k - x, mid + 1, r);
}
#undef mid
int fa[N], size[N];
int dep[N], maxs[N];
int top[N];
void Dfs1(int rt, int f) {
    root[rt] = update(root[f], wei[rt], 1, n);
    size[rt] = 1, fa[rt] = f, dep[rt] = dep[f] + 1;
    for (vector<int>::iterator it = G[rt].begin(); it != G[rt].end(); ++ it) {
        if (*it == f) continue;
        Dfs1(*it, rt), size[rt] += size[*it];
        if (size[maxs[rt]] < size[*it])
            maxs[rt] = *it;
    }
}
void Dfs2(int rt,int tp) {
    top[rt] = tp;
    if (maxs[rt]) Dfs2(maxs[rt], tp);
    for (vector<int>::iterator it = G[rt].begin(); it != G[rt].end(); ++ it)
        if (*it != fa[rt] && *it != maxs[rt])
            Dfs2(*it, *it);
}
inline int findLCA(int u,int v) {
    while(top[u] != top[v])
        if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
        else v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
int buf[N], cnt;
signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (register int i = 1; i <= n; ++ i)
        cin >> wei[i], buf[i] = wei[i];
    for (register int u, v, i = 1; i < n; ++ i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    sort(buf + 1, buf + 1 + n), cnt = unique(buf + 1, buf + 1 + n) - buf - 1;
    for (register int i = 1; i <= n; i ++)
        wei[i] = lower_bound(buf + 1, buf + 1 + cnt, wei[i]) - buf;
    root[0] = build(1, n);
    Dfs1(1, 0), Dfs2(1, 1);
    while (q --) {
        int u, v, k, l, f;
        cin >> u >> v >> k;
        l = findLCA(u, v), f = fa[l];
        cout << buf[findKth(root[u], root[v], root[f], root[l], k, 1, n)] << endl;
    }
    return 0;
}