akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

#define is_uruu main
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(a);i>(b);--i)
    
int is_uruu() {
    char c[3][3];
    FOR(i,0,3){
    	FOR(j,0,3){
    		cin >> c[i][j];
    	}
    }
    cout << c[0][0]<< c[1][1] << c[2][2]  << endl; 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m;
LL min(LL a,LL b){
    return (a>b)?b:a;
}
LL max(LL a,LL b){
    return (a<b)?b:a;
}
int main(){
    cin>>n>>m;
    cout<<min(n,m/2)+max(m-n*2,0)/4;
    return 0;
} 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<algorithm>
#include<tuple>

int c[4][4];

void input(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			scanf("%d",&c[i][j]);
		}
	}
}



bool solve(void){
	int sa[4][4]={};
	//横方向判定
	for(int i=1;i<=2;i++){
		for(int j=1;j<=3;j++){
			sa[i][j]=c[i+1][j]-c[i][j];
		}
	}
	if(sa[1][1]==sa[1][2] && sa[1][2]==sa[1][3] &&sa[2][1]==sa[2][2] && sa[2][2]==sa[2][3]){
		//縦方向判定
		for(int k=1;k<=3;k++){
			for(int l=1;l<=2;l++){
				sa[k][l]=sa[k][l+1]-sa[k][l];
				if(sa[1][1]==sa[2][1] && sa[2][1]==sa[3][1] && sa[1][2]==sa[2][2] && sa[2][2]==sa[3][2] ){
					return true;
				}
			}
		}
	}

	return false;



}

int main(void){
	input();
	if(solve()){
		std::cout<<"Yes"<<std::endl;
	}else{
		std::cout<<"No"<<std::endl;
	}


	return 0;
}


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

#pragma once
#include <type_traits>
#include <vector>
namespace yaito {
  template<class T, class Func = T(*)(T, T)>
  class segmentTree {
  private:
    std::vector<T> data;
    size_t height;
    size_t bottom_size;
    T identity;
    Func func;

  public:
    segmentTree() = default;
    segmentTree(size_t N, T identity_, const Func& func_ = Func{})
      : identity(identity_)
      , func(func_)
    {
      bottom_size = 1;
      height = 1;
      while (bottom_size < N) {
        bottom_size <<= 1;
        ++height;
      }
      data.resize(2 * bottom_size - 1, identity);
    }

    template<class Iter>
    segmentTree(Iter first_, Iter last_, T identity_, const Func& func_ = Func{})
      : segmentTree(std::distance(first_, last_), identity_, func_)
    {
      for (size_t i = 0; i < bottom_size; ++i, ++first_)update(i, *first_);
    }

    void update(size_t i, T value) {
      i += bottom_size - 1;
      data[i] = value;
      while (i > 0) {
        i = (i - 1) / 2;
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2]);
      }
    }

    T get(size_t l, size_t r) const {
      T res = identity;
      l += bottom_size - 1;
      r += bottom_size - 1;
      while (l < r) {
        if (l % 2 == 0)res = func(res, data[l++]);
        if (r % 2 == 0)res = func(data[--r], res);
        l = (l - 1) / 2;
        r = (r - 1) / 2;
      }
      return res;
    }

    void show()const {
      for (size_t i = 0; i < 2 * bottom_size - 1; ++i) {
        std::cout << data[i] << ", ";
        if (!((i + 2) & (i + 1)))std::cout << '\n';
      }
    }

  };

  template<class T, class Iter, class Func>
  auto make_segmentTree(Iter&& first, Iter&& last, T&& identity, Func&& func = std::remove_reference_t<Func>{}) {
    return segmentTree<std::remove_reference_t<T>, remove_reference_t<Func>>(
      std::forward<Iter>(first), std::forward<Iter>(last), std::forward<T>(identity), std::forward<Func>(func));
  }

  template<class T, class Func>
  auto make_segmentTree(size_t N, T&& identity, Func&& func = std::remove_reference_t<Func>{}) {
    return segmentTree<std::remove_reference_t<T>, remove_reference_t<Func>>(
      N, std::forward<T>(identity), std::forward<Func>(func));
  }

}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N;
  cin >> N;
  string S;
  cin >> S;
  array<yaito::segmentTree<int, plus<>>, 26> trees;
  for (char c = 'a'; c <= 'z'; ++c) {
    trees[c - 'a'] = yaito::make_segmentTree(N, 0, plus<>{});
    for (int i = 0; i < N; ++i)trees[c - 'a'].update(i, S[i] == c ? 1 : 0);
  }
  int Q;
  cin >> Q;
  for (int q = 0; q < Q; ++q) {
    int t;
    cin >> t;
    if (t == 1) {
      int i;
      char c;
      cin >> i >> c;
      --i;
      trees[S[i] - 'a'].update(i, 0);
      trees[c - 'a'].update(i, 1);
      S[i] = c;
    }
    else if (t == 2) {
      int l, r;
      cin >> l >> r;
      --l;
      int ans = 0;
      for (const auto& e : trees)if (e.get(l, r) > 0)++ans;
      cout << ans << "\n";
    }
  }
}


