By Cocoly1990

// Time complexity O(nlogn) because of map
#include <bits/stdc++.h>

const int MX = 100 + 5;

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::map<int ,int> occ;
    for (int i = 1; i <= n; ++i) {
      int x;
      std::cin >> x;
      occ[x]++;
    }
    if (occ.size() >= 3) puts("No");
    else {
      if (std::abs(occ.begin()->second - occ.rbegin()->second) <= 1) {
        puts("Yes");
      } else {
        puts("No");
      }
    }
  }
  return 0;
}

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}

void solve() {
  std::string s, t;
  int l1, l2;
  std::cin >> l1 >> l2;
  std::cin >> s >> t;
  if (ok(s)) {
    std::cout << "Yes" << std::endl;
    return;
  }

  if (!ok(t) || *t.begin() != *t.rbegin()) {
    std::cout << "No" << std::endl;
    return;
  }

  int zz = 0, oo = 0;
  for (size_t i = 1; i < s.length(); ++i) {
    if (s[i] == s[i - 1]) {
      if (s[i] == '0') zz = true;
      if (s[i] == '1') oo = true;
    }
  }

  if (zz && t[0] == '0') {
    std::cout << "No" << std::endl;
    return;
  }
  if (oo && t[0] == '1') {
    std::cout << "No" << std::endl;
    return;
  }  

  std::cout << "Yes" << std::endl;
  return;
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}


std::string s;
void solve() {
  int n; std::cin >> n;
  std::cin >> s;
  int cnt0 = 0, cnt1 = 0;
  for (int i = 0; i < s.length(); ++i) {
    cnt0 += s[i] == '0';
    cnt1 += s[i] == '1';
  }
  if (cnt0 != cnt1) {
    std::cout << -1 << std::endl;
    return;
  }
  std::vector<int> z;
  std::deque<char> q;
  for (int i = 0; i < s.length(); ++i)
    q.push_back(s[i]);
  
  int d = 0;
  while (!q.empty()) {
    if (q.front() == q.back()) {
      if (q.front() == '0') {
        q.push_back('0');
        q.push_back('1');
        z.push_back(n - d);
      } else {
        q.push_front('1');
        q.push_front('0');
        z.push_back(0 + d);
      }
      n += 2;
    }
    while (!q.empty() && q.front() != q.back()) {
      q.pop_back();
      q.pop_front();
      ++d;
    }
  }

  std::cout << z.size() << std::endl;
  for (int i = 0; i < z.size(); ++i) {
    std::cout << z[i];
    if (i + 1 == z.size()) std::cout << std::endl;
    else std::cout << " ";
  }
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

By Cocoly1990

#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 5e5 + 7;
int T, n, C, p[N]; i64 a[N];
void solve () {
	cin >> n >> C;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	iota (p + 1, p + n + 1, 1);
	sort (p + 1, p + n + 1, [&] (const int &u, const int &v) {
		return 1ll * u * C - a[u] < 1ll * v * C - a[v];
	});
	i64 now = a[1];
	for (int i = 1, u; i <= n; i ++) {
		u = p[i];
		if (u == 1) continue;
		if (1ll * u * C > now + a[u]) return cout << "No\n", void ();
		now += a[u];
	}
	return cout << "Yes\n", void ();
}
int main () {
	ios :: sync_with_stdio (false); cin.tie (0); cout.tie (0);
	cin >> T; while (T --) solve ();
}

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define LL long long

const int MX = 2e5 + 23;
const int INF = 1e9;

void chkmax(int &x, int y) {
  x = std::max(x, y);
}

struct Interval {
  int l, r;
} I[MX];

bool cmp(int x, int y) {
  return I[x].l > I[y].l;
}

std::vector<int> add[MX], del[MX];
int n, m, k, ban[MX];

int st[21][MX][18], lg[MX];

int query(int d, int l, int r) {
  int len = lg[r - l + 1];
  return std::max(st[d][l][len], st[d][r - (1 << len) + 1][len]);
}

void change(int d, int p, int val) {
  chkmax(st[d][p][0], val);
  for (int i = 1; p - (1 << i) + 1 >= 0; ++i) {
    st[d][p - (1 << i) + 1][i] = std::max(
          st[d][p - (1 << i) + 1][i - 1],
          st[d][p - (1 << (i - 1)) + 1][i - 1]);
  }
}

void init() {
  lg[0] = -1;
  for (int i = 1; i <= n + 1; ++i)
    lg[i] = lg[i - 1] + ((i & -i) == i); 
  for (int i = 1; i <= m; ++i) ban[i] = false;
  for (int i = 1; i <= n + 1; ++i) {
    add[i].clear();
    del[i].clear();
  }
  for (int i = 0; i <= k; ++i)
    for (int j = 0; j <= n; ++j)
      for (int _k = 0; _k < 18; ++_k)
        st[i][j][_k] = -INF;
}

void solve() {
  scanf("%d%d%d", &n, &m, &k);
  init();
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    I[i] = (Interval){l, r};
    add[l].push_back(i);
    del[r + 1].push_back(i);
  }
  
  std::vector<int> cur, tmp;

  change(0, 0, 0);
  
  int uncover = 0, ans = 0;
  int cnti = 0;
  for (int i = 1; i <= n; ++i) {
    for (auto j : add[i]) {
      cur.push_back(j);
      ++cnti;
    }

    for (auto j : del[i]) {
      ban[j] = true;
      --cnti;
    }

    if (cnti > k) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      continue;
    }

    tmp.clear();
    for (auto j : cur) {
      if (!ban[j]) {
        tmp.push_back(j);
      }
    }
    cur = tmp;
    std::sort(cur.begin(), cur.end(), cmp);
    
    if (cur.empty()) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      ++uncover;
      continue;
    }
    
    if (I[cur[0]].l <= i - 1)
      for (int g = 0; g <= k; ++g) {
        int z = query(g, I[cur[0]].l, i - 1);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
      }
    else {
      for (int g = 0; g <= k; ++g) {
        change(g, i, -INF);
      }
    }
    int cp = I[cur[0]].l - 1;
    

    for (int j = 0; j < cur.size(); ++j) {
      if (j + 1 != cur.size() && I[cur[j]].l == I[cur[j + 1]].l)
        continue;
      int np = (j + 1 == cur.size() ? 0 : I[cur[j + 1]].l);
      for (int g = j + 1; g <= k; ++g) {
        int z = query(g - (j + 1), np, cp);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
        // change(root[g], i, z + 1);
      }
      cp = np - 1;
    }
  }
  printf("%d\n", ans + uncover);
}

