akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
vector<int> switches[110];
signed main(){
    int n,m;cin >> n>> m;
    
    rep(i,m){
        int k;cin >> k;
        rep(j,k){
            int s;cin >> s;
            s--;
            switches[i].push_back(s);
        }
    }
    int p[m];rep(i,m)cin >> p[i];
    auto check = [&](int mask){
        rep(i,m){
            int tmp = 0;
            for(auto s:switches[i]){
                tmp += (mask>>s&1);
            }
            if(tmp%2 != p[i])return false;
        }
        return true;
    };
    int ret = 0;
    rep(mask,1<<n){
        ret += check(mask);
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <string.h>

#define debug 0

int main()
{
	int n,i;
	char buf[3];
	char w[40][8];
	int firstadr;
	int k,j,ans;
	int test[5] = {5,7,5,7,7};
	short int len[40];
	while(1){
		scanf("%d",&n);
		if( n==0 ) break;
		for( i=0 ; i<n ;i++ ){
			scanf("%s",w[i]);
			len[i] = strlen(w[i]);
		}
		int flag = 0;
		for( i = 0 ; i < n ; i++) {
			for( j=i,k=0,ans=0 ; j<n; j++){
				ans += len[j];
				if(ans == test[k]){
					ans=0;
					k++;
					if( k == 5 ){
						flag = 1;
						firstadr = i+1;
						break;
					}
				}else if( ans > test[k] ){
					break;
				}
			}
			if( flag == 1 ){
				printf("%d\n",firstadr);
				break;
			}
		}
					
	}
	
	return 0;
}


Measured memory_bytes: 2144
a, b = list(map(int, input().split()))
def gcd(a, b):
  if a < b:
    a, b = b, a
  else:
    pass
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)
  
print(a * b // gcd(a, b))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;

int main() {
  int sum = 0;
  int N;
  cin >> N;
  for(int i = N;i;i /= 10){
    sum += i % 10;
  }
  if(N % sum == 0){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int t=sc.nextInt();
		int[][] dp=new int[n+1][t+3001];
		State[] ss=new State[n];
		for(int i=0; i<n; i++){
			ss[i]=new State(sc.nextInt(),sc.nextInt());
		}
		Arrays.sort(ss);
		for(int i=1; i<=n; i++){
			for(int j=1; j<=t+3000; j++){
				if(j-ss[i-1].a>=t){
					break;
				}
				if(j<ss[i-1].a){
					dp[i][j]=dp[i-1][j];
					continue;
				}
				dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-ss[i-1].a]+ss[i-1].b);
			}
		}
		long ans=0;
		for(int i=0; i<=t+3000; i++){
			ans=Math.max(ans,dp[n][i]);
		}
		System.out.println(ans);
	}
	static class State implements Comparable<State>{
		int a,b;
		State(int a,int b){
			this.a=a;
			this.b=b;
		}
		@Override
 		 public int compareTo(State s){
    		return this.a - s.a;
  		}
	}
}


Measured memory_bytes: 131000
// Need start
#include<iostream>
// Need end
using namespace std;

// Copy start
template<typename T, long long MOD_VALUE>
class ModInt {
    static constexpr long long MOD = MOD_VALUE;
    private:
        T value_;
    public:
        ModInt() {}
        ModInt(const T& value):value_(value % MOD) {}
        ModInt& operator+=(const ModInt& x)  {value_ += x.value_; if (value_ >= MOD) value_ -= MOD; return *this;}
        ModInt& operator-=(const ModInt& x) {if (value_ < x.value_) value_ += MOD; value_ -= x.value_; return *this;}
        ModInt& operator*=(const ModInt& x) {value_ = (value_ * x.value_) % MOD; return *this;}
        const ModInt operator+(const ModInt& x) const {return ModInt(*this) += x;}
        const ModInt operator-(const ModInt& x) const {return ModInt(*this) -= x;}
        const ModInt operator*(const ModInt& x) const {return ModInt(*this) *= x;}
        static ModInt modpow(ModInt x, long long y) {ModInt z = 1; while (y > 0) {if (y & 1) {z *= x;}x *= x; y /= 2;} return z;}
        ModInt& operator/=(const ModInt& x) {return *this *= modpow(x, MOD - 2);}
        const ModInt operator/(const ModInt& x) const {return *this /= x;}
        ModInt operator++(int) {ModInt tmp(*this); value_ = (value_ + 1 == MOD ? 0 : value_ + 1); return tmp;}
        ModInt operator--(int) {ModInt tmp(*this); value_ = (value_ - 1 < 0 ? MOD - 1 : value_ - 1); return tmp;}
        friend istream& operator>>(istream& stream, ModInt& x) {stream >> x.value_; x.value_ %= MOD; return stream;}
        friend ostream& operator<<(ostream& stream, const ModInt& x) {stream << x.value_; return stream;}
};
// Copy end