Measured memory_bytes: 107548
#include <iostream>
using namespace std;
int sum(int n)
{
        return n * (n + 1) / 2;
}
int main()
{

        int n,m,ans;
        cin >> n >> m;
        ans = sum(n - 1) + sum(m - 1); 
        cout << ans << endl;
        return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <cstring>
using namespace std;

int vist[100002];
int main()
{
    //freopen("B.data", "r", stdin);
    int N,M;
    int A,B;
    scanf("%d%d",&N,&M);
    memset(vist,-1,sizeof(vist));
    vector<vector<int>  > path(N+1);
    for(int i = 0 ; i < M; ++i){
        scanf("%d%d",&A,&B);
        path[A].push_back(B);
        path[B].push_back(A);
    }
    queue<int> q;
    q.push(1);
    vist[1]= 0;
    int cnt = 0;
    while(!q.empty()){
        int cur = q.front();
        //cout<<endl<<"cur = "<<cur<<endl;
        for(int i = 0 ; i < path[cur].size();++i){
            int tmp = path[cur][i];
            // cout<<"tmp = "<<tmp<<endl;
            // for(int j = 1 ; j <= N ; ++j){
            //     cout<<" "<<vist[j]<<" ";
            // }
            // cout<<endl;
            if(vist[tmp] == -1){
                q.push(tmp);
                vist[tmp] = cur;
            }
        }
        cnt++;
        q.pop();
    }
    if(cnt != N){
        printf("No\n");
    }else {
        printf("Yes\n");
        for(int i = 2; i <= N ; ++i){
            printf("%d\n",vist[i]);
        }
    }
    return 0;
}

Measured memory_bytes: 10336
#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--)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    vector<ll> a(3 * n);
    rep(i, 3 * n) cin >> a[i];
    sort(a.begin(), a.end(), greater<ll>());
    ll ans = 0;
    rep(i, n){
        ans += a[2 * i + 1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m=1000000007;
int main() {
	ll n,k,i,j,w;
	cin>>n>>w;
	ll a[n+1],b[n+1];
	for(i=1;i<=n;i++)
	{
	    cin>>a[i]>>b[i];
	}
	vector<vector<ll>>dp(100005,vector<ll>(n+2,-1));
	for(i=0;i<=n;i++)
	dp[0][i]=0;
	ll ans=-1;
	for(i=1;i<=100003;i++)
	{
	    for(j=1;j<=n;j++)
	    {
	        if(b[j]<=i)
	        {
	            if(dp[i-b[j]][j-1]!=-1)
	            {
	                if(dp[i-b[j]][j-1]+a[j]<=w)
	                {
	                    if(dp[i][j]==-1)
	                    dp[i][j]=dp[i-b[j]][j-1]+a[j];
	                    else
	                    dp[i][j]=min(dp[i][j],dp[i-b[j]][j-1]+a[j]);
	                    ans=max(ans,i);
	                }
	            }
	            if(dp[i][j-1]!=-1&&dp[i][j]==-1)
	            dp[i][j]=dp[i][j-1];
	        }
	        else dp[i][j]=dp[i][j-1];
	        if(dp[i][j]!=-1&&dp[i][j-1]!=-1)
	        dp[i][j]=min(dp[i][j],dp[i][j-1]);
	    }
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 86928
import java.util.Scanner;

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

        int h = sc.nextInt();
        int w = sc.nextInt();
        int h_s = sc.nextInt();
        int w_s = sc.nextInt();

        int count = h * w;
        count -= (h_s * w) + (w_s * h) - (h_s * w_s);
        System.out.println(count);
    }
}


Measured memory_bytes: 23380
//答え見ました
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  
  ll n;
  ll m;
  cin >> n >> m;
  ll p[100000], y[100000];//入力用配列
  vector<ll>b[100001];//b[県番][市番]を格納する配列
  for(int i=0; i<m; i++){
   cin >> p[i] >> y[i]; 
   b[p[i]].push_back(y[i]);//b[県番][序列]=市番の状態
  }
  
  for(int i=0; i<n; i++){
   sort(b[i+1].begin(),b[i+1].end());//県ごとに市番をsort
  }

  
  for(int i=0; i<m; i++){
    printf ("%06d",p[i]);
    printf("%06d",lower_bound(b[p[i]].begin(),b[p[i]].end(),y[i])-b[p[i]].begin()+1);
    cout << endl;
  }
}



Measured memory_bytes: 8576
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int MOD = 1000000007;

int main()
{
    const string NG = "UNRESTORABLE";

	cin.tie(0);
	ios::sync_with_stdio(0);

    string s, t;
    cin >> s >> t;

    string ans = NG;
    for (int offset = 0; offset+t.length() <= s.length(); ++offset) {
        // cout << "offset = " << offset << endl;
        bool ok = true;
        rep(i, t.length()) {
            if (s[i+offset] != '?' && s[i+offset] != t[i]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            // cout << "  OK" << endl;
            string cand;
            rep(i, offset) {
                cand += (s[i] == '?' ? 'a' : s[i]);
            }
            cand += t;
            for (int i = offset+t.length(); i < s.length(); ++i) {
                cand += (s[i] == '?' ? 'a' : s[i]);
            }
            if (ans == NG || cand < ans) {
                ans = cand;
            }
        // } else {
        //     cout << "  NG" << endl;
        }
    }


    cout << ans << endl;
    

    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;
const int MOD = 1000000007; // 計算してからmodで割る ans = (ans * a) % mod
#define int long long
template <typename T = long long > T in () { T x; cin >> x; return(x);}
// int a = in() のように使うlong long以外の型の時はstirng s = in<string>()のように型を指定する

signed main(void){
    int n = in(), m = in();
    vector<string> s(n);
    REP(i, n) cin >> s[i];
    whole(sort, s);
    REP(i, n) cout << s[i];
    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<boost/algorithm/string/replace.hpp>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::algorithm;
using namespace boost::multiprecision;
 
#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define ALL(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;
 
const ll INF = 1LL<<60;
const int mINF = 1e9;
const int MOD = 1e9+7;

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

template<typename T>
T GCD(T a,T b){ return b ? GCD(b,a%b) : a ;}
template<typename T>
T LCM(T a,T b){ return a*b / GCD(a,b) ;}

template<typename T>//文字列の置換/Boost:replace_all()
T replace_str(T str, string target, string str_to) {
    string::size_type pos = 0;
    while (pos = str.find(target, pos), pos != string::npos) {
        str.replace(pos, target.length(), str_to);
        pos += str_to.length();
    }
    return str;
}

int main(){
    int n;cin >> n;
    map<int,int> a;
    rep(i,n){
      int key;
      cin >> key;
      a[key] = i+1;
    }
    rep(i,n){
      cout << a[i+1] << ' ';
    }
    return 0;
}

Measured memory_bytes: 5504
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N, sum=0;
    cin >> N;
    vector<int> a(N+2, 0);
    for(int i=1;i<N+1;++i){
        cin >> a[i];
        sum += abs(a[i] - a[i-1]);
    }
    sum += abs(a[N+1] - a[N]);

    int dif;
    for(int i=1;i<N+1;++i){
        dif = abs(a[i] - a[i-1]) + abs(a[i+1] - a[i]) - abs(a[i+1] - a[i-1]);
        cout << sum - dif << endl;
    }
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string str;
    ll i,one=0,zero=0;
    cin>>str;
    for(i=0;i<str.length();i++){
        if((str[i]=='1'))
            one+=1;
        else
            zero+=1;
    }
    cout<<2*min(zero,one)<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() { 
    string s;
    cin >> s;
    int n = s.size();
    vector<int> v(n + 1, 0);
    v[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 7; j >= 5; j--) {
            if (i + j <= n) {
                string ss = string(s.begin() + i, s.begin() + i + j);
                if (ss == "dream" || ss == "dreamer" || ss == "erase" || ss == "eraser") {
                    v[i + j] = max(v[i + j], v[i]);
                }
            }
        }
        // cout << v[i];
    }
    if (v[n] == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

}




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

int main() {
  vector<int> p = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
  int n;
  cin >> n;
  vector<int> v(101);
  for (int i = 1; i <= n; i++) {
    int t = i;
    for (auto e : p) {
      while (t % e == 0) {
        t /= e;
        v[e]++;
      }
    }
  }
  vector<int> m(98);
  for (auto e : v) {
    m[e]++;
  }
  for (int i = m.size() - 1; i > 0; i--) {
    m[i - 1] += m[i];
  }
  int r = 0;
  r += m[75 - 1];
  if (m[25 - 1]) r += m[25 - 1] * (m[3 - 1] - 1);
  if (m[15 - 1]) r += m[15 - 1] * (m[5 - 1] - 1);
  if (m[5 - 1] >= 2) r += m[5 - 1] * (m[5 - 1] - 1) / 2 * (m[3 - 1] - 2);
  cout << r << endl;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    l = []
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i- k), i))
print(dp[n - 1])

Measured memory_bytes: 53344
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define UNIQUE(v) { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); }
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) (q ? "Yes" : "No")
#define YES(q) (q ? "YES" : "NO")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) { cerr << "[DEBUG] " #q ": ["; REP(dumpall_i, (q).size()) { cerr << q[dumpall_i] << (dumpall_i == (q).size() - 1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; }
template<class T> T gcd(const T &a, const T &b) { return a < b ? gcd(b, a) : b ? gcd(b, a % b) : a; }
template<class T> T lcm(const T &a, const T &b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
using  ll = long long;
using ull = unsigned long long;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    ll n; cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    vector<ll> a2 = a;
    sort(ALL_OF(a2), greater<ll>());

    ll max1 = a2[0];
    ll max2 = a2[1];
    REP(i, n) {
        cout << (a[i] == max1 ? max2 : max1) << endl;
    }

}

Measured memory_bytes: 4736
cards = int(input())
tarou_win = 0
hanako_win = 0
hikiwake = 0
for _ in range(cards):
    tarou_word, hanako_word = input().split() 
    if tarou_word > hanako_word:
        tarou_win += 1
    elif tarou_word < hanako_word:
        hanako_win += 1
    else :
        hikiwake += 1
print(tarou_win * 3 + hikiwake ,hanako_win * 3 + hikiwake)


Measured memory_bytes: 5600
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type bufReader struct {
	r   *bufio.Reader
	buf []byte
	i   int
}

var reader = &bufReader{
	bufio.NewReader(os.Stdin),
	make([]byte, 0),
	0,
}

func (r *bufReader) readLine() {
	if r.i < len(r.buf) {
		return
	}
	r.buf = make([]byte, 0)
	r.i = 0
	for {
		line, isPrefix, err := r.r.ReadLine()
		if err != nil {
			panic(err)
		}
		r.buf = append(r.buf, line...)
		if !isPrefix {
			break
		}
	}
}

func (r *bufReader) next() string {
	r.readLine()
	from := r.i
	for ; r.i < len(r.buf); r.i++ {
		if r.buf[r.i] == ' ' {
			break
		}
	}
	s := string(r.buf[from:r.i])
	r.i++
	return s
}

func (r *bufReader) nextLine() string {
	r.readLine()
	s := string(r.buf[r.i:])
	r.i = len(r.buf)
	return s
}

var writer = bufio.NewWriter(os.Stdout)

func next() string {
	return reader.next()
}

func nextInt64() int64 {
	i, err := strconv.ParseInt(reader.next(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func nextInt() int {
	return int(nextInt64())
}

func nextLine() string {
	return reader.nextLine()
}

func out(a ...interface{}) {
	fmt.Fprintln(writer, a...)
}

func max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func min64(x, y int64) int64 {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	return int(max64(int64(x), int64(y)))
}

func min(x, y int) int {
	return int(min64(int64(x), int64(y)))
}

func joinInt64s(a []int64, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.FormatInt(v, 10)
	}
	return strings.Join(b, sep)
}

func joinInts(a []int, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.Itoa(v)
	}
	return strings.Join(b, sep)
}

func divUp64(x, y int64) int64 {
	return (x + y - 1) / y
}

func divUp(x, y int) int {
	return int(divUp64(int64(x), int64(y)))
}

func main() {
	solve()
	writer.Flush()
}

func solve() {
	H, W, N := nextInt64(), nextInt64(), nextInt()
	a, b := make([]int64, N), make([]int64, N)
	for i := 0; i < N; i++ {
		a[i], b[i] = nextInt64(), nextInt64()
	}
	_, _ = H, W
	ans := make([]int64, 10)
	ans[0] = (H - 2) * (W - 2)
	B := make(map[point]struct{})
	for i := 0; i < N; i++ {
		for dh := int64(-2); dh <= 0; dh++ {
			for dw := int64(-2); dw <= 0; dw++ {
				sh := a[i] + dh
				sw := b[i] + dw
				if 1 <= sh && sh <= H-2 && 1 <= sw && sw <= W-2 {
					nb := 0
					for ddh := int64(0); ddh < 3; ddh++ {
						for ddw := int64(0); ddw < 3; ddw++ {
							h := sh + ddh
							w := sw + ddw
							if _, ok := B[point{h, w}]; ok {
								nb++
							}
						}
					}
					ans[nb]--
					ans[nb+1]++
				}
			}
		}
		B[point{a[i], b[i]}] = struct{}{}
	}
	for _, n := range ans {
		out(n)
	}
}

type point struct {
	h, w int64
}


Measured memory_bytes: 10112
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
#define PQ priority_queue
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define MOD 1000000007 
#define MOD2 1000000021
#define MAXN 2000000
#define INF 1e9
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;

//ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll m_pow(ll a, ll b, ll M = MOD) { ll res = 1; for (; b; b >>= 1, a = (a * a) % M)if (b & 1)res = (res * a) % M; return res; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
db dis(pii a, pii b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
int dr[] = { 0, 1, 0, -1, 1,1,-1,-1 };
int dc[] = { 1, 0, -1, 0, 1,-1,1,-1 };

int n, m, k, t;

string ansok[2] = { "NO","YES" };

int a[200005];
int main()
{
	SYNC;
	string s, t;
	cin >> s >> t;
	int ans = INF;
	for (int i = 0; i <= s.size()- t.size(); i++) {
		int res = 0;
		for (int j = 0; j < t.size(); j++) {
			if (s[i+j] != t[j]) {
				res++;
			}
		}
		ans = min(ans, res);
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3684
#include <bits/stdc++.h> 
using namespace std;
#define llu long long unsigned 
int main() 
{  
  int t;
  cin>>t;
    string s1, s2;
  cin>>s1>>s2;
  for(int i=0; i<s1.length()&&i<s2.length();i++)
  {
    cout<<s1[i]<<s2[i];
  }
    return 0; 
} 

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

int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; i++){
        cin >> d.at(i);
    }
    sort(d.begin(), d.end());
    cout << d.at(N/2) - d.at(N/2 - 1) << endl;
}


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

const int MAXN = 42;
const int INF = 1<<28;

int n;
int p[MAXN], t[MAXN];
int dp[MAXN][MAXN];

int main() {
  while(cin >> n && n) {
    for(int i = 1; i <= n; ++i) {
      cin >> p[i] >> t[i];
    }
    fill(dp[0], dp[MAXN], INF);
    dp[0][0] = 0;
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j <= 3; ++j) {
        do {
          int dist = abs(p[i] - p[i+1]);
          int nj = j + 1;
          int nt = t[i] + dist * (j + 1);
          if(nt > t[i+1]) break;
          dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + dist);
        } while(0);
        do {
          int dist = p[i] + p[i+1];
          int nj = 1;
          int nt = t[i] + p[i] * (j + 1) + p[i+1];
          if(nt > t[i+1]) break;
          dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + dist);
        } while(0);
      }
    }

    int res = INF;
    for(int j = 0; j <= 3; ++j) {
      res = min(res, dp[n][j] + p[n]);
    }
    if(res != INF) {
      cout << "OK " << res << endl;
    } else {
      for(int i = 1; i <= n; ++i) {
        res = INF;
        for(int j = 0; j <= 3; ++j) {
          res = min(res, dp[i][j]);
        }
        if(res == INF) {
          cout << "NG " << i << endl;
          break;
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1168
import java.util.*;
import java.math.*;

class Main{
	public static void main(String Args[]){
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		BigInteger A = new BigInteger(str);
		str = sc.next();
		BigInteger B = new BigInteger(str);
		System.out.println(A.remainder(B));
	}
}



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

#define limit (int)(2e5 + 5)
// #define mod (int)(1e9 + 7)
#define pb push_back
#define fi first
#define se second

using namespace std;
using lli = long long int;
using ulli = unsigned long long int;
using ld = long double;

int main() {

	int n,k;
	cin >> n >> k;

	int a[n];

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

	 sort(a,a+n);

	 int ans = 0;

	 for (int i = 0; i < k; ++i)
	 {
	 	ans += a[i];
	 }

	 cout << ans;
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

using namespace std;

int main(void){
    string S, T;
    cin>>S>>T;
    cout<<T+S<<endl;
    
    return 0;
}


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

using namespace std;
using ll = long long;

ll INF = 1LL << 60;

ll dp[110][110];

int main() {
	int v, e;
	cin >> v >> e;
	vector<vector<pair<int, ll>>> g(v);

	for (int i = 0; i < e; i++) {
		int s, t;
		ll d;
		cin >> s >> t >> d;
		g[s].push_back({ t, d });
	}

	for (int i = 0; i < v - 1; i++) {
		for (int j = i + 1; j < v; j++) {
			dp[i][j] = INF;
			dp[j][i] = INF;
			for (auto to : g[i]) {
				if (j == to.first) dp[i][j] = to.second;
			}
			for (auto to : g[j]) {
				if (i == to.first) dp[j][i] = to.second;
			}
		}
	}

	bool negative = false;

	for (int k = 0; k < v; k++) {
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				if (dp[i][k] == INF || dp[k][j] == INF) continue;
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
				if (dp[i][i] < 0) negative = true;
			}
		}
	}

	if (negative) cout << "NEGATIVE CYCLE" << endl;
	else {
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				if (dp[i][j] == INF) cout << "INF";
				else cout << dp[i][j];
				if (j < v - 1) cout << " ";
			}
			cout << endl;
		}
	}

	return 0;
}



Measured memory_bytes: 3288
N,M,C = map(int,input().split())

B = list(map(int,input().split()))

cnt = 0
for i in range(N):
    A = list(map(int,input().split()))
    dic = 0
    for j in range(M):
        dic += A[j]*B[j]
    dic += C
    if dic > 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 3060
n = int(input())
a = [int(input()) for _ in range(n)]

visited=set([1])
ans=0
i=0
while True:
    x=a[i]
    if x in visited:
        ans = -1
        break
    visited.add(x)
    ans += 1
    if x == 2:
        break
    i=a[i]-1
print(ans)


Measured memory_bytes: 13220
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
			int a =sc.nextInt();
			int b =sc.nextInt();
			int d =0;
			int flag =0;
			 			
			for(int i=0;i<b+1;i++)
			{
				d=a-i;
				
				if(d%500==0){
					flag=1;
				}
			}
			
			if(flag==1){
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
}

Measured memory_bytes: 21972
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] s = sc.next().split(",");
		for(int i = 0; i < s.length-1; i++) {
			System.out.print(s[i] + " ");
		}
		System.out.println(s[s.length-1]);
	}

}


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