int main() {
  int t; scanf("%d", &t);

  while (t--) solve();
  return 0;
}

By waaitg

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
stack<int>s[maxn];
int re[maxn],st[maxn],vis[maxn],tp;
int dfs(int u){
    if(re[u])
        return re[u];
    if(s[u].empty())
        return u;
    if(vis[u]){
        st[tp+1]=0;
        while(st[tp+1]!=u){
            s[st[tp]].pop();
            vis[st[tp]]=0;
            --tp;
        }
        return dfs(u);
    }
    st[vis[u]=++tp]=u;
    return dfs(s[u].top());
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int k;scanf("%d",&k);
        while(k--){
            int c;scanf("%d",&c);
            s[i].push(c);
        }
    }
    for(int i=1;i<=n;++i){
        tp=0;int ok=dfs(i);
        for(int j=1;j<=tp;++j)
            re[st[j]]=ok;
        printf("%d%c",ok," \n"[i==n]);
    }
    return 0;
}

By waaitg

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Edge{
    int v,nt;
    Edge(int v=0,int nt=0):
        v(v),nt(nt){}
}eG[maxn*160];
int hdG[maxn*40],numG;
void qwqG(int u,int v){
    eG[++numG]=Edge(v,hdG[u]);hdG[u]=numG;
}
int tot;
struct AnTree{
    struct Edge{
        int v,nt;
        Edge(int v=0,int nt=0):
            v(v),nt(nt){}
    }e[maxn*2];
    int hd[maxn],num;
    void qwq(int u,int v){
        e[++num]=Edge(v,hd[u]),hd[u]=num;
    }
    int n;
    void init(int n){
        this->n=n;
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            qwq(u,v);qwq(v,u);
        }
    }
    int pa[maxn][20],id[maxn][20],dp[maxn];
    void dfs(int u,int p){
        if(p==0)dp[u]=0;
        for(int i=1;(1<<i)<=dp[u];++i)
            pa[u][i]=pa[pa[u][i-1]][i-1];
        for(int i=hd[u];i;i=e[i].nt){
            int v=e[i].v;
            if(v==p)continue;
            dp[v]=dp[u]+1;
            pa[v][0]=u;
            id[v][0]=++tot;
            dfs(v,u);
        }
    }
    int getid(int u,int d){
        int&re=id[u][d];
        if(re)return re;
        re=++tot;
        qwqG(re,getid(u,d-1));
        qwqG(re,getid(pa[u][d-1],d-1));
        return re;
    }
    void link(int x,int u,int v){
        if(dp[u]<dp[v])swap(u,v);
        for(int t=dp[u]-dp[v],cn=0;t;t>>=1,++cn)
            if(t&1)qwqG(x,getid(u,cn)),u=pa[u][cn];
        if(u==v)return;
        int t=0;while(dp[u]>>t)++t;
        while(t--){
            if(pa[u][t]!=pa[v][t]){
                qwqG(x,getid(u,t));
                qwqG(x,getid(v,t));
                u=pa[u][t];v=pa[v][t];
            }
        }
        qwqG(x,getid(u,0));
        qwqG(x,getid(v,0));
    }
    void erase(void){
        for(int i=1;i<=n;++i){
            hd[i]=0,dp[i]=0;int j=0;
            while(pa[i][j])pa[i][j++]=0;
            j=0;while(id[i][j])id[i][j++]=0;
        }
        num=0;
    }
    int parent(int u){
        return pa[u][0];
    }
    int identity(int u){
        return id[u][0];
    }
}T1,T2;
int dfn[maxn*40],low[maxn*40],cnt;
int st[maxn*40],tp,in[maxn*40];
int scc[maxn*40],scn;
int vis[maxn*40];
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    in[st[++tp]=u]=true;
    for(int i=hdG[u];i;i=eG[i].nt){
        int v=eG[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scn;
        st[tp+1]=0;
        while(st[tp+1]!=u){
            in[st[tp]]=false;
            scc[st[tp]]=scn;
            --tp;
        }
    }
}
const int mod=1e9+7;
int power(int a,int x){
    int re=1;
    while(x){
        if(x&1)re=1ll*re*a%mod;
        a=1ll*a*a%mod,x>>=1;
    }
    return re;
}
void solve(void){
    int n;scanf("%d",&n);
    T1.init(n);T2.init(n);
    T1.dfs(1,0);T2.dfs(1,0);
    int rec=tot;
    for(int i=2;i<=n;++i){
        T2.link(T1.identity(i),i,T1.parent(i));
        T1.link(T2.identity(i),i,T2.parent(i));
    }
    for(int i=1;i<=tot;++i)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=rec;++i)
        ++vis[scc[i]];
    int ANS=0;
    for(int i=1;i<=scn;++i){
        if(vis[i])++ANS;
        vis[i]=0;
    }
    for(int u=1;u<=rec;++u){
        if(eG[hdG[u]].nt==0){
            int v=eG[hdG[u]].v;
            if(u<v&&eG[hdG[v]].nt==0){
                if(eG[hdG[v]].v==u){
                    --ANS;
                }
            }
        }
    }
    ANS=power(2,ANS);
    printf("%d\n",ANS);
    for(int i=1;i<=tot;++i){
        hdG[i]=0;
        dfn[i]=low[i]=scc[i]=0;
    }
    tot=cnt=scn=numG=0;
    T1.erase();T2.erase();
}
int main(){
    // freopen("test","r",stdin);
    // freopen("out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
	static char q[64];int cnt=0;
	if(x==0)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
long long gcd(long long a,long long b){
	if(b==0)return a;
	return gcd(b,a%b);
}
struct Frac{
	long long a;
	int b;// a/b
	Frac(long long a=0,int b=1):
		a(a),b(b){}
	bool operator < (const Frac o)const{
		return a*o.b<o.a*b;
	}
	bool operator > (const Frac o)const{
		return a*o.b>o.a*b;
	}
	bool operator == (const Frac o)const{
		return a*o.b==o.a*b;
	}
	void output(){
		printf("%lld/%d",a,b);
	}
};
const int inf=0x3f3f3f3f;
struct Val{
	int p1,p2;Frac v1,v2;
	Val(int p1=inf,int p2=inf,Frac v1=Frac(),Frac v2=Frac()):
		p1(p1),p2(p2),v1(v1),v2(v2){}
	void output(void){
		printf("%d : ",p1);v1.output();puts("");
		printf("%d : ",p2);v2.output();puts("\n");
	}
};
Val Comb(Val A,Val B){
	if(A.p1>B.p1)swap(A,B);
	if(B.v1==A.v1)
		return Val(A.p1,A.p2<B.p2?A.p2:B.p2,A.v1,A.p2<B.p2?A.v2:B.v2);
	return Val(A.p1,A.p2<B.p1?A.p2:B.p1,A.v1,A.p2<B.p1?A.v2:B.v1);
}
const int maxn=10005,maxk=505;
struct Edge{
	int v,nt;
	Edge(int v=0,int nt=0):
		v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
	e[++num]=Edge(v,hd[u]),hd[u]=num;
}
long long sm[maxn];int sz[maxn];
int dp[maxn][maxk],wp[maxn][maxk],k,n;
Val va[maxn][maxk];
void Merge(int x,int l,int r,int L,int R){
	wp[x][0]=0;
	va[x][0]=Comb(va[l][0],va[r][0]);
	L=min(L,k);R=min(R,k);
	int up=min(L+R,k);
	for(int i=1;i<=up;++i){
		int t=wp[x][i]=min(L,i),cl=inf,cr=inf;
		while(t>0&&i-t<R){
			cl=min(cl,dp[l][t]);--t;
			cr=min(cr,dp[r][i-t]);
			if(cr<cl)wp[x][i]=t,cl=cr=inf;
		}
		t=wp[x][i-1];cl=cr=inf;
		if(wp[x][i-1]<wp[x][i]){
			while(t<wp[x][i])cl=min(cl,dp[l][++t]);
			dp[x][i]=cl;
		}
		else{
			while(i-t-1<i-wp[x][i])cr=min(cr,dp[r][i-(t--)]);
			dp[x][i]=cr;
		}
		va[x][i]=Comb(va[l][wp[x][i]],va[r][i-wp[x][i]]);
	}
}
int MN[maxn],rsz[maxn];
long long val[maxn];
void dfs(int u,int p){
	int l=0,fa=0;sm[u]=val[u];
	sz[u]=0;rsz[u]=1;MN[u]=0;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p){fa=i;continue;}dfs(v,u);
		Merge(i,i^1,l,sz[v],sz[u]);
		sm[u]+=sm[v],sz[u]+=sz[v];
		rsz[u]+=rsz[v];
		l=i;
	}
	if(sz[u]==0){
		++sz[u];MN[u]=1;
		va[fa][0]=va[fa][1]=Val(u,inf,val[u]);
		dp[fa][1]=inf;
	}
	else{
		int up=min(sz[u],k);
		for(int i=0;i<=up;++i)
			va[fa][i]=Comb(va[l][i],Val(u,inf,val[u])),dp[fa][i]=dp[l][i];
		Frac tmp(sm[u],rsz[u]);
		for(int i=1;i<=up;++i)
			if(va[fa][i].v1>tmp||(va[fa][i].v1==tmp&&va[fa][i].v2>tmp))
				va[fa][i]=Val(va[fa][i].p1,inf,tmp),MN[u]=i;
		if(MN[u]){
			if(va[fa][0].v1==va[fa][1].v1)
				dp[fa][1]=va[fa][0].p2;
			else
				dp[fa][1]=va[fa][0].p1;
			for(int i=2;i<=MN[u];++i)
				dp[fa][i]=inf;
			if(MN[u]<up){
				if(va[fa][MN[u]].v1==va[fa][MN[u]+1].v1)
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p2;
				else
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p1;
			}
		}
	}/*
	int up=min(sz[u],k);
	printf("%d MN:%d\n",u,MN[u]);
	for(int i=1;i<=up;++i)
		printf("dp %d = %d\n",i,dp[fa][i]);*/
}
int st[maxn],ts;
int que[maxn],cnt;
void solve(int u,int p,int sk){
	if(sk==0)return;sk=min(sk,sz[u]);
	if(sk<=MN[u])return st[++ts]=u,void();
	int tnc=cnt;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p)continue;
		que[cnt++]=i;
	}
	for(int j=cnt-1;j>=tnc;--j){
		int i=que[j];
		solve(e[i].v,u,wp[i][sk]);
		sk-=wp[i][sk];
	}
}
void imple(void){
	int r;
	read(n),read(r),read(k);
	for(int i=1;i<=n;++i)
		read(val[i]);
	qwq(r,0);
	for(int i=1;i<n;++i){
		int u,v;read(u),read(v);
		qwq(u,v);qwq(v,u);
	}
	dfs(r,0);
	solve(r,0,k);
	printf("%d\n",ts);
	for(int i=1;i<=ts;++i)
		printf("%d%c",st[i]," \n"[i==ts]);
	for(int i=0;i<=n;++i)hd[i]=0;
	num=cnt=ts=0;
}
int main(){
	// freopen("test","r",stdin);
	int T;read(T);
	while(T--)imple();
	return 0;
}

