Before the editorial, we are sorry for the big gap between problems C and D.

This was the first round we ever created (except for wxhtzdy).

We are striving to become better problem-setters and create more balanced problems-sets in the future.

Author: wxhtzdy

Prepared by: ognjentesic, AndrewPav, AlphaMale06

#include <bits/stdc++.h>

using namespace std;

int main(){
	int t; //read the number of test cases
	cin >> t;
	while(t--){
		int n, k;
		cin >> n >> k; //read n and k
		bool ys=0; //bool value if true then there exists a subsegment which satisfies the condition, else it doesn't exist
		for(int i=0; i< n; i++){
			int a; //read the i-th element of the array
			cin >> a;
			if(a==k)ys=1; //if the element is equal to k, then the subsegment [i, i] has the most common element equal to k
		}
		if(ys)cout << "YES\n"; //output the answer
		else cout << "NO\n";
	}
}

Author: ognjentesic

Prepared by: ognjentesic, AlphaMale06

#include <bits/stdc++.h>

using namespace std;

int main(){
	int t; //read the number of test cases
	cin >> t;
	while(t--){
		int n; //read n
		cin >> n;
		for(int i=0; i< n; i++)cout << i*2+1 << " "; //write the first n odd numbers in order
		cout << '\n';
	}
}

Author: AlphaMale06

Prepared by: ognjentesic, AlphaMale06

#include <iostream>

using namespace std;

int main(){
	int t; //read the number of test cases
	cin >> t;
	while(t--){
		long long n, x, k; //read n, x, k for each test case
		cin >> n >> x >> k;
		if(2*k>=x*(x+1) && 2*k<=n*(n+1)-(n-x)*(n-x+1)){ //check if k is between the minimum and maximum sum 
			cout << "YES\n";
		}
		else cout << "NO\n";
	}	
}

Author: AlphaMale06

Prepared by: ognjentesic, AlphaMale06

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
	int t; //number of test cases
	cin >> t;
	while(t--){
		int n, k; //read the input
		cin >> n >> k;
		string s;
		cin >> s;
		int a[k]; int b[k];
		for(int i=0; i< k; i++){cin >> a[i]; a[i]--;}
		for(int i=0; i< k; i++){cin >> b[i]; b[i]--;}
		int q;
		cin >> q;
		int cnt[n+1]={0}; //read and preprocess queries
		for(int i=0; i< q; i++){
			int x; cin >> x; cnt[x-1]++;
		}
		string ans="";
		for(int i=0; i<k; i++){ //treat each interval as a seperate test case
			string s1=s.substr(a[i], b[i]-a[i]+1);
			int sum=0;
			int l=a[i];
			int r=b[i];
			for(int j=l; j<=(l+r)/2; j++){
				sum+=cnt[j]+cnt[r-j+l];
				if(sum&1)swap(s1[j-l], s1[r-j]);
			}
			ans+=s1;
		}
		cout << ans << '\n';
	}
}

Author: AndrewPav, AlphaMale06

Prepared by: ognjentesic, AndrewPav, OAleksa, AlphaMale06

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
const int N =200003;
const int bits=30;
int pref[N][bits];
int a[N];
void Buildprefix(int n){ //Builds the prefix sums for each bit
    for(int i=0; i< n; i++){
        for(int j=0; j<30; j++){
            if(a[i]&(1<<j)){
                pref[i+1][j]=pref[i][j]+1;
            }
            else{
                pref[i+1][j]=pref[i][j];
            }
        }
    }
}
void solve(){
    int n;
    cin >> n;
    for(int i=0; i< n; i++){
        cin >> a[i];
    }
    Buildprefix(n);
    int q;
    cin >> q;
    while(q--){
        int l, k;
        cin >> l >> k;
        if(a[l-1]<k){
            cout << -1 << '\n';
            continue;
        }
        int lo=l;
        int hi=n;
        int ans=l;
        while(lo<=hi){
            int s=(lo+hi)/2;
            int num=0;
            for(int j=0; j< bits; j++){
                if(pref[s][j]-pref[l-1][j]==s-l+1){
                    num+=(1<<j);
                }
            }
            if(num>=k){
                lo=s+1;
                ans=max(ans, s);
            }
            else hi=s-1;
        }
        cout << ans << '\n';
    }
}
 