class UnionFind {
	vector<int> data;
	vector<int> rank;
	int root(int a) {
		return data[a] < 0 ? a : data[a] = root(data[a]);
	}
public:
	UnionFind(int n) : data(n, -1), rank(n, 1) {}
	bool Find(int a, int b) {
		return root(a) == root(b);
	}
	void Union(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b) return;
		if (rank[a] < rank[b]) {
			data[a] += data[b];
			data[b] = a;
		}
		else {
			data[b] += data[a];
			data[a] = b;
			if (rank[a] == rank[b]) rank[b]++;
		}
	}
	int Size(int a) {
		return -data[root(a)];
	}
	int Rank(int a) {
		return rank[root(a)];
	}
};

int main()
{
	int N, M;
	while (cin >> N >> M, N | M) {
		vector<int> h(N);
		vector<pair<int, int>> s(N);
		for (int i = 0; i < N; i++) {
			cin >> h[i];
			s[i].first = h[i];
			s[i].second = i;
		}
		vector<tuple<int, int, int>> abc(M);
		for (int i = 0, a, b, c; i < M; i++) {
			cin >> a >> b >> c;
			abc[i] = make_tuple(c, --a, --b);
		}
		sort(s.begin(), s.end());
		sort(abc.begin(), abc.end());
		vector<int> a(M), b(M), c(M);
		for (int i = 0; i < M; i++) {
			a[i] = get<1>(abc[i]);
			b[i] = get<2>(abc[i]);
			c[i] = get<0>(abc[i]);
		}

		vector<int> exist(N, 1);
		ll tmp;
		for (tmp = 0; tmp < N; tmp++) {
			UnionFind uf(N);
			for (int i = 0; i < M; i++) {
				if (exist[a[i]] && exist[b[i]]) {
					uf.Union(a[i], b[i]);
				}
			}
			int id;
			for (int i = 0; i < N; i++) {
				if (exist[i]) {
					id = i;
				}
			}
			if (uf.Size(id) != N - tmp) {
				break;
			}
			while (tmp + 1 < N && s[tmp].first == s[tmp + 1].first) {
				exist[s[tmp++].second] = 0;
			}
			exist[s[tmp].second] = 0;
		}
		ll res = 0;
		UnionFind uf(N);
		for (int j = tmp - 1; j >= 0; j--) {
			while (j - 1 >= 0 && s[j].first == s[j - 1].first) {
				exist[s[j--].second] = 1;
			}
			exist[s[j].second] = 1;
			for (int i = 0; i < M; i++) {
				if (exist[a[i]] && exist[b[i]]) {
					if (!uf.Find(a[i], b[i])) {
						uf.Union(a[i], b[i]);
						res += c[i];
					}
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3420
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 200002;

int n;
int a[MAX];
unordered_map <int, int> have[32];

int update(int idx, int num, int orig) {
    num /= 2;
    long long pwr = 1;
    while (pwr <= num)
        pwr <<= 1;
    while (pwr <= (1 << 30)) {
        // fprintf(stderr, "Here with pwr = %d\n", pwr);
        int match = (int)(pwr - 1) ^ num;
        if (have[idx].find(match) != have[idx].end()) {
            if (have[idx][match] > 0) {
                have[idx][match]--;
                // fprintf(stderr, "Matched %d.\n", orig);
                return 1;
            }
        }
        pwr <<= 1;
    }
    have[idx][num]++;
    return 0;
}

int main(void) {
	// in = fopen("B.in", "rt");
	
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; i++)
	    fscanf(in, "%d", &a[i]);
	sort(a, a + n);
	reverse(a, a + n);
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
	    int tmp = a[i], idx = 0;
	    while (tmp % 2 == 0)
	       tmp /= 2, idx++;
	    ans += update(idx, tmp, a[i]);
    }
    fprintf(out, "%d\n", ans);
	
	return 0;
}

Measured memory_bytes: 9264
a,b,n = map(int,input().split())

def f(x):
    return int(a*x/b)-a*int(x/b)

if b == 1:
    print(0);exit()

l = 0
r = n
while r - l > 100:
    rr = (l + 2*r)//3
    ll = (2*l + r)//3
    if f(ll) > f(rr):
        r = rr
    elif f(ll) < f(rr):
        l = ll
    else:
        l = ll

ans = -100
for i in range(l,r+1):
    ans = max(ans,f(i))
print(ans)


Measured memory_bytes: 9208
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 標準入力
		Scanner sc = new Scanner(System.in);

		String stN = sc.nextLine();
		int n = Integer.parseInt(stN);

		/*
		List<String> lines1 = Arrays.asList(line1.split(" "));
		List<String> lines2 = Arrays.asList(line2.split(" "));
		*/
		String line = null;
		List<String> lines = null;

		int t = 0;
		int x = 0;
		int y = 0;

		int nT = 0;

		int nX = 0;
		int nY = 0;
		int abs = 0;
		while (sc.hasNext()) {
			line = sc.nextLine();
			lines = Arrays.asList(line.split(" "));
			nT = Integer.parseInt(lines.get(0));
			nX = Integer.parseInt(lines.get(1));
			nY = Integer.parseInt(lines.get(2));
			abs = Math.abs(nX - x) + Math.abs(nY - y);
			if (abs == (nT - t)) {

			} else if (abs < (nT - t) && ((nT - t) - abs) % 2 == 0) {

			} else {
				System.out.println("No");
				return;
			}
			t = nT;
			x = nX;
			y = nY;
		}

		System.out.println("Yes");
	}

}

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

using namespace std;

typedef long long ll;

bitset<4000010> dp;

int main() {
    int N;
    cin >> N;
    dp[0] = 1;
    int s = 0;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        dp |= dp << x;
        s += x;
    }

    int mx = -1;
    int ans = 0;
    for (int i = 0; i <= 4000000; i++) {
        if (dp[i]) {
            if (mx < min(i, s - i)) {
                ans = i;
                mx = min(i, s - i);
            }
        }
    }
    cout << s - ans << endl;
}