Div. 1:

1. Benq
2. Petr
3. ecnerwala
4. Geothermal
5. Radewoosh

Div. 2:

1. xhx114514
2. Acetyl
3. rainboy
4. Anonymely
5. ian_HLX

Div. 1 first solves:

• A: tourist
• B: TheStory
• C1: neal
• C2: Seyaua
• D: ksun48
• E: ecnerwala
• F: Petr

Div. 2 first solves:

• A: marzipan
• B: italianDefence
• C: riroan
• D: PaoloB
• E1: Smirk
• E2: Acetyl
• F: rainboy

By Imakf

#include <iostream>

void solve(){
    int n; std::cin >> n;
    for(int i = 1 ,nouse ; i <= n ; ++i){
        std::cin >> nouse;
    }
    std::cout << "1 " << n << std::endl;
}

int main(){
    int t; std::cin >> t;
    while(t--) solve();
    return 0;
}

By waaitg

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int a[maxn];
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		int n;scanf("%d",&n);
		int tmp=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			tmp=gcd(tmp,a[i]);
		}
		printf("%d\n",a[n]/tmp+(a[1]==0));
	}
	return 0;
}

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
	static char q[64];int cnt=0;
	if(x==0)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10+'0',x/=10;
	while(cnt--)pc(q[cnt]);
}
const int maxn=200005;
int a[maxn];
int main(){
	int t;read(t);
	while(t--){
		int n;read(n);
		for(int i=1;i<=n;++i)
			read(a[i]);
		sort(a+1,a+n+1);
		if(a[1]==a[n]){
			write(n/2),pc('\n');
			continue;
		}
		long long ans=0;
		for(int l=1,r=1;l<=n;l=r=r+1){
			while(r+1<=n&&a[r+1]==a[l])++r;
			ans=max(ans,1ll*(n-r)*r);
		}
		write(ans),pc('\n');
	}
	return 0;
}

