akhauriyash/Code-Regression huggingface dataset:
// AOJ 0294 Catch a Thief
// 2018.2.14 
// Lengauer-Tarjan algorithm? 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100002
#define MAGIC 150
int par[MAX], m[MAX];
int parent[MAX], vertex[MAX];
int semi[MAX], idom[MAX], U[MAX];
int **b_to, b_hi[MAX];
int *g_to[MAX], g_hi[MAX], _g_hi[MAX];
int *r_to[MAX], r_hi[MAX], _r_hi[MAX];
int tbl[300002][2];

int find(int v) { int r;
	if (par[v] == v) return v;
	r = find(par[v]);
	if (semi[m[v]] > semi[m[par[v]]]) m[v] = m[par[v]];
	return par[v] = r;
}
int eval(int v) { find(v); return m[v]; }
void link(int x, int y) { par[y] = x; }

void tree(int n)
{
	int id, i, j, w, u, v;
	int *q; int top;
	
	for (i = 0; i < n; i++) par[i] = m[i] = i, semi[i] = -1;

	q = malloc(150000*sizeof(int));
	id = 0, q[0] = 0, top = 1;
	while (top) {
		v = q[--top];
		if (semi[v] >= 0) continue;
		semi[v] = id;
		vertex[id++] = v;
		for (i = g_hi[v]-1; i >= 0; i--) {
			u = g_to[v][i];
			if (semi[u] < 0) {
				parent[u] = v;
				q[top++] = u;
			}
		}
	}
	free(q);

	b_to = malloc(n*sizeof(int *));
	b_to[0] = malloc(25000*sizeof(int));
	for (i = 1; i < n; i++) b_to[i] = malloc(MAGIC*sizeof(int));

	b_to[0][0] = 0, u = 25000;
	for (i = 1; i < n; i++) for (j = 0; j < MAGIC; j++) {
		b_to[i][j] = u, u += MAGIC;
	}

	for (i = n-1; i > 0; i--) {
		w = vertex[i];
		for (j = 0; j < r_hi[w]; j++) {
			v = r_to[w][j];
			u = eval(v);
			if (semi[w] > semi[u]) semi[w] = semi[u];
		}
		v = vertex[semi[w]];
		b_to[v][b_hi[v]++] = w;
		u = parent[w];
		for (j = 0; j < b_hi[u]; j++) {
			v = b_to[u][j];
			U[v] = eval(v);
		}
		b_hi[u] = 0;
		link(u, w);
	}
//	free(b_to);

	for (i = 1; i < n; i++) {
		w = vertex[i];
		u = U[w];
		if (semi[w] == semi[u]) idom[w] = semi[w];
		else idom[w] = idom[u];
	}
	for (i = 1; i < n; i++) {
		w = vertex[i];
		idom[w] = vertex[idom[w]];
	}
}

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
	int n, m, i, s, t, q, r;
	
	n = in(), m = in();
	for (i = 0; i < m; i++) {
		s = in()-1, t = in()-1;
		tbl[i][0] = s, tbl[i][1] = t;
		_g_hi[s]++, _r_hi[t]++;
	}
	for (i = 0; i < n; i++) {
		g_to[i] = malloc(_g_hi[i] << 2);
		r_to[i] = malloc(_r_hi[i] << 2);
	}
	for (i = 0; i < m; i++) {
		s = tbl[i][0], t = tbl[i][1];
		g_to[s][g_hi[s]++] = t;
		r_to[t][r_hi[t]++] = s;
	}

	tree(n);

	q = in();
	while (q--) {
		r = in()-1;
		if (!idom[r]) printf("%d\n", r+1);
		else          printf("%d\n", idom[r]+1);
	}
	return 0;
}


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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> v(n + 1), w(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> v[i] >> w[i];
  }
  auto f = [&](const auto& idx) {
    int m = size(idx);
    vector<pair<int, int>> res(1);
    res.reserve(1 << m);
    for (int t = 0; t < m; ++t) {
      int i = idx[t];
      for (int bt = 0; bt < 1 << t; ++bt) {
        res.emplace_back(res[bt].first + w[i], res[bt].second + v[i]);
      }
      inplace_merge(begin(res), begin(res) + (1 << t), end(res));
    }
    for (int bt = 1; bt < 1 << m; ++bt) {
      res[bt].second = max(res[bt].second, res[bt - 1].second);
    }
    return res;
  };
  constexpr int th = 4096;
  vector<vector<pair<int, int>>> pre(th);
  for (int i = th / 2; i <= min(th - 1, n); ++i) {
    vector<int> idx;
    for (int j = i; j; j >>= 1) {
      idx.push_back(j);
    }
    pre[i] = f(idx);
  }
  int q;
  cin >> q;
  while (q--) {
    int i, l;
    cin >> i >> l;
    if (i < th) {
      vector<int> idx;
      for (; i; i >>= 1) {
        idx.push_back(i);
      }
      auto a = f(idx);
      int res = prev(lower_bound(begin(a), end(a), make_pair(l + 1, 0)))->second;
      cout << res << '\n';
    } else {
      vector<int> idx;
      for (; i >= th; i >>= 1) {
        idx.push_back(i);
      }
      int res = 0;
      for (auto [sw, sv] : f(idx)) {
        if (sw > l) break;
        auto it = prev(lower_bound(begin(pre[i]), end(pre[i]), make_pair(l - sw + 1, 0)));
        res = max(res, it->second + sv);
      }
      cout << res << '\n';
    }
  }
}