Measured memory_bytes: 1664
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VB> VVB;

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<decltype((c).front())>())
#define SZ(x) ((int)(x).size())
#define MEMSET(c, v) memset((c), v, sizeof(c))

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// constant
// const ll MOD = 1e9 + 7;
// const int INF = 1e9;
// const ll INF = 1e15;
// const int dx[4] = {0, -1, 1, 0};
// const int dy[4] = {-1, 0, 0, 1};
// const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


// --------------------------------------------------------


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

  string s;
  cin >> s;
  int l = SZ(s);
  bool flag = true;
  while (flag) {
    l -= 2;
    flag = false;
    REP(i, l / 2) {
      if (s[i] != s[i + l / 2]) {
        flag = true;
      }
    }
  }

  cout << l << endl;

  return 0;
}

Measured memory_bytes: 256
let round_up n = 
  let r = n mod 10 in
    if r = 0 then n 
    else n + 10 - r
;;

let add n = 
  let r = n mod 10 in
    if r = 0 then 0
    else 10 - r
;;

let r_max a b c d e =
  max (max (max (max (add a) (add b)) (add c)) (add d)) (add e)
;;


let () = Scanf.scanf "%d\n%d\n%d\n%d\n%d" (fun a b c d e -> (
  (round_up a) + (round_up b) + (round_up c) + (round_up d) + (round_up e) - r_max a b c d e |> print_int
));;