By Imakf

#include <cstdio>
#include <iostream>

#define LL long long

const int MX = 5000 + 233;
LL C[MX][MX] ,n ,p ,fac[MX];

void init(){
	for(int i = 0 ; i < MX ; ++i) C[i][0] = 1;
	for(int i = 1 ; i < MX ; ++i)
		for(int j = 1 ; j < MX ; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
	fac[0] = fac[1] = 1 % p;
	for(int i = 2 ; i < MX ; ++i) fac[i] = fac[i - 1] * i % p;
}

int main(){
	std::cin >> n >> p;
	init();
	int t = n / 2;
	LL Ans = 0;
	for(int i = t ; i <= n - 1 ; ++i){
		if((n & 1) && i == n - 1) break;
		int upper = (i == n - 1) ? n - i - 1 : n - i - 2;
		for(int j = 0 ; j <= upper ; ++j){
			Ans = (Ans + n * (2 * t - i) * C[upper][j] % p * fac[j + i - 1]) % p;
		}
	}
	std::cout << Ans << std::endl;
	return 0;
}

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 2e5 + 5;

int n ,s;
struct Goat{
    int x ,y ,id;
}A[MX];

bool cmp(Goat a ,Goat b){
    return a.x < b.x;
}

int mx[MX];
int calc(int id){
    if(id == 1) return A[id].x;
    int far = std::max(calc(id - 1) ,mx[id - 2]);
    return std::max(std::min(far ,A[id].x) + A[id].y ,A[id].x);
}

int ans[MX];
void solve(){
    scanf("%d%d" ,&n ,&s);
    for(int i = 1 ,x ,y ; i <= n ; ++i){
        scanf("%d%d" ,&x ,&y);
        A[i] = (Goat){x ,y ,i};
        ans[i] = false;
    }
    std::sort(A + 1 ,A + 1 + n ,cmp);
    for(int i = 1 ; i <= n ; ++i){
        mx[i] = std::max(A[i].x + A[i].y ,mx[i - 1]);
    }
    for(int i = 1 ; i < n ; ++i){
        if(A[i].x + A[i].y >= s){
            ans[A[i].id] = true;
        }
    }
    if(calc(n) >= s) ans[A[n].id] = true;
    puts(ans[1] ? "YES" : "NO");
}

int main(){
    int t; scanf("%d" ,&t);
    while(t--) solve();
    return 0;
}

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long

const int MX = 3e3 + 5;

bool vis[MX];
LL w[MX][MX] ,dis[MX];

std::vector<int> e[MX];

int size[MX];
void dfs(int x ,int f){
    size[x] = 1;
    for(auto i : e[x]){
        if(i == f) continue;
        dfs(i ,x);
        size[x] += size[i];
    }
    for(auto i : e[x]){
        if(i == f) continue;
        printf("%d %d %lld\n" ,x ,i ,(w[1][x] - w[1][i]) / size[i]);
    }
}

int main(){
    int n; scanf("%d" ,&n);
    memset(w ,-0x3f ,sizeof w);
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= i ; ++j){
            scanf("%lld" ,&w[i][j]);
            w[j][i] = w[i][j];
        }
    }
    memset(dis ,-0x3f ,sizeof dis);
    dis[1] = 0;
    for(int i = 1 ; i <= n ; ++i){
        int x = 0;
        for(int j = 1 ; j <= n ; ++j){
            if(!vis[j] && (!x || dis[j] > dis[x])){
                x = j;
            }
        }
        //debug("x = %d " ,x);
        //ans += dis[x];
        if(i != 1) for(int j = 1 ; j <= n ; ++j){
            if(w[j][x] == dis[x] && vis[j]){
                e[x].push_back(j);
                e[j].push_back(x);
                //debug("%d %d\n" ,x ,j);
            }
        }
        vis[x] = true;
        for(int j = 1 ; j <= n ; ++j){
            dis[j] = std::max(dis[j] ,w[x][j]);
        }
    }
    //return 0;
    dfs(1 ,1);
    return 0;
}