Measured memory_bytes: 71036
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1e9+7;
const ll  longinf = 1LL<<60;
const int mod=1e9+7;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
  string s;
  cin>>s;
  int n=s.size();
  map<int,int> mp;
  if(n!=26){
    rep(i,n)mp[s[i]-'a']++;
    cout<<s;
    rep(i,26){
      if(mp[i]==0){
        char c='a'+i;
        cout<<c<<endl;
        return 0;
        }
      }
    }
  if(s=="zyxwvutsrqponmlkjihgfedcba"){
    cout<<-1<<endl;
    return 0;
    }
  vector<int> v;
  rep(i,n)v.push_back(s[i]-'a');
  next_permutation(v.begin(),v.end());
  cout<<(char)(v[0]+'a');
  rep(i,n){
    if(v[i]+'a'==s[i])cout<<(char)(v[i+1]+'a');
    else break;
    }
    
  return 0;
  }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
 string s;
 cin>>s;
 int ans=0,count=0;
 for(int i = 0; i < s.size(); i++ ){
   if(s.at(i)=='A'||s.at(i)=='C'||s.at(i)=='G'||s.at(i)=='T'){
     count++;
     ans=max(ans,count);
   }
   else{
     ans=max(ans,count);
     count=0;
   } 
 } 
 cout<<ans<<endl;
}

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

#define MOD 1000000007

class mint {
	public:
		int i;

		mint() : i(0) {}

		template<class T>
			mint(T x) {
				i = int(x % MOD);
				if (i < 0) i += MOD;
			}

		mint operator+(mint x) {
			return i + x.i;
		}

		mint operator-(mint x) {
			return i - x.i;
		}

		mint operator*(mint x) {
			return (long long)i * x.i;
		}

		mint operator/(mint x) {
			return (long long)i * x.pow(MOD - 2).i;
		}

		mint inv() {
			return pow(MOD - 2);
		}

		template<class T>
			mint pow(T p) {
				long long r = 1;
				long long t = i;
				for(; p > 0; p >>= 1) {
					if (p & 1) r = r * t % MOD;
					t = t * t % MOD;
				}
				return r;
			}

		template<class T1, class T2>
			static mint pow(T1 a, T2 b) {
				long long r = 1;
				long long t = (long long)(a % MOD);
				for(; b > 0; b >>= 1) {
					if (b & 1) r = r * t % MOD;
					t = t * t % MOD;
				}
				return r;
			}

		mint& operator+=(mint x) {
			i = (i + x.i) % MOD;
			return *this;
		}

		mint& operator-=(mint x) {
			i = i - x.i;
			if (i < 0) i += MOD;
			return *this;
		}

		mint& operator*=(mint x) {
			i = (int)((long long)i * x.i % MOD);
			return *this;
		}

		mint& operator/=(mint x) {
			i = (long long)i * x.pow(MOD - 2).i % MOD;
			return *this;
		}
};

std::ostream& operator<<(std::ostream& os, const mint& m) {
	return os << m.i;
}

int n, k;
vector<mint> merge(vector<mint>& v1, vector<mint>& v2) {
	vector<mint> res(k+1);
	for(int i = 1; i <= k; i++) {
		res[i] = v1[i] * v2[i];
	}
	return res;
}

struct divs_ {
	vector<vector<int>> d;
	divs_(int n): d(n+1) {
		for(int i = 1; i <= n; i++) {
			//if (!is_prime(i)) continue;
			for(int j = i; j <= n; j += i) {
				d[j].push_back(i);
			}
		}
	}
	vector<int>& operator[](int n) {
		return d[n];
	}
} divs(100000);

int main() {
	cin >> n >> k;
	int d = 1;
	while(n >> d) d++;
	vector<vector<mint>> veach(d);
	veach[0] = vector<mint>(k+1);
	for(int i = 1; i <= k; i++) {
		veach[0][i] = k / i;
	}
	for(int i = 1; i < d; i++) {
		veach[i] = merge(veach[i-1], veach[i-1]);
	}
	vector<mint> res(k+1, 1);
	for(int i = 0; i < d; i++) {
		if ((n >> i)&1) {
			res = merge(res, veach[i]);
		}
	}
	for(int i = k; i > 0; i--) {
		for(int p: divs[i]) {
			if (p == i) continue;
			res[p] -= res[i];
		}
	}
	mint ans = 0;
	for(int i = 1; i <= k; i++) {
		ans += res[i] * i;
	}
	cout << ans << endl;
}



Measured memory_bytes: 21008
N = int(input())
def f(a,b):
    res = 0
    for i in [a,b]:
        res = max(len(str(i)),res)
    return res