Measured memory_bytes: 384
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include<algorithm>
//---------------------------------------------------------------
#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 rep2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define SIZE 100005
#define INF 1e18
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define vec vector
using pint = pair<int,int>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
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 dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = acos(-1);
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


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

    ll n;cin>>n;
    vll t(n+1);
    vll x(n+1);
    vll y(n+1);
    t[0]=0;
    x[0]=0;
    y[0]=0;
    rep2(i,1,n){
        cin>>t[i]>>x[i]>>y[i];
    }

    rep(i,n){
        if(abs(x[i]-x[i+1])>t[i+1]-t[i] || abs(y[i]-y[i+1])>t[i+1]-t[i] || abs(x[i]-x[i+1])+abs(y[i]-y[i+1])>t[i+1]-t[i]) {
            cout<<"No"<<endl;
            return 0;
        }else{
            if((t[i+1]-t[i])%2 != ((x[i+1]+x[i]+y[i+1]+y[i])%2)){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }

    cout<<"Yes"<<endl;
}

Measured memory_bytes: 5512
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

pub fn divisor(n: u64) -> Vec<u64> {
    let mut res = Vec::new();
    for i in (1..).take_while(|x| x * x <= n) {
        if n % i == 0 {
            res.push(i);
            if i != n / i {
                res.push(n / i);
            }
        }
    }
    res.sort();
    res
}

fn main() {
    input! {
        a: u64,
        b: u64
    }
    let g = gcd(a,b);
    let d = divisor(g);
    let mut f = d.clone();
    for i in d.into_iter().skip(1) {
        f = f.into_iter()
             .filter(|&x| x == i || x % i != 0)
             .collect();
    }
    println!("{}", f.len());
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator 
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20,mod=998244353,inf=2e9;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
    char c=gc; x=0; int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
    while(isdigit(c)) x=x*10+c-'0',c=gc;
    x*=f;
}
template<class o> void qw(o x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
template<class o> void pr1(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar('\n');
}

int n,m,q,lg,x[N],r[N][20],l[N][20];
ll sl[N][20],sr[N][20];

int main() {
    qr(n); qr(m);
    for(int i=1;i<=n;i++) qr(x[i]);
    for(int i=1;i<=n;i++) {
        r[i][0]=r[i-1][0];
        while(r[i][0]<=n&&x[r[i][0]]-x[i]<m) r[i][0]++;
        sr[i][0]=r[i][0]-1;
    }
    l[n+1][0]=n;
    for(int i=n;i;i--) {
        l[i][0]=l[i+1][0];
        while(l[i][0]&&x[i]-x[l[i][0]]<m) l[i][0]--;
        sl[i][0]=l[i][0];
    }
    for(int i=0;i<20;i++) r[n+1][i]=n+1;
    for(int j=1;(1<<j)<=n;j++,lg++)
        for(int i=1;i<=n;i++) {
            l[i][j]=l[l[i][j-1]][j-1];
            sl[i][j]=sl[i][j-1]+sl[l[i][j-1]][j-1];
            r[i][j]=r[r[i][j-1]][j-1];
            sr[i][j]=sr[i][j-1]+sr[r[i][j-1]][j-1];
        }
    qr(q); while(q--) {
        int L,R; qr(L); qr(R); ll ans=0;
        ans -= L-1;
        for(int v=L,i=lg;i>=0;i--)
            if(r[v][i]<=R) 
				ans -= sr[v][i],v=r[v][i];
        ans += R; 
        for(int v=R,i=lg;i>=0;i--)
            if(l[v][i]>=L) 
				ans += sl[v][i],v=l[v][i];
        pr2(ans);
    }
    return 0;
}

Measured memory_bytes: 98176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0; i<n; ++i)
#define rep1(i,n) for(ll i=1; i<=n; ++i)
#define revrep(i,n) for(ll i=n-1; i>=0; --i)
inline constexpr ll Inf = (1ULL << 62) -1;
#define fastio cin.tie(nullptr); ios_base::sync_with_stdio(false);
#define endl '\n'
template <class T> bool updmax(T& a, T b) { if (b > a) { a = b; return true;} return false;}
template <class T> bool updmin(T& a, T b) { if (b < a) { a = b; return true;} return false;}


int main() {
    fastio;
    ll ans=0;
    ll N;
    cin >> N;
    int X, M;
    cin >> X >> M;
    map<int,int> c;
    int x = X;
    int cycle = 0;
    int start = 0;
    rep1(i, M+1) {
        if (c.count(x)) {
            cycle = i-c[x];
            start = c[x];
            break;
        }
        c[x] = i;
        x = (ll)x * x % M;
    }
    int t = X;
    for (int i=1; i <= min(N,(ll)start); ++i) {
        ans += t;
        t = (ll)t*t % M;
    }
    if (N > start) {
        t = x;
        ll cs = 0;
        rep(i, cycle) {
            cs += t;
            t = (ll)t*t % M;
        }
        ans += (N - start)/cycle * cs;

        int r = (N - start) % cycle;
        cs = 0;
        t = (ll)x*x % M;
        for (int i=0; i<r; ++i) {
            cs += t;
            t = (ll)t*t % M;
        }
        ans += cs;
    }
    cout << ans << endl;
}


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

int main(){
    string s ;
    int n,a=0,b=0,c=0,d=0 ;
    cin>>n ;

    for(int i = 0 ; i < n ; i++){
        cin>>s;
        if(s=="AC") a++;
        else if(s=="WA") b++;
        else if(s=="TLE") c++;
        else if(s=="RE") d++;

    }
    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<b<<endl;
    cout<<"TLE x "<<c<<endl;
    cout<<"RE x "<<d<<endl;

}


Measured memory_bytes: 3584
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()


using namespace std;
void dout() { cerr << endl; }
typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

#define debug(x) cout << #x " = " << (x) << endl

using ll = long long;
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

template <typename T>
void do_uniq(vector<T> vec) {
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}

#define solvsh
//#define multi
#ifdef solvsh

void prec(){

}

const int MAXN = 2e5;

vector<int> g[MAXN];
ll mod = 1e9 + 7;

ll pows[MAXN];

int to[MAXN];

int comp[MAXN];

map<int ,int> mins_comp;

int inp[MAXN];

void dfs(int ver, int color) {
    if (comp[ver] != 0)
        return;

    comp[ver] = color;
    if (inp[ver] == -1)
        mins_comp[color] ++;

    for (auto out : g[ver]) {
        dfs(out, color);
    }
}

ll ml(ll a, ll b) {
    return (a * b) % mod;
}

ll add(ll a, ll b) {
    return (a + b) % mod;
}


void solve() {

    ll n;
    cin >> n;

    vector<int> pows;
    ll x = n;
    for (ll i =2 ; i  *i <= n; ++ i) {
        int deg = 0;
        while (x % i == 0) {
            x /= i;
            ++deg;
        }
        if (deg)
            pows.push_back(deg);
    }

    if (x > 1)
        pows.push_back(1);

    sort(all(pows));

    ll answr = 0;

    for (auto e : pows){

        ll it = sqrt(2 * e) - 1;

        while (it * (it + 1) <= 2 * e)
            ++it;
        --it;

        answr += it;

    }

    cout << answr;
}

#else

void solve() {

}

#endif

void multisolve() {

    int t;
    cin >> t;

    int i = 1;
    while (t--) {
//        cout << "Case " << (i++) << ": ";
        solve();
        cout << "\n";
    }
}


#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

#ifdef multi
    multisolve();
#else
    solve();
    //    gen();
#endif

}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  long long c1 = 0, c2 = 0, s1 = 0, s2 = 0;
  for (int i = 0; i < n; i++) {
    s1 += a[i];
    s2 += a[i];
    if (i & 1) {
      if (s1 >= 0) {c1 += s1 + 1; s1 = -1;}
      if (s2 <= 0) {c2 += 1 - s2; s2 = 1;}
    } else {
      if (s1 <= 0) {c1 += 1 - s1; s1 = 1;}
      if (s2 >= 0) {c2 += s2 + 1; s2 = -1;}
    }
  }
  cout << min(c1, c2) << endl;
}


