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;
        }
    }
    //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;
}