ans = float("inf")
for a in range(1,N+1):
    if a*a>N:break
    if N%a==0:
        ans = min(ans, f(a,N//a))
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int(void) {
  int num;
  scanf("%d", &num);
  return num;
}

#define POWER2_MAX 32

int main(void) {
    int num = get_int();
    int sign = (num>=0) ? 1 : -1;
    int anum = abs(num);
    static int map[POWER2_MAX];
    int bit;
    for(bit = 0; bit < POWER2_MAX; bit++) {
        if(!(anum & (1<<bit))) continue;
        int bit_sign = (bit%2) ? -1 : 1;
        map[bit] = bit_sign * sign;
    }

    // carry
    int msb = 0;
    for(bit = 0; bit < POWER2_MAX; bit++) {
        if(map[bit]==-1) {
            map[bit] = 1;
            map[bit+1] += 1;
        } else if (map[bit]==2) {
            map[bit] = 0;
            map[bit+1] -= 1;
        } else if (map[bit] == -2) {
            map[bit] = 0;
            map[bit+1] += 1;
        }
        if(map[bit]==1) msb = bit;
    }

    for(bit = msb; bit >= 0; bit--) {
        putchar('0' + map[bit]);
    }
    putchar('\n');
    return 0;
}

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

int main(){
  int A,B;
  long C;
  cin >> A >> B >> C;
  
  int cnt=0;
  for(int coin=0;coin<C;coin+=A){
    cnt++;
    if(cnt%7==0) coin+=B;
  }
  cout << cnt << endl;
}



Measured memory_bytes: 3112
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int a, b;
	
	cin >> a >> b;
	
	if (a <= 8 && b <= 8) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}
	
	return (0);
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
list=[]
for i in range(0,n+1):
    s1=int(i%10)
    s2=int((i-s1)%100/10)
    s3=int((i-s1-10*s2)%1000/100)
    s4=int((i-s1-10*s2-100*s3)%10000/1000)
    s5=int((i-s1-10*s2-100*s3-1000*s4)%100000/10000)
    if s1+s2+s3+s4+s5>=a and s1+s2+s3+s4+s5<=b:
        list.append(i)
print(sum(list))

Measured memory_bytes: 9152
N, Q = map(int, input().split())
S = input()

nums = [0] * N
count = 0
for i in range(len(S)-1):
    nums[i] = count
    if S[i] == "A" and S[i+1] == "C":
        count += 1
nums[-1] = count

for _ in range(Q):
    l,r = map(int, input().split())
    print(nums[r-1] - nums[l-1])

Measured memory_bytes: 6084
#define _USE_MATH_DEFINES
#include <cmath>
#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <numeric>
#include <array>
#include <float.h>
#include <memory>
#include <functional>
#include <iomanip>
#include <random>
#include <map>
#include <set>
#include <boost/lexical_cast.hpp>

using namespace std;


using ULL = decltype(0ull);
constexpr auto DIV = 1000000007ull;
constexpr auto MAX = numeric_limits<ULL>::max();

int dp[1000000 + 5];

int main() {
  ULL N, K;
  cin >> N >> K;
  cout << K*(ULL)pow(K - 1, N - 1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string s;cin>>s;
	if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I'){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		List<Integer> list = new ArrayList<>();
		while (!list.contains(n)) {
			
			list.add(n);
			if (n % 2 == 0) n /= 2;
			else n = 3 * n + 1;
			
		}
		
		System.out.println(list.size() + 1);
	}
}

Measured memory_bytes: 21204
<?php
    fscanf(STDIN, "%d", $n);
    fscanf(STDIN, "%d", $k);
    $ball_pos = explode(" ", trim(fgets(STDIN)));
    $middle = intval($k / 2);
    $dist = 0;
    foreach ($ball_pos as $value) {
        if ($value > $middle) {
            $dist += ($k - $value) * 2;
        } else {
            $dist += $value * 2;
        }
    }
    echo $dist . "\n";
?>


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

using namespace std;

int main()
{
    double x,y,w,h;
    long long c=0;

    cin>>w>>h>>x>>y;

//    d=w/2;

    if(x==w/2 && y==h/2)
    {

        c++;
        //printf("%.6f %d",a,c);

    }
     double a=(h/2)*1.0*w;
    printf("%.6lf %lld",a,c);
   /* else
    {
        float a=y*x*1.0;

        c=abs(d-x);
         printf("%.6f %d",a,c);

    }*/
    return 0;
}


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

using namespace std;

#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define re return
#define endl '\n'

using ll = long long;
using ull = unsigned long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using ld = long double;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }

const ld pi = 4 * atan(1.);
const double inf = 1e18 + 7; 
const int N = 3e5 + 17;

int n, m, k;
vii q;

const int lg = 20;
int t[N * lg], L[N * lg], R[N * lg];
int cnt = 1;
int root[N];

int build(int v, int tl, int tr) {
    if (tl == tr) re v;
    int c = (tl + tr) >> 1;
    L[v] = build(++cnt, tl, c);
    R[v] = build(++cnt, c + 1, tr);
    re v;
}