Measured memory_bytes: 640
#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    INF = 1001001
    p_min = INF
    cnt = 0
    for pi in P:
        if p_min < pi:
            continue
        else:
            p_min = pi
            cnt += 1
    print(cnt)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()


Measured memory_bytes: 25984
a,b=map(int,input().split())
if a>b and a-b>=2:
  print(2*a-1)
elif a>b and a-b<2:
  print(a+b)
elif b>a and b-a>=2:
  print(2*b-1)
elif b>a and b-a<2:
  print(a+b)
elif a==b:
  print(a+b)

Measured memory_bytes: 9084
n,m,x = map(int,input().split())
t = []
for i in range(n):
  ti = list(map(int,input().split()))
  t.append(ti)
mn = float("inf")
flag = False
for i in range(2**n):
  cost = 0
  a =[0]*m
  j = 0
  while i > 0:
    if i%2 == 1:
      cost += t[j][0]
      for k in range(m):
        a[k] += t[j][1+k]
    i = i//2
    j += 1
  if min(a)>=x:
    flag = True
    if cost < mn:
      mn = cost
if flag:
  print(mn)
else:
  print(-1)

Measured memory_bytes: 68368
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  auto k = readln.chomp.to!int;
  auto x = readln.split.to!(int[]);

  auto ans = 0;
  foreach (xi; x)
    ans += min(xi, k-xi);

  writeln(ans*2);
}