By Imakf

#include <bits/stdc++.h>

using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

std::map<std::pair<int, int>, int> M;
int n;
int query(int l, int r, int k = 2) {
    if (l == r) return 1;
    if (l == 1 && r == n) {
        return n / k + 1; 
    }
    if (k == 2 && M.count(make_pair(l, r)))
        return M[make_pair(l, r)];
    printf("? %d %d %d\n",l ,r, k);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    if (k == 2) {
        M[make_pair(l, r)] = x;
    }
    return x;
}

void answer(int x) {
    printf("! %d\n", x);
    fflush(stdout);
    exit(0);
}

int main() {
     scanf("%d", &n);

    int npos = 0;
    if (n % 2 == 0) {
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;

            if (query(1, mid, n) == 2) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            npos = r + 1;
        }
        if (npos == 1 || npos == 2) {
            if (query(2, n, n) == 1) {
                npos = 1;
            } else {
                npos = 2;
            }
        }
    }
    //answer(npos);
    //if (n & 1) {
        int l = 1, r = n - 1, mid;
        while (l <= r) {
            debug("[%d ,%d]\n",l ,r);
            mid = (l + r) >> 1;
            int lq = 2 * query(1, mid) - (mid - 1 + 1);
            int rq = 2 * query(mid + 1, n) - (n - (mid + 1) + 1);
            if (npos) {
                if (npos <= mid) --lq;
                else --rq;
            }
            if (lq > rq) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        // cut [r + 1, r + 2]
        ++r;
        // now cut [r, r + 1]
        answer(r);
   // }
}