int upd(int v, int tl, int tr, int x, int pos) {   
    int r = ++cnt;
    R[r] = R[v];
    L[r] = L[v];
    t[r] = t[v];
    if (tl == tr) { t[r] += x; return r; }
    int c = (tl + tr) >> 1;
    if (pos > c) R[r] = upd(R[r], c + 1, tr, x, pos);
    else L[r] = upd(L[r], tl, c, x, pos);
    t[r] = t[L[r]] + t[R[r]];
    return r;
}

int get(int v, int tl, int tr, int l, int r) {
    if (!v || tl > r || l > tr) return 0;
    if (l <= tl && tr <= r) return t[v];
    int c = (tl + tr) >> 1;
    return get(L[v], tl, c, l, r) + get(R[v], c + 1, tr, l, r);
}

int func(int x, int y) {
    re get(root[x], 0, m, x, y);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int l, r; 
        cin >> l >> r;
        q.pb({l, r});
    }
    sort(all(q));
    root[0] = build(cnt, 0, m);
    int l = 1;
    for (auto p : q) {
        while (l < p.fi) {
            l++;
            root[l] = root[l - 1];
        }
        root[l] = upd(root[l], 0, m, 1, p.se);
    }
    while (l <= m) {
        l++;
        root[l] = root[l - 1];
    }
    for (int i = 1; i <= m; i++) {
        int cur = 0;
        for (int j = 0; j <= m; j += i)
            cur += func(j, min(j + i - 1, m));
        cout << cur << '\n';
    }
}

Measured memory_bytes: 70024
local mmi, mma = math.min, math.max
local n, k = io.read("*n", "*n")
local v = {}
for i = 1, n do
  v[i] = io.read("*n")
end
local leftsum = {v[1]}
for i = 2, n do
  leftsum[i] = leftsum[i - 1] + v[i]
end
local rightsum = {}
for i = 1, n do rightsum[i] = 0 end
rightsum[n] = v[n]
for i = n - 1, 1, -1 do
  rightsum[i] = rightsum[i + 1] + v[i]
end
local dpleft = {}
for i = 1, n do
  dpleft[i] = {}
  local val = leftsum[i]
  local tmp = {}
  for j = 1, i do
    tmp[j] = v[j]
  end
  table.sort(tmp)
  for j = 1, i do
    val = val - tmp[j]
    dpleft[i][j] = val
  end
end

local dpright = {}
for i = 1, n do
  dpright[i] = {}
  local val = rightsum[i]
  local tmp = {}
  for j = i, n do
    tmp[j - i + 1] = v[j]
  end
  table.sort(tmp)
  for j = 1, n + 1 - i do
    val = val - tmp[j]
    dpright[i][j] = val
  end
end

for i = 1, n do
  dpleft[i][1] = mma(dpleft[i][1], leftsum[i])
  for j = 2, #dpleft[i] do
    dpleft[i][j] = mma(dpleft[i][j], dpleft[i][j - 1])
  end
  if i < n then
    for j = 1, #dpleft[i] do
      dpleft[i + 1][j] = mma(dpleft[i + 1][j], dpleft[i][j])
    end
  end
end

for i = n, 1, -1 do
  dpright[i][1] = mma(dpright[i][1], rightsum[i])
  for j = 2, #dpright[i] do
    dpright[i][j] = mma(dpright[i][j], dpright[i][j - 1])
  end
  if 1 < i then
    for j = 1, #dpright[i] do
      dpright[i - 1][j] = mma(dpright[i - 1][j], dpright[i][j])
    end
  end
end
local ret = 0
do
  for i = n, 1, -1 do
    local z = n + 1 - i
    if z < k then
      ret = mma(ret, dpright[i][mmi(k - z, z)])
    elseif z == k then
      ret = mma(ret, rightsum[i])
    else
      break
    end
  end
end
for il = 1, n do
  do
    if il <= k then
      ret = mma(ret, leftsum[il])
    end
    local rightuse = k - il
    for i = n, il + 1, -1 do
      local z = n + 1 - i
      if z < rightuse then
        ret = mma(ret, leftsum[il] + dpright[i][mmi(rightuse - z, z)])
      elseif z == rightuse then
        ret = mma(ret, leftsum[il] + rightsum[i])
      else
        break
      end
    end
  end
  for j = 1, il do
    local leftuse = il + j
    if leftuse <= k then
      ret = mma(ret, dpleft[il][j])
    end
    local rightuse = k - leftuse
    for i = n, il + 1, -1 do
      local z = n + 1 - i
      if z < rightuse then
        ret = mma(ret, dpleft[il][j] + dpright[i][mmi(rightuse - z, z)])
      elseif z == rightuse then
        ret = mma(ret, dpleft[il][j] + rightsum[i])
      else
        break
      end
    end
  end
end
print(ret)