#include<vector>

using ll = long long;
using mint = ModInt<ll, 1000000007>;

mint dfs(int k, const vector<vector<int>>& graph, int now, int from) {
    mint can_use_color_num;
    if (from == -1) {
        can_use_color_num = k - 1;
    }
    else {
        can_use_color_num = k - 2;
    }
    if (k < graph[now].size()) {
        return 0;
    }
    mint case_num = 1;
    for (int node : graph[now]) {
        if (node == from) continue;
        case_num *= can_use_color_num;
        can_use_color_num--;
    }
    for (int node : graph[now]) {
        if (node == from) continue;
        case_num *= dfs(k, graph, node, now);
    }
    return case_num;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // This sample is AtCoder Beginners Contest 133 E
    int N, K;
    cin >> N >> K;
    vector<vector<int>> graph(N);
    int A, B;
    for (int i = 0; i < N - 1; ++i) {
        cin >> A >> B;
        --A, --B;
        graph[A].push_back(B);
        graph[B].push_back(A);
    }
    mint ans = mint(K) * dfs(K, graph, 0, -1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11648
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main()
{
    long long n,i,k,j;
    double max=0.0,x,total,a[200005],y;
    cin>>n>>k;
    for(i=1;i<=k;i++)
    {
        cin>>a[i];
        max=max+((a[i]*1.0*(a[i]+1.0))/2.0)/(a[i]*1.0);
    }
    total=max;
    for(j=k+1;j<=n;j++)
    {
        cin>>a[j];
        x=((a[j-k]*(a[j-k]+1.0)*1.0)/2.0)/(a[j-k]*1.0);
        y=((a[j]*1.0*(a[j]+1.0))/2.0)/(a[j]*1.0);
        total-=x;
        total+=y;
        if(total>max)
        {
            max=total;
        }        
    }
    cout<<fixed<<showpoint<<setprecision(12)<<max<<endl;
    return 0;
}

Measured memory_bytes: 5248
#include <string>
#include <time.h>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <utility>
#include <iostream>
#include <cmath>
#include <deque>

#define MOD 998244353
#define pii pair<ll,ll>
#define X first
#define Y second
#define mp make_pair

typedef long long ll;
using namespace std;
#define MAXN 1488228
ll x, y, n;
ll a[350005], b[350005], dp[200500][4];
ll ans;
set<pii> f;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        f.insert(mp(b[i], i));
    }
    ll ans = 0;
    while (!f.empty()) {
        auto it = f.end();
        it--;
        ll pos = it->Y;
        f.erase(it);
        if (b[pos] == a[pos]) {
            continue;
        }
        ll sum = b[(pos-1+n)%n] + b[(pos+1)%n];
        ll diff = b[pos] - a[pos];
        if (diff < 0 || sum >= b[pos]) {
            cout << -1 << endl;
            return 0;
        }
        if (a[pos] >= sum && diff % sum != 0) {
            cout << -1 << endl;
            return 0;
        }
        if (a[pos] >= sum ) {
            ans += diff / sum;
            b[pos] = a[pos];
            continue;
        }
        ans += b[pos] / sum;
        b[pos] %= sum;
        f.insert(mp(b[pos], pos));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 17280
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)

n,m=map(int,input().split())
s=input();t=input()
c=0
l=lcm(n,m)
a=l//n;b=l//m

for i in range(n):
  if (i*a)%b==0:
    if s[i]==t[i*a//b]:c+=1
    else:
      break
if c==(l//lcm(a,b)):print(l)
else:print(-1)

Measured memory_bytes: 5344
// D - Div Game
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// // 素数と個数を求める
// vector<pair<ll,ll>> factorize(ll n){
//   vector<pair<ll,ll>> res;
//   for(ll i=2L; i*i<=n; ++i){
//     if (n%i) continue;
//     res.emplace_back(i,0);
//     while(n%i == 0){ n /= i; res.back().second++; }
//   }
//   if(n != 1) res.emplace_back(n,1L);
//   return res;
// }

int main(){
	ll N; cin>>N;
	// vector<pair<ll,ll>> P = factorize(N);
	ll ans = 0;
	// for(auto x:P)
	// for(ll p=2, pi=p, i=1; i<=c; i++, p*=p){
	// 	if(N%pi) continue;
	// 	N /= pi;
	// 	ans++;
	// }

	ll n = N;
  for(ll p=2; p*p<=n; ++p){
    if (N%p) continue;
		ll c = 0;
   	while(n%p == 0){ n /= p; c++; }
		// cout<<" p "<<p;
		// cout<<" c "<<c;
		// cout<<"\n";
		for(ll pi=p, i=1; i<=c; i++, pi*=p){
			if(N%pi) continue;
			N /= pi;
			ans++;
		}
  }
  if(n != 1) ans++;
  // if(N != 1) res.emplace_back(N,1L);

	cout<< ans <<endl;
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

int main(){
    string s;
    map<char, int> mp;
    for(char c = 'a'; c <= 'z'; c++){
        mp[c] = 0;
    }
    while(getline(cin, s)){
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        for(int i = 0; i < s.size(); i++){
            mp[s[i]]++;
        }
    }
    for(char c = 'a'; c <= 'z'; c++){
        cout << c << " " << ":" << " " << mp[c] << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
#include <cstdio>
#include <vector>

using namespace std;

int n;
char T[200005];

vector<int> inc[12][550000];
int ans[12][550000];
int psum[200005];

int pwr3[15];

int main()
{
    pwr3[0] = 1;
    for (int i = 1; i < 15; i++) pwr3[i] = 3 * pwr3[i-1];
    scanf("%d", &n);
    scanf("%s", T + 1);
    int tsiz = 0;
    for (int i = 1; T[i]; i++) {
        tsiz = i;
        psum[i] = psum[i-1] + (T[i] == 'S' ? 1 : 0);
    }
    for (int s = 0; s < 3; s++) {
        int cur = s;
        for (int i = 1; T[i]; i++) {
            if (T[i] == 'S') {
                if (cur) cur = 3 - cur;
            } else {
                cur++;
                if (cur == 3) {
                    cur = 0; inc[0][s].push_back(i);
                }
            }
        }
        ans[0][s] = cur;
    }
    for (int dig = 1; dig < n; dig++) {
        for (int high = 0; high < 3; high++) {
            for (int low = 0; low < pwr3[dig]; low++) {
                int num = high * pwr3[dig] + low;
                int lastinc = 0;
                int curhigh = high;
                for (int i = 0; i < inc[dig-1][low].size(); i++) {
                    int curinc = inc[dig-1][low][i];
                    if ((psum[curinc] - psum[lastinc]) % 2) {
                        if (curhigh) curhigh = 3 - curhigh;
                    }
                    curhigh++;
                    if (curhigh == 3) {
                        curhigh = 0; inc[dig][num].push_back(curinc);
                    }
                    lastinc = curinc;
                }
                if ((psum[tsiz] - psum[lastinc]) % 2) {
                    if (curhigh) curhigh = 3 - curhigh;
                }
                ans[dig][num] = curhigh * pwr3[dig] + ans[dig-1][low];
            }
        }
    }
    for (int i = 0; i < pwr3[n]; i++) {
        printf("%d ", ans[n-1][i]);
    }
    return 0;
}


Measured memory_bytes: 186300
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> k(n);
    vector<vector<bool>> a(n,vector<bool>(m,false));
    rep(i,n){
        int ki; cin >> ki;
        k[i] = ki;
        rep(j,ki){
            int aij; cin >> aij; aij--;
            a[i][aij] = true;
        }
    }

    int ans = 0;
    rep(j,m){
        bool bj = true;
        rep(i,n){
            if(!a[i][j]){
                bj = false;
                break;
            }
        }
        if(bj) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#ひどいアルゴリズムができてしまった

def conv(a,b)
  if b > a/2
    b = a - b
  end
  ans = 1
  div = 1
  b.times do |i|
    ans *= a - i
    div *= (i+1)
  end
  ans = ans / div
end

def calc(n,k)
  if n.to_s.length < k
    0
  elsif  ( n.to_s =~ /[^9]/ ) == nil
    9**k*conv(n.to_s.length,k)
  elsif k == 0
    1
  elsif n < 10
    n
  else
    #最初の桁が0の場合　+ 最初の桁が0以外の場合
    calc(10 ** (n.to_s.length-1) -1,k) + (n.to_s[0].to_i - 1) * calc(10 ** (n.to_s.length-1) -1,k-1) + calc(n.to_s[1..-1].to_i,k-1)
  end
end

n = gets.to_i
k = gets.to_i
puts calc(n,k)

Measured memory_bytes: 1916
D = gets.to_i
C,*S = (0..D).map {gets.split.map &:to_i}
V,L,M,N = (0..25).to_a,[-1]*26,2,10
T = L*N
I = V.select {|i| C[i]<1}
1 < I.size && S.each {|s|
  z=99; I.each {|i| if i<z; z=i elsif s[z]<s[i]; s[z] = 0; z = i else s[i] = 0 end }
}
def F(d,n)
  n = D-d if n > D-d
  o,s = (N-n)*26, S[d]
  v = V.max_by(M) {|i| T[o+i] = n*C[i]*(d-L[i]) + s[i] }
  x = T[o+(i=v[0])]
  n > 1 && (i = v.max_by {|i|
    l,L[i] = L[i],d
    c = T[o+i] + (F(d+1,n-1)>>5)
    L[i] = l
    x < c ? x=c : c
  })
  (x<<5) + i
end
D.times { p 1 + i=F(_1,N)&31; L[i]=_1 }

Measured memory_bytes: 14612
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18


map<int, int> primes(int n) {

	map<int, int> m;

	for (int i = 2; i*i <= n; i++) {
		while (n%i == 0) {
			m[i]++;
			n /= i;
		}
	}

	if (n != 1)m[n]++;

	return m;

}

int main() {

	int n; cin >> n;
	cout << n << ":";

	for (auto &i : primes(n)) {

		while (i.second--) {
			cout << " " << i.first;
		}

	}

	cout << endl;

	return 0;
}



Measured memory_bytes: 3096
N, W = map(int, input().split())
wlis, vlis = [0], [0]
for i in range(N):
    w, v = map(int, input().split())
    wlis.append(w)
    vlis.append(v)
dp = [[0]*(W+1) for _ in range(N+2)]
for i in range(1, N+1):
    for j in range(W+1):
        if wlis[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wlis[i]]+vlis[i])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
print(dp[N+1][W])

Measured memory_bytes: 120556
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;
const ll MOD = 1000000007;

ll rsw[400010];

int main() {
	for (int i = 0;i < 400010;i++)rsw[i] = 0;
	ll N, K;
	cin >> N >> K;

	vector<ll> P(N);
	for (int i = 0;i < N;i++) {
		cin >> P[i];
		P[i]++;
	}

	for (int i = 0;i < N;i++) {
		rsw[i + 1] = rsw[i] + P[i];
	}

	ll ans = 0;
	for (int i = 0;i < N;i++) {
		ans = max(rsw[i + K] - rsw[i], ans);
	}
	double ad = (double)ans / 2;
	printf("%.10f\n", ad);
}

Measured memory_bytes: 4992
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

int main(void){
	ll x;
	cin >> x;

	ll a = 100;
	ll ans = 0;
	while(a < x){
		ans++;
		a *= 1.01;
	}
	co(ans);

	return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>

using namespace std;


void pln()
{
	cout << endl;
	return;
}

void print(int x)
{
	cout << x << endl;
	return;
}

int ri() {
	int x;
	cin >> x;
	return x;
}

int main(void)
{
	int R = ri();
	int G = ri();

	int ans = 2*G - R;

	print(ans);
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main(){
	int n,m;
	cin >> n >> m;
	UnionFind uf(n);
	int a,b,c;
	for(int i=0;i<m;++i){
		cin >> a >> b >> c;
		a--;b--;
		uf.unite(a,b);
	}
	set<int> se;
	for(int i=0;i<n;++i){
		se.insert(uf.root(i));
	}
	
	cout << se.size() <<endl;
	
	return 0;
}



Measured memory_bytes: 5376
_n, x = gets.split.map(&:to_i)
cities = gets.split.map(&:to_i)
distances = cities.map { |city| (city - x).abs }

def gcd_of_two(a, b)
  small, large = [a, b].sort
  if small == 0
    return large
  else
    gcd_of_two(small, large % small)
  end
end

def gcd_of_many(array)
  current = array.shift
  until array.empty?
    following = array.shift
    current = gcd_of_two(current, following)
  end
  return current
end

puts gcd_of_many(distances)


Measured memory_bytes: 11908
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
  long long q, h, s, d, n;
  scanf("%lld%lld%lld%lld%lld", &q, &h, &s, &d, &n);
  h = min(q * 2, h);
  s = min(h * 2, s);
  d = min(s * 2, d);
  printf("%lld\n", n % 2 * s + n / 2 * d);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int H, W;

char m[22][22] = {};
queue<pair<int,int>> q;

int calc_max_distance( int sx, int sy ){
	int d[22][22] = {};
	int max_dist = -1;
	q.push({sx,sy}); d[sy][sx] = 1;
	
	while ( !q.empty() ){
		auto p = q.front();
		q.pop();
		int x = p.first;
		int y = p.second;
		
		int dist = d[y][x];
		if ( max_dist < dist )
			max_dist = dist;
		auto f = [&](int x, int y, int newdist){
			if ( m[y][x] == '.' && d[y][x] == 0 ){
				q.push({x,y});
				d[y][x] = newdist;
			}
		};
		f(x+1,y, dist+1);
		f(x-1,y, dist+1);
		f(x,y+1, dist+1);
		f(x,y-1, dist+1);
	}
	
/*
	cout << sx << " " << sy << " " << max_dist << endl;
	for ( int y = 1; y <= H; y++ ){
		for ( int x = 1; x <= W; x++ )
			cout << d[y][x];
		cout << endl;
	}
	cout << "-----\n";
*/
	
	return max_dist;
}



int main(){
	cin >> H >> W;
	for ( int y = 1; y <= H; y++ ){
		string S;
		cin >> S;
		for ( int x = 1; x <= W; x++ ){
			m[y][x] = S[x-1];
		}
	}
	
	int result = -1;
	for ( int y = 1; y <= H; y++ ){
		for ( int x = 1; x <= W; x++ ){
			if ( m[y][x] == '.' ){
				int d = calc_max_distance(x,y);
				if ( d > result )
					result = d;
			}
		}
	}
	
	cout << (result-1) << endl;
	
	return 0;
}




Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace AtCoderTest
{
    class Program
    {
        static void Main()
        {
            const int inf = (int)1e9;
            int N = int.Parse(Console.ReadLine().Trim());
            List<List<int>> abc = new List<List<int>>();
            List<List<int>> dp = new List<List<int>>();
            for (int i = 0; i <= N; i++) {
                List<int> bar = new List<int>();
                for (int k = 0; k < 3; k++) {
                    bar.Add(0);
                }
                dp.Add(bar);
            }
            

            for (int i = 0; i < N; i++) {
                List<int> foo = new List<int>();
                var buf = Console.ReadLine().Trim().Split();
                foreach (var bf in buf) foo.Add(int.Parse(bf));
                abc.Add(foo);
            }

            int ans = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < 3; j++) {
                    for(int k = 0; k < 3; k++)
                    {
                        if (j == k) continue;
                        int tmp = dp[i][j] + abc[i][k];
                        if (tmp > dp[i + 1][k]) dp[i + 1][k] = tmp;
                    }
                }
            }

            for (int j = 0; j < 3; j++) {
                if (dp[N][j] > ans) ans = dp[N][j];
            }
            Console.WriteLine(ans);


        }


    }
}

Measured memory_bytes: 66432
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define per(i, n) for(int i = (n)-1; i >= 0; --i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);
#define ppp(a) (cout << (a) << endl); 

using ll = long long;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

constexpr int MOD = 1e9+7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr double phi = (1+sqrt(5))/2;
constexpr double pi = 3.14159265358979323846264338327950288;

ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
inline void Yes(){puts("Yes");}
inline void No(){puts("No");}
inline void Judge(bool b){b?Yes():No();}
inline void YES(){puts("YES");}
inline void NO(){puts("NO");}
inline void JUDGE(bool b){b?YES():NO();}
inline ll powmod(ll b, ll e, ll mod){ll r=1;while(e>0){if(e&1)r=(r%mod)*(b%mod)%mod;b=(b%mod)*(b%mod)%mod;e>>=1;}return r;}
inline double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
inline double d2r(double d){return d*pi/180;}
inline double r2d(double r){return r*180/pi;}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {s<<'[';for(size_t i=0;i<v.size();++i){s<<v[i];if(i < v.size()-1)s<<", ";}s<<']';return s;}

int main(){

    int n, m;
    scanf("%d%d", &n, &m);

    ppp(n^m); 




    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int H, W;
	cin >> H >> W;

	string A[100];
	rep(i, H) cin >> A[i];

	string S = "#";
	string S0;
	rep(i, W) S0 += "#";

	co(S + S0 + S);
	rep(i, H) co(S + A[i] + S);
	co(S + S0 + S);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<set>
#include<algorithm>
#include <queue>

using ll =  long long;
#define rep(i,n) for(int i= 0; i< (n); i++)
using namespace std;
using Graph = vector<vector<int>>;

int main(){


    int n;
    string s;
    cin >> n >> s;
    int cnt=0;
    rep(i,n){
        if(s.substr(i,3)=="ABC")
            cnt++;
    }
    cout << cnt << endl;
    
     return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
	const char *comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}

int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

int a[2005];
int tot[2005],till[2005];
void solve() {
	int n,k;
	cin>>n>>k;
	fr(i,1,n) {
		cin>>a[i];
		fr(j,1,i-1)
			if(a[i]<a[j])
				till[i]++;
	}
	fr(i,1,n)
		fr(j,1,n)
			if(a[i]>a[j])
				tot[j]++;
	int ans=0;
	fr(i,1,n) {
		ans+=k*till[i];
		ans+=(tot[i]*(((k*(k-1))/2)%mod))%mod;
		ans%=mod;
	}
	cout<<ans<<endl;


}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(2);
	int t=1;
//	cin>>t;
	while(t--)
		solve();
#ifdef rd
//	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const int maxn = 2e5+5;

int main() {
	int x,y;
	scanf("%d%d",&x,&y);
	for(int i = 0;i <= 1005;++i){
		int tx = (double)i*0.08;
		int ty = (double)i*0.1;
		if(tx == x && ty == y){
			printf("%d\n",i);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <deque>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> istream& operator>>(istream &is, pair<S, T> &p){ return is >> p.first >> p.second; }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ return os << "[" << p.first << ", " << p.second << "]"; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define For1(i, n) for(int i = 1; i <= (n); i ++)
#define Rof(i, n) for(int i = (n)-1; i >= 0; i --)
#define Rof1(i, n) for(int i = (n); i >= 1; i --)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)
#define Return(x) { Cout(x); return 0; }

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(string, a);
    int n = (int)a.size();
    unordered_map<char, int> m;
    For(i, n) m[a[i]] ++;
    
    ll ans = (ll)n*(n-1)/2 + 1;
    for(auto &e : m){
        int m = e.second;
        ans -= (ll)m*(m-1)/2;
    }
    Cout(ans);
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

ll lcm (ll a, ll b) {
    return a / __gcd(a,b) * b; 
}
int main(){
 int n;
 cin >> n;
 vector<ll> t(n);
 REP(i,n) cin >> t[i];
 ll ans = 1;
 REP(i,n) ans = lcm(ans,t[i]);

 cout << ans << endl; 
  return 0;
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 200000000000
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()

bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll A,B,C;
    cin >>A>>B>>C;

    if(A==B && B==C){
        cout << "No" << endl;
    }else if(A!=B && A!=C && C!=B){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    
    


    return 0;
    

}

Measured memory_bytes: 3600
#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define FOF(i,a,b) for(int i=a;i< b;i++)
using namespace std;
const int N=22,M=100100,P=1e9+7;
int n,m,T,ans;
int a[N],iv[M],fc[M],vf[M],sz[M],dc[M],f[N][M];
int C(int x,int y){return x<0||y<0||x<y?0:1ll*fc[x]*vf[x-y]%P*vf[y]%P;}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);T=(1<<n)-1;
	FOR(i,1,m) scanf("%d",&a[i]),a[i]--;
	iv[1]=fc[0]=vf[0]=dc[0]=1;
	FOR(i,2,T) iv[i]=1ll*(P-P/i)*iv[P%i]%P;
	FOR(i,1,T) fc[i]=1ll*fc[i-1]*i%P,vf[i]=1ll*vf[i-1]*iv[i]%P;
	f[m][0]=1;
	ROF(i,m,1){
		FOR(j,0,T)if(f[i][j]){
			(f[i-1][j]+=f[i][j])%=P;
			FOF(k,0,n)if(!(1<<k&j))
				(f[i-1][1<<k|j]+=1ll*f[i][j]*C(T-a[i]-j,(1<<k)-1)%P)%=P;
		}
	}
	FOR(i,0,T) dc[i]=1ll*dc[i-(i&-i)]*vf[i&-i]%P;
	FOR(i,0,T){
		sz[i]=sz[i>>1]+(i&1);
		(ans+=1ll*(sz[i]&1?P-1:1)*f[0][i]%P*fc[T^i]%P*dc[T^i]%P)%=P;
	}
	FOF(i,0,n) ans=2ll*ans*fc[1<<i]%P;
	cout<<ans<<'\n';
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) ((int)((c).size()))
#define st first
#define nd second
#define pb push_back

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<bool> vb;
typedef long long ll;

bool dp[101];

void solve(){
    int n;
    cin>>n;
    dp[0] = true;
    dp[4] = true;
    dp[7] = true;
    FOR(i,8,n+1)
        dp[i] = dp[i-4] || dp[i-7];
    cout << (dp[n] ? "Yes\n" : "No\n");
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x, y;
    while(1){
        cin >> x >> y;
        if(x == 0 && y == 0){
            return 0;
        }
        if(x > y){
            cout << y << " " << x << endl;
        }
        else{
            cout << x << " " << y << endl;
        }
    }
}


Measured memory_bytes: 3012
//============================================================================
// Name        : test.cpp
// Author      : tree
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;
const int mol = 1000000007;


int main() {
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	int x = 0,y = 0;
	if(a == 5)	x ++;
	else if(a == 7)	y ++;

	if(b == 5)	x ++;
	else if(b == 7)	y ++;

	if(c == 5)	x ++;
	else if(c == 7)	y ++;

	if(x == 2 && y == 1)	printf("YES\n");
	else					printf("NO\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int x,a,b,c,cnt;
int main()
{
    cin >> a >> b >> c >> x;
    for (int k = 0;k <= a;k++)
        for (int i = 0;i <= b;i++)
            for (int j = 0;j <= c;j++)
                if ((500 * k + 100 * i + 50 * j) == x)
                    cnt ++;
    cout << cnt;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long int
using namespace std;
bool comp(pair<int,int>a,pair<int,int > b){
    return a.first < b.first;
}
signed main() {
	//code
	vector<pair<int,int> > v;
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
	    int x;
	    cin >> x;
	    v.push_back(make_pair(x,i));
	}
	sort(v.begin(),v.end(),comp);
	for(int i=0;i<n;i++){
	    cout << v[i].second<<" ";
	}
	return 0;
}

Measured memory_bytes: 2544
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int t,a,k;
cin>>t>>a>>k;
for(int i=0;i<k;i++)
{
	if(i%2==0)
	{
		if(t%2==0)
		{
			a=a+t/2;
			t=t/2;
		}
		else
		{
			--t;
			a=a+t/2;
			t=t/2;
		}
	}
	else
	{
			if(a%2==0)
		{
			t=t+a/2;
			a=a/2;
		}
		else
		{
			--a;
			t=t+a/2;
			a=a/2;
		}
	}
}
cout<<t<<" "<<a;
return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main() {
	int n;
	scanf("%d", &n);
	int p[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
	}
	int c = 0;
	for (int i = 0; i < n; i++) {
		if (p[i] != i+1) {
			c++;
		}
	}
	if ((c == 2) || (c == 0)) printf("YES");
	else printf("NO");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  string S;
  cin >> N >> S;

  vector<set<int>> vec(26);

  rep(i, N){
    vec[S[i]-'a'].insert(i);
  }

  vector<int> ans;

  int Q;
  cin >> Q;

  rep(q, Q){

    int qtype;
    cin >> qtype;

    if(qtype == 1){

      int iq;
      char cq;
      
      cin >> iq >> cq;
      iq--;

      rep(i, 26){
        auto itr = vec[i].find(iq);
        if(itr != vec[i].end()){
          vec[i].erase(itr);
        }
      }

      vec[cq-'a'].insert(iq);

    }else{

      int cnt = 0;

      int l, r;
      cin >> l >> r;
      l--;
      r--;

      rep(i, 26){
        if(vec[i].lower_bound(l) != vec[i].upper_bound(r)){
          cnt++;
        }
      }
      ans.push_back(cnt);
    }
  }

  rep(t, ans.size()){
    cout << ans[t] << endl;
  }


  return 0;
}


Measured memory_bytes: 26396
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

int main(int argc, char **argv)
{
	ll N, M; cin >> N >> M;
	vector<string> A(N), B(M);
	for (ll i = 0; i < N; ++i) cin >> A[i];
	for (ll i = 0; i < M; ++i) cin >> B[i];

	bool ok;
	for (ll h = 0; h < N-M+1; ++h)
	{
		for (ll w = 0; w < N-M+1; ++w)
		{
			ok = true;
			for (ll hh = 0; hh < M; ++hh)
			{
				for (ll ww = 0; ww < M; ++ww)
				{
					if (A[h+hh][w+ww] != B[hh][ww])
						ok = false;
				}
			}
			if (ok)
				goto exit;
		}
	}
 exit:
	std::cout << (ok ? "Yes" : "No") << std::endl;
}


Measured memory_bytes: 256
n, m, L = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
st = [list(map(int, input().split())) for _ in range(q)]

d = [[float('inf') for _ in range(n)] for _ in range(n)]
for a, b, c in abc:
    if c > L:
        continue
    d[a-1][b-1] = c
    d[b-1][a-1] = c

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            if i == k or d[i][k] > L:
                continue
            for j in range(n):
                if i == j:
                    continue
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

warshall_floyd(d)

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif d[i][j] <= L:
            d[i][j] = 1
        else:
            d[i][j] = float('inf')

warshall_floyd(d)

for s, t in st:
    if d[s-1][t-1] == float('inf'):
        print(-1)
    else:
        print(d[s-1][t-1] - 1)


Measured memory_bytes: 125912
//
//  main.cpp
//  AOJ-1172-ans
//
//  Created by Kenta Kodera on 2017/06/18.
//  Copyright ?? 2017??´ Kenta Kodera. All rights reserved.


#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
#include <ctype.h> // isdigit
#include <cassert>
using namespace std;

int main(){
  
  vector<bool> sieve(300000,true);
  sieve[0]=false, sieve[1]=false;
  for(int i=0; i<=sqrt(300000); i++){
    if(sieve[i]){
      for(int j=2; i*j<300000; j++){
        sieve[i*j] = false;
      }
    }
  }
  
  int n;
  while(cin >>n, n){
    int ans=0;
    for(int i=n+1; i<=2*n; i++){
      if(sieve[i]) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3120
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
 
//#define PI 3.141592653589
 
using namespace std;
 
 
 
int main()
{
    int w_score[10];
    int k_score[10];
    int w_sum, k_sum;
     
    for (int i=0; i<10; i++)
    {
        cin >> w_score[i];
    }
    for (int i=0; i<10; i++)
    {
        cin >> k_score[i];
    }
     
    sort(w_score, w_score+10);
    sort(k_score, k_score+10);
    w_sum = w_score[9] + w_score[8] + w_score[7];
    k_sum = k_score[9] + k_score[8] + k_score[7];
     
    cout << w_sum << " " << k_sum << endl;
     
    /*
    for (int i=0; i<10; i++)
    {
        cout << w_score[i] << endl;
    }
    */
     
     
    return 0;
}

Measured memory_bytes: 3140
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;

const int maxn = 55;
int f[maxn], g[maxn][maxn];
int a[maxn], b[maxn], n;
ll ans;

bool need(int i, int k) {
	if (g[i][b[i]]) return 0;
	memset(f, 0, sizeof f);
	rep (j, b[i], a[i]) f[j] = g[i][j];
	per (j, k-1, b[i]+1)
		rep (t, 0, 50) f[t%j] |= f[t];
	return !f[b[i]];
}

void check(int k) {
	int flag = 0;
	rep (i, 1, n)
		if (need(i, k)) {
			flag = 1; break;
		}
	if (!flag) return;
	ans += 1ll << k;
	rep (i, 1, n) rep (j, b[i], 50)
		g[i][j%k] |= g[i][j];
}

bool judge() {
	rep (i, 1, n)
		if (!g[i][b[i]]) return 0;
	return 1;
}

int main() {
	scanf("%d", &n);
	rep (i, 1, n) scanf("%d", &a[i]);
	rep (i, 1, n) scanf("%d", &b[i]);
	rep (i, 1, n) if (a[i] < b[i]) 
		return puts("-1"), 0;
	rep (i, 1, n) g[i][a[i]] = 1;
	per (i, 50, 1) check(i);
	if (!judge()) puts("-1");
	else cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int n,x,t,a;

    scanf("%d%d%d",&n,&x,&t);

    if(n%x!=0){
        a = n/x+1;
    }else{
        a = n/x;
    }

    printf("%d",a*t);
    return 0;
}

Measured memory_bytes: 1728
#include<stdio.h>
int main(){
    int x,y,z,d;
    scanf("%d%d",&x,&y);
    
    if(x<y){
        while((d=y%x)!= 0){
            y=x;
            x=d;
        }
        printf("%d\n",x);
    }
    else{
    while((d=x%y)!=0){
        x=y;
        y=d;
    }
    printf("%d\n",y);
    }
    return 0;
}



Measured memory_bytes: 2136
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        String s = sc.next();
        String t = sc.next();

        int ans = 0;
        for (int i = 0; i < s.length(); i++){
            if(s.charAt(i)!=t.charAt(i)) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 32128
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod2 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 2e9

int main()
{
    int l,r,d;
    cin >> l >> r >> d;
    int ans=0;
    for(int i=l;i<=r;i++)
        if(i%d==0)
            ans+=1;
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;


int main() {
    string s;
    cin >> s;
    int len = s.size();
    int sum = 0;
    for(int i = 0; i < len; i++) {
    	sum = (sum + s[i] - '0') % 9;
	}
	if(sum % 9 == 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define MAX (ll)(5e3 + 4)
#define MOD (ll)(1e9 + 7)
#define PI (double)(3.14159265)
#define IO ios_base :: sync_with_stdio (false), cin.tie (nullptr);

using namespace std;
using ll = long long;
using ld = long double;

int main () {
	int n, nn;
	cin >> n;
	int ar[n], br[n], aa[n * 3], pr[n * 3] = {};
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> br[i];
	}
	for (int i = 0; i < n; i++) {
		aa[i] = br[(i + 1) % n] ^ br[i % n];
	}
	aa[n] = -1;
	for (int i = 0; i < 2 * n - 1; i++) {
		aa[n + 1 + i] = ar[(i + 1) % n] ^ ar[i % n];
	}
	pr[0] = 0;
	nn = n + 1 + 2 * n - 1;
	for (int i = 1; i < nn; i++) {
		int ind = i - 1;
		while (aa[pr[ind]] != aa[i]) {
			if (pr[ind] - 1 < 0) {
				break;
			}
			ind = pr[ind] - 1;
		}
		if (aa[pr[ind]] == aa[i]) {
			pr[i] = pr[ind] + 1;
		}
	}
	vector<int> ve;
	for (int i = n + 1; i < nn; i++) {
		if (pr[i] == n) {
			ve.push_back (i - n - 1);
		}
	}
	for (int x : ve) {
		cout << x - n + 1 << " " << (ar[x - n + 1] ^ br[0]) << "\n";
	}
}
			
			
			
	


Measured memory_bytes: 10612
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n; cin >> n;
	int64_t a[n]; rep(i,n) cin >> a[i];
	int64_t ans0 = 0;
	for(int i = 0; i < n; ++i){
		if(i % 2 == 0) ans0 += a[i];
		else ans0 -= a[i];
	}
	int64_t ans[n]; ans[0] = ans0;
	for(int i = 1; i < n; ++i) {
		ans[i] = 2 * a[i - 1] - ans[i - 1];
	}
	for(int i = 0; i < n; ++i) {
		cout << ans[i] << (i == n - 1 ? "\n" : " ");
	}
	return 0;
}

Measured memory_bytes: 2816