By waaitg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int query(int l,int r,int k){
	printf("? %d %d %d\n",l,r,k);
	fflush(stdout);int re;scanf("%d",&re);
	return re;
}
void answer(int x){
	printf("! %d\n",x);
	fflush(stdout);
}
int rt=-1;
void divide(int l,int r,int l1,int l2,int r1,int r2){
	if(l==r){
		answer(l);
		return;
	}
	if(l+1==r){
		if(r1==r2+1){
			if(query(r,n,2)==r2+1)answer(r);
			else answer(l);
		}
		else if(l1==l2+1){
			if(query(1,l,2)==l2+1)answer(l);
			else answer(r);
		}
		else{
			if(l>1){
				if(query(1,l,n)==2)answer(r);
				else answer(l);
			}
			else{
				if(query(r,n,n)==2)answer(l);
				else answer(r);
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	int L=query(1,mid,2),R=query(mid+1,n,2);
	if(L*2-mid>R*2-(n-mid))divide(l,mid,L,l2,r1,R);
	else if(L*2-mid<R*2-(n-mid))divide(mid+1,r,l1,L,R,r2);
	else{
		if(~rt){
			if(rt)divide(l,mid,L,l2,r1,R);
			else divide(mid+1,r,l1,L,R,r2);
		}
		if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2);
		else rt=1,divide(l,mid,L,l2,r1,R);
	}
}
int main(){
	scanf("%d",&n);
	divide(1,n,n/2+1,0,n/2+1,0);
	return 0;
}

By errorgorn

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

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,k;
ii arr[600005];
int ans[400005];

vector<int> uni;
int nxt[200005];
int state[200005];
int state2[200005];

bool has(int l,int r,set<int> &s){
	auto it=s.lb(l);
	return *it<r;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m>>k;
	rep(x,0,m) cin>>arr[x].fi>>arr[x].se;
	rep(x,0,m) arr[x].fi--,arr[x].se--;
	rep(x,0,2*m) arr[x+m]=arr[x];
	
	int l=0;
	
	while (l<m){
		uni={0,n};
		rep(x,l,l+2*k) uni.pub(arr[x].fi),uni.pub(arr[x].se+1);
		sort(all(uni)); uni.erase(unique(all(uni)),uni.end());
		rep(x,0,sz(uni)-1) nxt[uni[x]]=uni[x+1];
		
		set<ii> s; for (auto it:uni) s.insert({it,it}); //position, color
		rep(x,0,sz(uni)) state[uni[x]]=state2[uni[x]]=1;
		
		vector<iii> proc; //time, position, state
		rep(x,l+k,l+2*k){
			if (s.count({arr[x].fi,arr[x].fi}) && state[arr[x].fi]){
				proc.pub({x,arr[x].fi,state[arr[x].fi]});
				state[arr[x].fi]=0;
			}
			
			while (true){
				auto it=s.ub(ii(arr[x].fi,1e9));
				if ((*it).fi>arr[x].se) break;
				
				if (arr[x].se+1<(*next(it)).fi) s.insert({arr[x].se+1,(*it).se});
				else{
					proc.pub({x,(*it).se,state[(*it).se]});
					state[(*it).se]=0;
				}
				
				s.erase(it);
			}
		}
		
		int curr=0;
		set<int> pos={n};
		for (auto [a,b]:s) if (b!=n){
			curr++;
			if (state[b]) curr+=nxt[b]-b-1;
			pos.insert(b);
		}
		
		s.clear(); for (auto it:uni) s.insert({it,it}); //color, position
		set<ii> ranges; rep(x,0,sz(uni)-1) ranges.insert({uni[x],uni[x+1]});
		
		rep(x,l+k,l){
			//merge things
			auto it=s.lb({arr[x].fi,-1});
			vector<int> v={(*it).se};
			while ((*it).fi<=arr[x].se){
				it=next(it);
				s.erase(prev(it));
				v.pub((*it).se);
			}
			
			if (sz(v)>1){
				rep(x,0,sz(v)-1){
					if (state[v[x]] && state2[v[x]]) curr-=v[x+1]-v[x]-1;
					state2[v[x]]=0;
					curr-=has(v[x],v[x+1],pos);
					ranges.erase({v[x],v[x+1]});
				}
				curr+=has(v[0],v[sz(v)-1],pos);
				s.insert({arr[x].fi,v[0]});
				ranges.insert({v[0],v[sz(v)-1]});
			}
			
			while (!proc.empty() && get<0>(proc.back())==x+k){
				int a,b,c; tie(a,b,c)=proc.back(); proc.pob();
				if (c){
					state[b]=c;
					if (state[b] && state2[b]) curr+=nxt[b]-b-1;
				}
				
				if (!pos.count(b)){
					auto it=prev(ranges.ub({b,1e9}));
					int l,r; tie(l,r)=*it;
					if (!has(l,r,pos)) curr++;
					pos.insert(b);
				}
			}
			
			ans[x]=curr;
		}
		
		
		l+=k;
	}
	
	rep(x,0,m) cout<<ans[x]<<" "; cout<<endl;
}

109627519

109637470

109637538

109637608

109628224

109637767

109628977

109637826

$$$\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Gray Code is a special permutation of $$$n$$$-bit binary strings ,which requires adjacent strings have exactly one different bit. Specially, the first string is adjacent to the last string.

One example of $$$2$$$-bit Gray Code is $$$00,01,11,10$$$.

We give an algorithm of generating Gray Code below:

• $$$1.$$$ $$$1$$$-bit Gray Code consist of two $$$1$$$-bit binary string: $$$0,1$$$

• $$$2.$$$ The first $$$2^n$$$ binary strings of $$$(n+1)$$$-bit Gray Code is $$$n$$$-bit Gray Code($$$2^n$$$ binary strings in total) generated by this algorithm adding a prefix $$$0$$$.

• $$$3.$$$ The next $$$2^n$$$ binary strings of $$$(n+1)$$$-bit Gray Code is $$$n$$$-bit Gray Code($$$2^n$$$ binary strings in total) generated by this algorithm being reversed ,then adding a prefix $$$1$$$.

We number all the Gray Code from $$$0$$$ to $$$2^n-1$$$. Now you task is to figure out the $$$k$$$-th binary string of $$$n$$$-bit Gray Code.

$$$\bf{Input}$$$

Only two integer $$$n ,k$$$ ,the bit of Gray Code and the index of the binary string.

$$$\bf{Output}$$$

One binary string, the answer.

$$$\bf{Constraints}$$$

$$$1\le n \le 64, 0\le k < 2^n$$$

$$$\bf{D1T2\ Brackets\ Tree\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

First we have some definitions in this problem.

What is a valid bracket string:

• $$$1.$$$ $$$()$$$ is;
• $$$2.$$$ If $$$A$$$ is, then $$$(A)$$$ is;
• $$$3.$$$ if $$$A$$$ and $$$B$$$ are, then $$$(AB)$$$ is.

What are a substring and different substrings:

• $$$1.$$$ The substring of string $$$S$$$ is a string consisting of any continuous characters in string $$$S$$$. We can describe a substring like $$$S(l,r)\ (1 \le l \le r \le |S| ,|S|$$$ is the length of string $$$S$$$)​ , where $$$l$$$ and $$$r$$$ are the left endpoint and right endpoint, respectively.
• $$$2.$$$ Two substrings of string $$$S$$$ is regarded different when they have different $$$l$$$ or $$$r$$$.

A tree consists of $$$n$$$ vertices and $$$n-1$$$ edges. Every edge connects two vertices. There is exactly one simple path between two vertices on a tree.

Little Q is a curious kid. One day on his way to school he saw a tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The vertex with index $$$1$$$ is the root. Except vertex $$$1$$$, every vertex has one parent. The parent of vertex $$$u$$$ is $$$f_u\ (1 \le f_u < u)$$$.

Little Q found that there was exactly one bracket on a vertex. It could be $$$'('$$$ or $$$')'$$$. Little Q defined $$$s_i$$$ as the string formed by: writing down all the vertices through the simple path from root to vertex $$$i$$$ in one line.

It is obvious that $$$s_i$$$ is a bracket string but may not be a valid bracket string. So Little Q was going to figure out, for every $$$i\ (1 \le i \le n)$$$, how many different substrings of $$$s_i$$$ are valid bracket string?

This problem is so difficult for Little Q, so he wants you to help him out. Denote $$$k_i$$$ is the number of valid bracket string in different substrings of $$$s_i$$$. You need to figure out $$$\bigotimes\limits^{n}_{i=1} i\times k_i$$$. $$$\bigotimes$$$ stands for $$$\bf{xor}$$$ operation here.

$$$\bf{Input}$$$

The first line contains one integer $$$n$$$, the number of vertices on the tree.

The second line contains one string consisting of characters $$$'(’$$$ and $$$')'$$$ (No quotation marks). The $$$i$$$-th bracket is the bracket on $$$i$$$-th vertex.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le n \le 5\times 10^5$$$

$$$\bf{D1T3\ Numbers\ on\ a\ Tree\ 2s\ 256MB}$$$

$$$\bf{Statement}$$$

You are given a tree consisting of $$$n$$$ vertices and $$$n-1$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. At the beginning, every vertex has a different number on it. Numbers are $$$1,2,...,n$$$.

Next, you are going to cut off exactly $$$n-1$$$ edges. During one operation, you choose a edge connecting vertex $$$u ,v$$$, exchange each number on itself, then the edge disappears.

After $$$n-1$$$ operations, all the edges are cut off. Now sort all the vertices by number on it, from small to large. Then you get a permutation $$$P_i$$$ of the vertices. Your goal is to minimize the lexicographical order of $$$P_i$$$.

$$$\bf{Input}$$$

Input contains several testcases.

The first line contains an integer $$$T$$$, the number of testcases.

For every testcases:

The first line contains an integer $$$n$$$, the number of vertices.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is the index of the vertex on which number $$$i$$$ is at beginning.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output $$$n$$$ integers separated by space, the minimum lexicographical order of permutation $$$P_i$$$.

$$$\bf{Constraints}$$$

$$$1 \le T \le 10 ,1 \le n \le 2000$$$

$$$\bf{D2T1\ Today's\ Meal\ of\ Emiya's\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Emiya is a high school student. He is good at cooking. He masters $$$n$$$ ways of cooking and has $$$m$$$ kinds of different ingredients. We number cooking ways from $$$1$$$ to $$$n$$$ and ingredients from $$$1$$$ to $$$m$$$.

Every dish Emiya makes will use exactly one cooking way and exactly one ingredient. If he use $$$i$$$-th cooking way and $$$j$$$-th ingredient, then he can make $$$a_{i,j}$$$ different dishes, which means Emiya can make $$$\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}a_{i,j}$$$ different dishes in total.

Today Emiya is going to make a meal for his friend Yazid and Rin. They all have their own needs. For a meal with $$$k$$$ dishes:

• Emiya does not want to make themselves hungry, so $$$k\ge 1$$$.
• Rin wants to try different cooking ways, so every dishes must use different cooking ways.
• Yazid does not want to taste many dishes made of the same ingredient, so all the ingredients can be used in at most $$$\left\lfloor \frac{k}{2}\right\rfloor$$$ dishes.

$$$\left\lfloor x\right\rfloor$$$ here means the minimum integer that is equal or less than $$$x$$$.

Their needs is easy to realize for Emiya, so he tries to figure out how many ways there are to make a meal? Two meals are different when they have at least one different dish.

Emiya finds you. You should help him calculate the number of ways modulo $$$998,244,353$$$

$$$\bf{Input}$$$

The first line contains two integer $$$n,m$$$, the number of cooking ways and the number of different ingredients.

In the next $$$n$$$ lines ,the $$$j$$$-th number of $$$i$$$-th line is $$$a_{i,j}$$$, the different dishes Emiya can make when using $$$i$$$-th cooking way and $$$j$$$-th ingredient.

$$$\bf{Output}$$$

One integer, the answer modulo $$$998,244,353$$$.

$$$\bf{Constraints}$$$

$$$1 \le n \le 100 ,1 \le m \le 2000 ,0 \le a_{i,j} < 998,244,353$$$

$$$\bf{D2T2\ Partition\ 2s\ 1GB}$$$

$$$\bf{Statement}$$$

In 2048, in the exam hall of The 48th CSP, contestant Little Ming is looking at the first problem. The sample has $$$n$$$ testcases numbered from $$$1$$$ to $$$n$$$. The scale of $$$i$$$-th testcase is $$$a_i$$$.

Little Ming does a brute-force solution. His program needs $$$u^2$$$ seconds to solve a testcases with $$$u$$$ scale. However, after running on a testcases with $$$u$$$ scale, the program will get RE on any testcases with scale strictly less than $$$u$$$. In the sample, $$$a_i$$$ is not always increasing. Little Ming wants to get AC on the sample without reprogramming ,so he use a very natural way: combining some adjacent testcases. The new scale of some combined testcases is the sum of scale of these testcases.

Formally, Little Ming needs to find out some borders $$$1 \le k_1 < k_2 < ... <k_p \le n$$$, making:

When $$$p = 0$$$, it means Little Ming combines all testcases together.

Little Ming does not want to get RE or TLE, so he wants to minimum his program's running time, which means minimizing:

Little Ming loves the problem very much, so he writes this problem and ask you: with given $$$n$$$ and $$$a_i$$$, how to figure out the minimum running time?

$$$\bf{Input}$$$

To avoid much input time, some testcases will be generated in contestants' program.

The first line contains two integer $$$n,type$$$ ,the number of "testcases" and the way of inputting.

• $$$1.$$$ If $$$type = 0$$$, $$$a_i$$$ will be given directly. The second line contains $$$n$$$ integers $$$a_i$$$ separated by space, the scale of every "testcases".
• $$$2.$$$ If $$$type = 1$$$, $$$a_i$$$ will be generated specially, the way of generating is written below. The second line contains six integers $$$x,y,z,b_1,b_2,m$$$. In the next $$$m$$$ line, the $$$i$$$-th line contains three integers $$$p_i,l_i,r_i$$$.

$$$type = 2$$$ only appear on testcases $$$23,24,25$$$. The way of generating is:

Guarantee that $$$n\ge 2$$$. If $$$n>2$$$ ,then $$$\forall\ 3\le i\le n,b_i=(x\times b_{i-1} +y \times b_{i-2} + z) \mod 2^{30}$$$

Guarantee that $$$1 \le p_i \le n ,p_m = n ,p_0 = 0$$$ and $$$\forall\ 0 \le i < m,p_i<p_{i+1}$$$.

For all $$$1 \le j \le m$$$ ,if index $$$i(1 \le i \le n)$$$ satisfies $$$p_{j-1} < i \le p_j$$$, then $$$a_i=(b_i\mod (r_j-l_j+1)) + l_j$$$.

The ways of generating is just to reduce the input time. Standard solution does not rely on it.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constraints}$$$

The problem has $$$25$$$ testcases.

For testcases $$$1\sim 22,2 \le n \le 5 \times10^5,1\le a_i \le 10^6,type=0$$$.

For testcases $$$23\sim25,2 \le n \le 4\times 10^7,1 \le a_i \le 10^9 ,1\le m\le 10^5 ,1 \le l_i \le r_i\le 10^9,0 \le x,y,z,b_1,b_2 < 2^{30},type=1$$$

$$$\bf{D2T3\ The\ Centroid\ of\ a\ Tree\ 3s\ 256MB}$$$

Little Simple is learning discrete mathematics! It's about graph theory today! He makes two notes in class:

• $$$1.$$$ On a tree with $$$n$$$ vertices, there are $$$n-1$$$ undirected edges. There is exactly one simple path between two vertices. Delete a vertex and all edges that connect it, and the tree splits into several sub-trees; delete an edge(not delete vertex it connects, the same below), and the tree splits into exactly two sub-trees.
• $$$2.$$$ For a tree with $$$n$$$ vertices and a vertex $$$c$$$, we call vertex $$$c$$$ the centroid of the tree if after deleting vertex $$$c$$$ ,the vertex numbers of the left trees are all less than $$$\left\lfloor \frac{n}{2} \right\rfloor$$$($$$\left\lfloor x \right\rfloor$$$ here means floor function). For those tree whose vertices is more than one, the number of centroid is only $$$1$$$ or $$$2$$$.

After class, the teacher gives Little Simple a tree $$$S$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. It is Little Simple's homework to figure the sum of two splitting subtrees when cutting every edge, respectively, which is:

In the formula above, $$$E$$$ is the edge set of tree $$$S$$$, $$$(u ,v)$$$ is a edge that connects vertex $$$u$$$ and vertex $$$v$$$. $$$S'_u$$$ and $$$S'_v$$$ are two sub-tree into which tree $$$S$$$ is split after deleting edge $$$(u ,v)$$$.

Little Simple does not think his homework is simple, so he asks you for help.

$$$\bf{Input}$$$

Input contains several testcases

The first line contains a integer $$$T$$$, the number of testcases.

For every testcase:

The first line contains a integer $$$n$$$, the number of vertices.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output one integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le T \le 5,1 \le n \le 299995$$$