Measured memory_bytes: 376
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s,t;
  int count=0;
  cin>>s>>t;
  for(int i=0;i<3;i++){
    if(s.at(i)==t.at(i)){
      count++;
    }
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int a[3], i, j, t;
	scanf("%d %d %d", &a[0], &a[1], &a[2]);

	for (i = 0; i < 3; i ++) {
		for (j = 2; j > i; j --) {
			if (a[j - 1] > a[j]) {
				t = a[j];
				a[j] = a[j-1];
				a[j-1] = t;
			}
		}
	}

	printf("%d", (a[2]-a[1])+(a[1]-a[0]));
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long int ll;
typedef pair<int, int> P;

int n, m;
double a[200];

int main()
{
  cin >> n >> m;
  double sum = 0;
  rep(i, n)
  {
    cin >> a[i];
    sum += a[i];
  }
  sort(a, a + n, greater<int>());
  
  rep(i, m)
  {
    if(a[i] < (double)(sum / (double)(4 * m)))
    {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
struct UnionFind {
  vector<long> par; 
  vector<long> siz; 
  UnionFind(long N) : par(N),siz(N,1) { 
    rep(i,N) par[i] = i;
  }
  void init(long n) {
    par.resize(n);
    siz.assign(n, 1LL);
    for (long i = 0; i < n; ++i) par[i] = i;
  }
  long root(long x) { 
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(long x, long y) {
    long rx = root(x); 
    long ry = root(y);
    if (rx == ry) return;  
    if (siz[rx] < siz[ry]) swap(rx, ry);
    siz[rx] += siz[ry];
    par[ry] = rx;  
  }
  bool same(long x, long y) {
    long rx = root(x);
    long ry = root(y);
    return rx == ry;
  }
  
  long size(long x) { 
    return siz[root(x)];
  }
};

int main() {
  long n,m;
  cin >> n>>m;
  vector<long>p(n);
  rep(i,n){
    cin>>p.at(i);
    p.at(i)--;
  }
  UnionFind tree(n);
  vector<long>a(m),b(m);
  rep(i,m){
    cin>>a.at(i)>>b.at(i);
    a.at(i)--;
    b.at(i)--;
    tree.unite(a.at(i),b.at(i));
  }
  int ans=0;
  rep(i,n){
    if(tree.same(i,p.at(i))){
      ans++;
    }
  }
  cout<<ans<<endl;
}




Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;
 
const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;
 
int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int n;
    LL d,x,y;
    cin>>n>>d;
    d = d * d;
 
    int ans = 0;
    loop(i,0,n)
    {
        cin>>x>>y;
        if((x * x) + (y * y) <= d) ++ans;
    }
 
    cout<<ans<<'\n';
 
    
 
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  ll n, m, x;
  cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll>> a(n, vector<ll>(m));
  REP(i, n){
    cin >> c[i];
    REP(j, m) cin >> a[i][j];
  }

  ll ans = 1ll<<60;
  REP(i, 1ll<<n){
    ll t = 0;
    vector<ll> v(m, 0);
    REP(j, n){
      if(i>>j & 1){
        t += c[j];
        REP(k, m) v[k] += a[j][k];
      }
    }
    bool ok = true;
    REP(j, m) if(v[j] < x) ok = false;
    if(ok) chmin(ans, t);
    
  }
  if(ans != 1ll<<60) cout << ans << endl;
  else cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main()
{
    int a, b;
    cin >> a >> b;
    int ans = 0;
    int outlet = 1;
    while (outlet < b)
    {
        outlet --;
        outlet += a;
        ++ans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define ll long long
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define SORTD(a) sort(a.rbegin(), a.rend());
#define UNIQUE(a) unique(a.begin(), a.end())
#define INF 1000000000000000000
#define INT_MAX 2147483647

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <utility>
#include <ios>
#include <iomanip>
#include <sstream>
#include <map>

using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const ll mod = 1e9+7;

int main() {
	ll n;
	cin >> n;
	vl a(n);
	REP(i, n) {
		cin >> a[i];
	}

	ll sum = 0;
	REP(j, n) {
		sum += a[j % n] * pow(-1, j % 2);
	}
	cout << sum << " ";

	FOR(i, 1, n) {
		sum = 2 * a[i - 1] - sum;
		cout << sum << " ";
	}
	cout << endl;
}

Measured memory_bytes: 2048
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	char a, b;
	cin >> a >> b;
	if(a == 'H' && b == 'H'){
		cout << "H" << endl;
	}
	else if(a == 'H' && b == 'D'){
		cout << "D" << endl;
	}
	else if(a == 'D' && b == 'H'){
		cout << "D" << endl;
	}
	else if(a == 'D' && b == 'D'){
		cout << "H" << endl;
	}
	return 0;
}

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

struct Edge 
{
    int v, idx;
};

const int N = 1e5 + 7;
vector<Edge> G[N];
int color[N];
bool taken[N];

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

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back({v, i});
        G[v].push_back({u, i});
    }

    int res = 0;

    for (int i = 1; i <= n; ++i) {
        res = max(res, (int)G[i].size());

        for (auto e : G[i]) {
            taken[color[e.idx]] = true;
        }

        int col = 1;
        for (auto e : G[i]) {
            if (!color[e.idx]) {
                while (taken[col])  
                    ++col;
                color[e.idx] = col++;
            }
        }

        for (auto e : G[i]) {
            taken[color[e.idx]] = false;
        }
    }

    printf("%d\n", res);
    for (int i = 0; i < n - 1; ++i)
        printf("%d\n", color[i]);

    return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define f first
#define s second

typedef pair<int, int> P;

int main(){
  int m, n;
  P search[210], star[1010];
  while(cin >> m, m){
    for(int i = 0 ; i < m ; i++) cin >> search[i].f >> search[i].s;
    cin >> n;
    for(int i = 0 ; i < n ; i++) cin >> star[i].f >> star[i].s;
    int x, y;
    for(int i = 0 ; i < n ; i++){
      x = star[i].f - search[0].f;
      y = star[i].s - search[0].s;
      int cnt = 0;
      
      for(int j = 0 ; j < m ; j++){
	for(int k = 0 ; k < n ; k++){
	  if(search[j].f + x == star[k].f && search[j].s + y == star[k].s) cnt++;
	}
      }
      if(cnt == m) break;
    }
    cout << x << ' ' << y << endl;
  }
  return 0;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807


int h,w,d,a,q;
map<int,pair<int,int>> m;
queue<int> ans;

signed main() {
    cin >> h >> w >> d;
    rep(i,h) rep(j,w) cin >> a,m[a] = mp(i,j);
    int memo[w*h+1] = {};
    rep1(i,(w*h)/d) rep(j,min(d,w*h-i*d+1)) {
        int f = (i-1)*d+j,s = i*d+j;
        memo[s] = memo[f] + abs(m[s].fi - m[f].fi) + abs(m[s].se - m[f].se);
    }
    cin >> q;
    rep(i,q) {
        int l,r;
        cin >> l >> r;
        ans.push(memo[r]-memo[l]);
    }
    rep(i,q) cout << ans.front() << endl,ans.pop();
}


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

typedef pair<int, int> P;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  if (k <= a)
    cout << k << endl;
  else if (k <= a+b)
    cout << a << endl;
  else
    cout << a-(k-a-b) << endl;
}


Measured memory_bytes: 3640
a=int(input())
ans =0


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
b = factorization(a)
for i in range(len(b)):
    count=0
    c = b[i][1]

    for j in range(1,40):
        if c - j >= 0:
            c -= j
            count += 1
        else:
            ans += count
            break
if a ==1:
    print(0)
else:
    print(ans)


Measured memory_bytes: 9432
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <sstream>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, a) RREP(i, a, 0)
#define RREP(i, a, b) for(int i = a; i >= b; --i)
#define repll(i, a) REPLL(i, 0, a)
#define REPLL(i, a, b) for(ll i = a; i < b; ++i)
#define rrepll(i, a) RREPLL(i, a, 0)
#define RREPLL(i, a, b) for(ll i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<int, P> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+18 + 10;

int n;
ll fib[50];

int main(){
	fib[0] = fib[1] = 1;
	REP(i, 2, 50)fib[i] = fib[i - 1] + fib[i - 2];

	std::cin >> n;
	std::cout << fib[n] << std::endl;

	return 0;
}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1
long long int mod = 1000000007;

int main() {

    ll N,M;
    Scll2(N,M);

    vector<ll> x(N),y(M);

    Rep(i,N){
        Scll(x[i]);
    }
    Rep(i,M){
        Scll(y[i]);
    }

    sort(x.begin(),x.end());
    sort(y.begin(),y.end());

    ll ansx = 0;
    ll ansy = 0;
    ll ans = 0;
    N--,M--;

    Rep(i,N){
        ansx += ( x[i+1] - x[i] ) * (N-i)*(i+1);
        ansx %= mod;
    }
    Rep(i,M){
        ansy += ( y[i+1] - y[i] ) * (M-i)*(i+1);
        ansy %= mod;
    }


    printf ("%lld\n", ans = ansx * ansy % mod );


    return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e3 + 5;
const int INF = 0x7f7f7f7f;
const ll p = 998244353;
#define DEBUG(x) cout << x << '\n'

int n, s, t, f[MAXN];
ll f_pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % p)
        if(b & 1) res = res * a % p;
    return res;
}
int main(){
#ifdef Irene
    freopen("in.txt", "r", stdin);
#endif // Irene
    ios::sync_with_stdio(false);

    cin >> n >> s;
    f[0] = f_pow(2, n);
    ll inv2 = f_pow(2, p - 2);
    for(int i = 1; i <= n; i++){
        cin >> t;
        for(int j = s - t; j >= 0; j--)
            f[j+t] = (f[j+t] + f[j] * inv2) % p;
    }
    cout << f[s];
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define range(i,a,n) for(int i=a;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define INF (int)(1e9)

int h,w,k;

int clear(vvi&f, int combo){
    int del=0;
    range(i,1,h+1)range(j,1,w+2-k){
        if(f[i][j]==-1) continue;
        if(f[i][j]==f[i][j+1] and f[i][j]==f[i][j+2])  del+=f[i][j]*3,f[i][j]=f[i][j+1]=f[i][j+2]=0,j+=2;
        if(f[i][j]==f[i][j+1] and k==2) del+=f[i][j]*2, f[i][j]=f[i][j+1]=0, j++;
    }
    return del<<combo;
}
void fall(vvi&f){
    vvi nf(h+2,vi(w+2,-1));
    range(j,1,w+1){
        int p=h;
        for(int i=h;i>=1;i--){
            if(f[i][j]>0) nf[p--][j]=f[i][j];
        }
    }
    f=nf;
}

int solve(vvi f, int i, int j){
    f[i][j]=0;
    fall(f);
    int score=0,add=0,ren=0;
    while((add=clear(f,ren++))!=0){
        score+=add;
        fall(f);
    }
    return score;
}

int main(){
    cin>>h>>w>>k;
    if(k>=4){
        cout<<0<<endl;
        return 0;
    }
    vvi f(h+2,vi(w+2,-1));
    range(i,1,h+1)range(j,1,w+1){char c; cin>>c; f[i][j]=c-'0';}
    int ans=0;
    range(i,1,h+1)range(j,1,w+1) ans=max(ans,solve(f,i,j));
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 1000005
#define eps 1e-10
#define Pi acos(-1.0)
int n;
long long ans,m;
int a[N],b[N];
bool f[N];
char s[N];
inline bool C(LL x1)
{
	LL ret=0;
	for(int i=1;i<=n;i++)
	{
		LL x2=x1/b[n-i+1];
		if(a[i]>x2)
			ret+=a[i]-x2;
	}
	return ret<=m;
}
int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	LL l=-1,r=(LL)1e12+1;
	while(l+1<r)
	{
		LL mid=(l+r)/2;
		if(C(mid))
			r=mid;
		else
			l=mid;
	}
	printf("%lld",r);
}

Measured memory_bytes: 6528
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2")  //Enable AVX

using namespace std;

using ll = long long;

#define mp make_pair

const int p = 1000000007;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*const int N = 1000000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> a(n);
    for (int i = 0; i<n; i++) if (s[i]=='o') a[i] = 0; else a[i] = 1;

    for (int x = 0; x<=1; x++)
        for (int y = 0; y<=1; y++)
        {
            vector<int> b(n);
            b[0] = x; b[1] = y;
            for (int i = 2; i<n; i++) b[i] = (b[i-1] + b[i-2] + a[i-1])%2;
            bool check = true;
            for (int i = 0; i<n; i++) if ((b[i] + b[(i+1)%n] + b[(i+2)%n] + a[(i+1)%n])%2) check = false;
            if (check)
            {
                for (int i = 0; i<n; i++) if (b[i]==0) cout<<'S'; else cout<<'W';
                return 0;
            }
        }
    cout<<-1;

}

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

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

    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }

    int mi = A[0], ans = 1;
    for(int i = 1; i < n; i++){
        if(mi >= A[i]){
            ans++;
            mi = A[i];
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


int main(){
    int d[20];
    for(int i = 0;i < 12;i++){
        cin >> d[i];
    }
    sort(d,d+12);
    for(int i = 0;i < 3;i++){
        int c = d[i*4];
        for(int j = 0;j < 4;j++){
            if(d[i*4+j] != c){
                cout << "no" << endl;
                return 0;
            }
        }
    }
    cout << "yes" << endl;
}


Measured memory_bytes: 3140
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi p(n);
    cin >> p;
    int ans = 0;
    rep2(i,1,n-1){
        if((p[i-1]<p[i] && p[i]<p[i+1]) || (p[i-1]>p[i] && p[i]>p[i+1])) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys

s = sys.stdin.readline().rstrip()
k = int(sys.stdin.readline())
cnt = 0
i = 0
l = len(s)
if len(set(s)) == 1:
  print(int(l*k/2))
  exit()
while i < l-1:
  if s[i] == s[i+1]:
    cnt += 1
    i += 2
    continue
  i += 1
cnt1 = 0
i1 = 0
s *= 2
while i1 < l*2-1:
  if s[i1] == s[i1+1]:
    cnt1 += 1
    i1 += 2
    continue
  i1 += 1
print((cnt1 - cnt)*(k-1) + cnt)



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

using ll = long long;

constexpr ll inf = 1e10;

int main() {
    int n; cin >> n;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }

    const int p = (x[0] + y[0]) & 1;
    for(int i = 0; i < n; ++i) {
        if(p != ((x[i] + y[i]) & 1)) {
            cout << -1 << endl;
            return 0;
        }
        if(p == 0) {
            y[i] += 1;
        }
    }

    for(int i = 0; i < n; ++i) {
        const int X = x[i] + y[i], Y = x[i] - y[i];
        x[i] = X, y[i] = Y;
    }
    const int m = 31 + (p == 0);
    vector<int> d(m);
    for(int i = 30; i >= 0; --i) {
        d[i] = 1 << i;
    }
    if(p == 0) d[31] = 1;
    vector<string> w(n);
    const string dir = "LDUR";
    for(int i = 0; i < n; ++i) {
        ll cur_x = x[i], cur_y = y[i];
        for(int j = 30; j >= 0; --j) {
            int idx = 0;
            if(abs(cur_x - d[j]) < (1LL << j)) {
                idx |= 0b10;
                cur_x -= d[j];
            } else {
                cur_x += d[j];
            }
            if(abs(cur_y - d[j]) < (1LL << j)) {
                idx |= 0b01;
                cur_y -= d[j];
            } else {
                cur_y += d[j];
            }
            w[i] += dir[idx];
        }
        reverse(begin(w[i]), end(w[i]));
        if(p == 0) {
            w[i] += 'D';
        }
    }

    cout << m << endl;
    for(int i = 0; i < m; ++i) {
        cout << d[i] << " \n"[i + 1 == m];
    }
    for(auto const& s : w) {
        cout << s << endl;
    }
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


int main() {
	char c; cin >> c;
	cout << (char)(c + 1) << endl;
	return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += n/i - (n % i == 0);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

char maze[7][7];
char maze2[7][7];
int main(){
  int h,w,k;
  cin >> h >> w >> k;
  int ans = 0;
  rep(i,h){
    rep(j,w){
      cin >> maze[i][j];
      maze2[i][j] = maze[i][j];
    }
  }
  
  for (int bit1 = 0; bit1 < (1 << h);bit1++){
    for (int bit2 = 0; bit2 < (1 << w); bit2++){
      for (int j = 0; j < w;j++){
        if (bit2 & (1 << j)){
          for (int y = 0; y < h;y++){
            maze[y][j] = 'R';
          }
        }
      }
      for (int i = 0; i < h;i++){
        if (bit1 & (1 << i) ){
          for (int x = 0;x < w;x++){
            maze[i][x] = 'R';
          }
        } 
      }
    int cnt = 0;
    rep(e,h){
      rep(r,w){
      if (maze[e][r] == '#') cnt++;
      //cout << maze[e][r];
      }
      //cout << endl;
    }
    if (cnt == k) ans++;
    //cout << endl;
    rep(e,h)rep(r,w)maze[e][r] = maze2[e][r];
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3620
#include "bits/stdc++.h"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#include<memory>

#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
using Graph=vector<vector<int>>;
	
#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}
//1. maskの部分集合を列挙する
	// 	a. i==0を評価しない
	// 	for(int i=mask; i>0; i=(i-1)&mask) {
	// 	}

	// b. i==0を評価する
	// 	for(int i=mask; i>=0; i--) {
	// 		i&=mask;
	// 	}
// 2. maskを含む集合を列挙する

// 少し目的は変わりますが同じようなやり方でできる処理が、maskを含む集合の列挙です。

// 	for(int i=mask; i<(1<<n); i=(i+1)|mask) {
// 	}

	
using ll = long long int;

int answer=0;
int K,N;
int dfs(Graph&g,int now,int from=-1){
    int amax=0;
    for(auto e:g[now]){
        amax=max(amax,1+dfs(g,e,now));
    }
    if(amax==K-1&&(from!=0&&from!=-1)){
        amax=-1;
        answer++;
    }
    return amax;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie();
    cin>>N>>K;
    Graph g(N);
    Graph rev_g(N);
    for(int i=0;i<N;++i){
        int a;cin>>a;
        a--;
        if(i==0){
            if(a){
                answer++;
            }
        }else{
            g[i].push_back(a);
            rev_g[a].push_back(i);
        }
    }
    dfs(rev_g,0);
    cout<<answer<<endl;
    return 0;
}

Measured memory_bytes: 17408
package main

import (
	"fmt"
)


func main() {
	var a, b, c, d int
	fmt.Scan(&a,&b,&c,&d)
	if a > c {
		a, c = c, a
	}

	if d < b {
		d, b = b, d
	}

	e := b - c

	if e < 0 {
		fmt.Println(0)
	}else{
		fmt.Println(e)
	}
}



Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static long inversion = 0;

    static void merge(int[] A, int left, int mid, int right) {
        int l1 = mid - left;
        int l2 = right - mid;

        int[] L = new int[l1 + 1];
        int[] R = new int[l2 + 1];

        for (int i = 0; i < l1; i++)
            L[i] = A[left + i];

        for (int i = 0; i < l2; i++)
            R[i] = A[mid + i];

        L[l1] = R[l2] = 1000000001; // Sの要素より確実に大きいInfのようなものを番兵として扱う

        int i = 0;
        int j = 0;

        for (int k = left; k < right; k++) {

            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                inversion += (l1 - i);
                A[k] = R[j];
                j++;
            }

        }
    }

    static void mergeSort(int[] A, int left, int right) {
        if (left + 1 < right) {
            int mid = (left + right) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid, right);
            merge(A, left, mid, right);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        mergeSort(arr, 0, n);

        System.out.println(inversion);
    }
}


Measured memory_bytes: 61672