Measured memory_bytes: 256
from queue import Queue

n = int(input())
edges_original = []
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges_original.append((a, b))
    edges[a].append(b)
    edges[b].append(a)

color = {}

# BFS
queue = Queue()
dist = [-1] * n
queue.put((-1, 0))  # (distが等しいノードの中で何番目のノードか, ノード番号)
dist[0] = 0
K = 1

while True:
    num, node = queue.get()
    next_nodes = edges[node]
    tmp_color = 1
    for next_node in next_nodes:
        if dist[next_node] != -1:
            continue
        dist[next_node] = dist[node] + 1

        if tmp_color == num:
            tmp_color += 1
        color[(node, next_node)] = tmp_color
        color[(next_node, node)] = tmp_color
        if tmp_color > K:
            K = tmp_color

        queue.put((tmp_color, next_node))
        tmp_color += 1

    if queue.empty():
        break

print(K)
for edge in edges_original:
    print(color[edge])


Measured memory_bytes: 113052
n = gets.to_i
heights = gets.split.map(&:to_i)

low_connector = n.times.map{Array.new}
high_connector = n.times.map{Array.new}

n.times do |i|
  low_connect = i - heights[i]
  high_connect = i + heights[i]
  if low_connect >= 0
    low_connector[low_connect].push i
  end
  if high_connect < n
    high_connector[high_connect].push i
  end
end

count = 0
n.times.each do |i|
  lower = low_connector[i].size
  higher = high_connector[i].size
  count += lower * higher
end

puts count


Measured memory_bytes: 49264