int main(){
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

Author: ognjentesic, AlphaMale06

Prepared by: ognjentesic, AlphaMale06

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int N = 1000003;
map<int, int> powers; //key is a prime number, value is te highest powert
map<int, int> original_divisors; //same as map powers but isn't updated during queries, it's used to reset the powers
int smallest_divisor[N]; //precalculated smallest divisors to make factorization O(logx) 
bool mark[N]; //marks numbers which aren't prime (used for sieve)
ll divisor_count = 1; //the number of divisors (updated during queries)

void prime(){ //calculates the smallers divisor for each number from 1 to N (sieve of erathosetenes)
	smallest_divisor[1]=1;
	smallest_divisor[2]=2;
	for(int i=4; i<N; i+=2){
		mark[i]=true;
		smallest_divisor[i]=2;
	}	
	for(int i=3; i<N; i+=2){
		if(!mark[i]){
			smallest_divisor[i]=i;
			for(ll j = i*1ll*i; j<N; j+=2*i){
				if(!mark[j]){
					smallest_divisor[j]=i;
					mark[j]=1;
				}
			}
		}
	}
}
//a function for factorizing a number (used to process queries and factorize n in the beginning)
//it also updates the highest prime which divides n (powers map), and the number of divisors of n (divisor_count)
void factorize(int x){ 
	int p=0;
	int current_divisor = 1;
	while(x>1){ //while x has non 1 divisors, divide it by it's smallest divisor which isn't 1(smallers divisor if always prime)
		if(smallest_divisor[x]!=current_divisor){
			if(p>0){
				divisor_count/=powers[current_divisor]+1;
				powers[current_divisor]+=p;
				divisor_count*=powers[current_divisor]+1;
			}
			p=1;
			current_divisor=smallest_divisor[x];
		}
		else{
			p++;
		}
		x/=smallest_divisor[x];
	}
	if(p>0){
		divisor_count/=powers[current_divisor]+1;
		powers[current_divisor]+=p;
		divisor_count*=powers[current_divisor]+1;
	}
	return;
}

int main(){
	prime(); //precalculate smallest divisors
	int t;
	cin >> t;
	while(t--){
	    //read n and q
    	int n; int q;
    	cin >> n >> q;
    	//factorize n
    	factorize(n);
    	//since factorize updates the powers map, update the origional_divisors map too
    	for(auto prime : powers){
    		original_divisors[prime.first]=prime.second;
    	}
    	int original_divisor_count = divisor_count; //since factorize updates the divisor_count we update the original_divisor_count too
    	vector<int> queries; //storing previous queries
    	//processing queries
    	while(q--){
    		int query_type;
    		cin >> query_type;
    		if(query_type==1){ //query of type 1 (multiply n by x)
    			int x;
    			cin >> x;
    			factorize(x); //factorize x, update the powers map, and the number of divisors
    			queries.push_back(x); //add x to the list of previous queries
    			ll num=n;
    			for(int query : queries){ //check if the product of all previous queries and n is divisible by d(n)
    				num*=query;
    				num%=divisor_count;
    			}
    			if(num==0){ //if it is the answer is yes else the answer is no
    				cout << "YES\n";
    			}
    			else cout << "NO\n";
    		}
    		else{ //here we should reset everything related to the type 1 query
    			powers.clear(); //clear the powers map and set it to original divisors and powers
    			for(auto original_div : original_divisors){
    				powers[original_div.first]=original_div.second;
    			}
    			divisor_count=original_divisor_count; //restart the divisor_count
    			queries.clear(); //clear the queries (since we only need the queries since the previous type 2 query)
    		}
    	}
    	original_divisors.clear();
    	powers.clear();
    	divisor_count=1;
    	original_divisor_count =1;
    	if(t) cout << "\n";
	}
}

Author: wxhtzdy

Prepared by: ognjentesic, OAleksa, AlphaMale06

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long
const int maxn = 2e5 + 69;
const int k = 19;
const int bits = 30;
vector<int> g[maxn];
int n, q, a[maxn], up[maxn][k], tin[maxn], tout[maxn], timer, d[maxn];
int r[maxn][k];
int bst[maxn][bits];
void dfs(int v, int p, vector<int> b) {
	tin[v] = ++timer;
	up[v][0] = p;
	r[v][0] = a[p];
	d[v] = d[p] + 1;
	for (int i = 0;i < bits;i++) {
		bst[v][i] = b[i];
		if (a[v] & (1 << i))
			b[i] = v;
	}
	for (int i = 1;i < k;i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		r[v][i] = r[v][i - 1] | r[up[v][i - 1]][i - 1];
	}
	for (auto u : g[v]) {
		if (u != p)
			dfs(u, v, b);
	}
	tout[v] = timer;
}

bool is_anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
	if(is_anc(u, v))
		return u;
	else if(is_anc(v, u))
		return v;
	for (int i = k - 1;i >= 0;i--) {
		if (!is_anc(up[u][i], v) && up[u][i] > 0)
			u = up[u][i];
	}
	return up[u][0];
}

int OR(int u, int dis) {
	int res = a[u];
	for (int j = 0;j < bits;j++) {
		if (dis & (1 << j)) {
			res |= r[u][j];
			u = up[u][j];
		}
	}
	return res;
}

int Qry(int u, int v) {
	int lc = lca(u, v);
	return OR(u, d[u] - d[lc]) | OR(v, d[v] - d[lc]);
}

signed main()
{
	int tt = 1;
	cin >> tt;
	while(tt--) {
		cin >> n;
		timer = 0;
		for (int i = 1;i <= n;i++)
            g[i].clear();
		for (int i = 1;i <= n;i++)
			cin >> a[i];
		for (int i = 1;i <= n - 1;i++) {
			int x, y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		vector<int> temp(30, -1);
		dfs(1, 0, temp);
		cin >> q;
		for (int i = 1;i <= q;i++) {
			int x, y;
			cin >> x >> y;
			int LCA = lca(x, y);
			vector<int> t;
			t.push_back(x);
			t.push_back(y);
			for (int i = 0;i < bits;i++) {
				if (bst[x][i] != -1 && is_anc(LCA, bst[x][i]))
					t.push_back(bst[x][i]);
				if (bst[y][i] != -1 && is_anc(LCA, bst[y][i]))
					t.push_back(bst[y][i]);
			}
			int ans =  __builtin_popcount(a[x]) + __builtin_popcount(a[y]);
			for (auto p : t) {
				int x1 = a[x], x2 = a[y];
				x1 |= Qry(x, p);
				x2 |= Qry(y, p);
				ans = max(ans, 1ll * __builtin_popcount(x1) + __builtin_popcount(x2));
			}
			cout << ans << " ";
		}
		cout << "\n";
	}
   return 0;
}