akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdint>
#include <cmath>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <memory>

#define rep(i,n) for(int i = 0; i < (n); ++i)

using namespace std;

template<class T, class U>
istream& operator>>(istream& is, pair<T, U>& pair)
{
    is >> pair.first >> pair.second;
    return is;
}

template<class T>
istream& operator>>(istream& is, vector<T>& collection)
{
    for(auto& item : collection) is >> item;
    return is;
}

template <class T>
T peak_and_pop(std::queue<T>& q)
{
    assert(!q.empty());
    T t = move(q.front());
    q.pop();
    return t;
}

template <class T>
T peak_and_pop(std::priority_queue<T>& q)
{
    assert(!q.empty());
    T t = move(q.top());
    q.pop();
    return t;
}

template <class T>
T peak_and_pop(std::stack<T>& q)
{
    assert(!q.empty());
    T t = move(q.top());
    q.pop();
    return t;
}

void solution()
{
    int N,K,R,S,P;
    string T;
    cin >> N >> K >> R >> S >> P >> T;
    string A;
    A.reserve(T.size());
    rep(i, N){
        if(T[i] == 'r'){
            A.push_back('p');
        }else if(T[i] == 's'){
            A.push_back('r');
        }else{
            A.push_back('s');
        }
        if(i>=K && A.at(i-K) == A.at(i)){
            A[i] = 'x';
        }
    }
    rep(i, N){
        if(A[i] == 'x'){
            if(A[i-K] == 'r'){
                if(i < N - K && A[i+K] == 'p'){
                    A[i] = 's';
                }else{
                    A[i] = 'p';
                }
            }
            else if(A[i-K] == 'p'){
                if(i < N - K && A[i+K] == 's'){
                    A[i] = 'r';
                }else{
                    A[i] = 's';
                }
            }
            else{
                if(i < N - K && A[i+K] == 'r'){
                    A[i] = 'p';
                }else{
                    A[i] = 'r';
                }
            }
        }
    }
    int score = 0;
    rep(i, N){
        assert(A[i] != 'x');
        if(A[i] == 'r' && T[i] == 's'){
            score += R;
        }else if(A[i] == 's' && T[i] == 'p'){
            score += S;
        }else if(A[i] == 'p' && T[i] == 'r'){
            score += P;
        }
    }
    //cout << A << '\n';
    cout << score << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


Measured memory_bytes: 512
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

struct Scanner<R: Read> {
    reader: R,
    buffer: String,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader, buffer: String::new() }
    }

    // fn line(&mut self) -> String {
    //     self.buffer = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
    //         .skip_while(|&c| c == '\n' || c == '\r')
    //         .take_while(|&c| !(c == '\n' || c == '\r'))
    //         .collect::<String>();
    //     self.buffer.clone()
    // }

    fn read_buffer(&mut self) {
        self.buffer = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        self.read_buffer();
        if self.buffer.is_empty() {
            None
        } else {
            self.buffer.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(std::io::stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.read()).collect()
    }

    fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }
}

trait Joinable {
    fn join(self, sep: &str) -> String;
}

impl<U: ToString, T: Iterator<Item=U>> Joinable for T {
    fn join(self, sep: &str) -> String {
        self.map(|x| x.to_string()).collect::<Vec<_>>().join(sep)
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(104_857_600)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}

fn solve() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let mut stack: Vec<i32> = vec![];
    while let Some(token) = sc.safe_read::<String>() {
        match token.as_str() {
            "+" | "-" | "*" => {
                let y = stack.pop().unwrap();
                let x = stack.pop().unwrap();
                let r = match token.as_str() {
                    "+" => x + y,
                    "-" => x - y,
                    "*" => x * y,
                    _ => panic!(),
                };
                stack.push(r);
            },
            _ => {
                stack.push(token.parse().unwrap());
            }
        }
    }
    println!("{}", stack[0]);
}



Measured memory_bytes: 9052
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	x := nextInt()
	a := nextInt()
	b := nextInt()

	da := x - a
	if da < 0 {
		da *= -1
	}
	db := x - b
	if db < 0 {
		db *= -1
	}

	if da < db {
		fmt.Println("A")
	} else {
		fmt.Println("B")
	}
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

int n;
ll A[2048];
ll memo[2048][2048];

ll joi(int l, int r);
ll ioi(int l, int r);

ll joi(int l, int r) {
  // cout << "joi" << l << r << endl;
  if (l == r) return A[l];
  if (r < 0) return joi(l, r + n);
  if (l >= n) return joi(l - n, r);
  if (memo[l][r] != -1) return memo[l][r];
  return memo[l][r] = max(A[l] + ioi(l + 1, r), A[r] + ioi(l, r - 1));
}

ll ioi(int l, int r) {
  // cout << "ioi" << l << r << endl;
  if (l == r) return 0;
  if (r < 0) return ioi(l, r + n);
  if (l >= n) return ioi(l - n, r);
  if (memo[l][r] != -1) return memo[l][r];
  if (A[l] < A[r]) return memo[l][r] = joi(l, r - 1);
  return memo[l][r] = joi(l + 1, r);
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha;
  cout.imbue(loc);
  memset(memo, -1, sizeof(memo));
  cin >> n;
  REP(i,n) cin >> A[i];
  ll res = 0;
  REP(i,n) {
    chmax(res, A[i] + ioi(i + 1, i - 1));
  }
  cout << res << endl;
  return 0;
}

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

typedef long long ll;

int main() {
  set<int> st;
  int q; cin >> q;
  for(int i=0; i<q; i++){
    int query, x;
    cin >> query >> x;
    if(query==0){
      st.insert(x);
      cout << st.size() << endl;
    }
    else {
      auto itr = st.find(x);
      if(itr != st.end()) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

const int D = 60;
const int MAX_N = 200005;

int to[D][MAX_N];

int main()
{
    int n;
    ll k;
    cin >> n >> k;
    rep(i, n)
    {
        cin >> to[0][i];
        to[0][i]--;
    }
    
    rep(i, D - 1) rep(j, n) to[i + 1][j] = to[i][to[i][j]];
    int v = 0;
    for (int i = D - 1; i >= 0; i--)
    {
        ll l = 1ll << i;
        if (l <= k)
        {
            v = to[i][v];
            k -= l;
        }
    }

    cout << v + 1 << endl;

    return 0;
}


Measured memory_bytes: 50504
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,A,N,M,K,S,T,X,Y,Z;
  cin >> H >> A;
  int loop=0;
  while(1){
    if(loop*A >= H){
      break;
    }
    loop++;
  }

  cout << loop << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int N;
    long long i, sum=0;

    scanf("%d",&N);

    for(i=1; i<=N; i++){
        if((i%3!=0)&&(i%5!=0)){
            sum+=i;
            //printf("i=%lld\n",i);
        }
    }

    printf("%lld\n",sum);

    return 0;
}

Measured memory_bytes: 1732
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    l, r, d = map(int, input().split())
    print(r // d - (l - 1) // d)
resolve()

Measured memory_bytes: 61848
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	k := getNextInt(scanner)
	dp := makeGrid(n+5, k+5)
	dp[0][0] = 1
	for i := 0; i < n+1; i++ {
		for j := 0; j < k+1; j++ {
			dp[i+1][j+1].addAs(dp[i][j])
			dp[i+1][j].addAs(dp[i][j].mul(mint(j)))
		}
	}
	var ans mint
	for i := 0; i <= k; i++ {
		ans.addAs(dp[n][i])
	}
	fmt.Fprintln(writer, ans)
}

func makeGrid(h, w int) [][]mint {
	index := make([][]mint, h, h)
	data := make([]mint, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}

type mint int64

func (mt mint) mod() mint {
	m := mint(1e9 + 7)
	mt %= m
	if mt < 0 {
		return mt + m
	}
	return mt
}
func (mt mint) inv() mint {
	return mt.pow(mint(0).sub(2))
}
func (mt mint) pow(n mint) mint {
	p := mint(1)
	for n > 0 {
		if n%2 == 1 {
			p.mulAs(mt)
		}
		mt.mulAs(mt)
		n >>= 1
	}
	return p
}
func (mt mint) add(x mint) mint {
	return (mt + x).mod()
}
func (mt mint) sub(x mint) mint {
	return (mt - x).mod()
}
func (mt mint) mul(x mint) mint {
	return (mt * x).mod()
}
func (mt mint) div(x mint) mint {
	return mt.mul(x.inv())
}
func (mt *mint) addAs(x mint) *mint {
	*mt = mt.add(x)
	return mt
}
func (mt *mint) subAs(x mint) *mint {
	*mt = mt.sub(x)
	return mt
}
func (mt *mint) mulAs(x mint) *mint {
	*mt = mt.mul(x)
	return mt
}
func (mt *mint) divAs(x mint) *mint {
	*mt = mt.div(x)
	return mt
}



Measured memory_bytes: 9492
def insertion_sort a
  a.each_with_index do |key, i|
    j = i - 1
    while j >= 0 && a[j] > key
      a[j + 1] = a[j]
      j -= 1
    end
    a[j + 1] = key
    puts a.join(' ')
  end
end

n = gets.to_i
a = gets.split.map(&:to_i)

insertion_sort a

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

int main()
{
    unsigned long long N;
    std::cin >> N;

    unsigned long long A[100005];
    unsigned long long B[100005];

    for (unsigned long long i=0; i<N+1; i++){
        std::cin >> A[i];
    }
    for (unsigned long long i=0; i<N; i++){
        std::cin >> B[i];
    }

    unsigned long long sum=0;

    for (unsigned long long i=N; i >= 1; i--){
        if(A[i] >= B[i-1]){
            sum+=B[i-1];
        } else {
            sum+=A[i];
            unsigned long long remain = B[i-1] - A[i];
            if(A[i-1] >= remain){
                sum+=remain;
                A[i-1]-=remain;
            } else {
                sum+=A[i-1];
                A[i-1]=0;
            }
        }
    }

    std::cout << sum << std::endl;

    return 0;
}

Measured memory_bytes: 1792
program dubious_document
  implicit none
  integer       :: n, i, j, k, a(50,26)
  character(50) :: s
  a = 0
  read(*,*) n
  do i = 1, n
    read(*,*) s
    s = trim(adjustl(s))
    do j = 1, len_trim(s)
      k = ichar(s(j:j)) - 96
      a(i,k) = a(i,k) + 1
    end do
  end do
  do i = 1, 26
    k = minval(a(1:n,i))
    if (k.gt.0) then
      do j = 1, k
        write(*,'(a)',advance='no') achar(i+96)
      end do
    end if
  end do
  write(*,*)
end program dubious_document

Measured memory_bytes: 768
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(n), z(n);
    rep(i, n){
        cin >> x[i] >> y[i] >> z[i];
    }

    vector<int> a = {1, -1};
    int ans = 0;
    rep(i, 2){
        rep(j, 2){
            rep(k, 2){
                vector<int> b(n);
                rep(l, n){
                    b[l] = x[l] * a[i] + y[l] * a[j] + z[l] * a[k];
                }
                sort(b.begin(), b.end());
                int tmp = 0;
                rep(i, m){
                    tmp += b[n-1-i];
                }
                if(tmp > ans){
                    ans = tmp;
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n=int(input())
y=0
x=1
for i in range(n):
	a=list(map(int,input().split()))
	if(a[1]+a[2]>a[0]):
		x=0
	elif((a[1]+a[2])%2!=a[0]%2):
		x=0
	else:
		y+=1
if(x==0):
	print("No")
elif(x!=0 and y==n):
	print("Yes")				

Measured memory_bytes: 3064
#include <stdio.h>
#define N 200000
//#define Num 1000000000
int data[N];
int main(){

  int num,i,j,max,min;

  //int data[N];

  scanf("%d",&num);

  for(i = 0 ; i < num ; i++)
    {
      scanf("%d",&data[i]);

    }


  max = data[1] - data[0];
  min = data[0];


  for(j = 1 ; j < num ; j++)
    // {
    //for(i = 0 ; i <= j-1 ; i++)
	{
	  if(data[j] - min > max)max = data[j] - min;
	  if(min > data[j])min = data[j];
	  
	  //	}
    }

  // if(max <= 0)max == -1;

  printf("%d\n",max);

  return 0;
}

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

unsigned long long a[10], n, t, sum;
string S;

int main() {
	a[0] = 1;
	cin >> n >> t;
	cin >> S;
	for (int i = 1; i < 10; i++) {
		if (a[i - 1] * n > 1000000000) {
			a[i] = 2000000000;
		}
		else {
			a[i] = a[i - 1] * n;
		}
	}
	for (int i = 0; i <= S.size() / 4; i++) {
		sum += t*a[S[i * 4 + 2] - 48];
	}
	if (sum > 1000000000) { cout << "TLE" << endl; }
	else { cout << sum << endl; }
	return 0;
}

Measured memory_bytes: 3220
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define ll long long
#define vi vector<int>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int N,M;
string A[55], B[55];

int solve(){
    rep(i,N-M+1){
        rep(j,N-M+1) {
            bool flag = true;
            rep(l,M){
                string tmp = A[i+l].substr(j,M);
                if(tmp != B[l]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                cout << "Yes" << endl;
                return 0;
                }
            }
        }
    cout<<"No"<<endl;
    return 0;
}

int main(){
    cin >> N >> M;

    rep(i,N) cin >> A[i];
    rep(i,M) cin >> B[i];

    solve();
}


Measured memory_bytes: 256
/********************************************
 *Author*        :ZZZZone
 *Created Time*  : 日  3/11 19:56:48 2018
 * Ended  Time*  : 日  3/11 20:12:02 2018
*********************************************/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

inline void OPEN(string s){
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	if(m < n) swap(n, m);
	if(n == 1){
		if(m == 1) printf("1\n");
		else if(m >= 2) printf("%d\n", m-2);
	}
	else if(n == 2) printf("0\n");
	else if(n >= 3) printf("%lld\n", 1LL * (n-2LL)*(m-2LL));
		
    return 0;
}


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

const int Maxn=1e5;
const int Maxlogn=17;

int N;

struct Edge {
	static Edge *ecnt;
	int to,dis,col;
	Edge *nxt;
};
Edge e[2*Maxn+5];
Edge *G[Maxn+5];
Edge* Edge::ecnt=&e[0];
void addedge(int u,int v,int c,int d) {
	Edge *p=++Edge::ecnt;
	p->to=v,p->dis=d,p->col=c;
	p->nxt=G[u],G[u]=p;
}

struct SegmentTree {
	struct Segment {
		int cnt,sum;
		Segment *ch[2];
	};
	Segment t[Maxn*25+5];
	Segment *ncnt,*NIL;
	SegmentTree() {NIL=ncnt=&t[0];NIL->ch[0]=NIL->ch[1]=NIL;}
	Segment * newnode() {
		Segment *ret=++ncnt;
		ret->cnt=ret->sum=0;
		ret->ch[0]=ret->ch[1]=NIL;
		return ret;
	}
	Segment * add(Segment *pre,int l,int r,int pos,int val) {
		Segment *rt=newnode();(*rt)=(*pre);
		if(l==r) {
			rt->cnt++,rt->sum+=val;
			return rt;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			rt->ch[0]=add(pre->ch[0],l,mid,pos,val);
		else rt->ch[1]=add(pre->ch[1],mid+1,r,pos,val);
		return rt;
	}
	void query(Segment *rt,int l,int r,int pos,int &ret_cnt,int &ret_sum) {
		if(l==r) {
			ret_cnt=rt->cnt;
			ret_sum=rt->sum;
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			query(rt->ch[0],l,mid,pos,ret_cnt,ret_sum);
		else query(rt->ch[1],mid+1,r,pos,ret_cnt,ret_sum);
	}
};
SegmentTree T;
SegmentTree::Segment *RT[Maxn+5];

int dep[Maxn+5];
int dis[Maxn+5];
int fa[Maxlogn+5][Maxn+5];
void DFS(int u,int par,int depth) {
	dep[u]=depth;
	fa[0][u]=par;
	for(int i=1;i<=Maxlogn;i++)
		fa[i][u]=fa[i-1][fa[i-1][u]];
	for(Edge *p=G[u];p!=NULL;p=p->nxt) {
		int v=p->to;
		if(v==par)continue;
		RT[v]=T.add(RT[u],1,N,p->col,p->dis);
		dis[v]=dis[u]+p->dis;
		DFS(v,u,depth+1);
	}
}

int CalcLCA(int u,int v) {
	if(dep[u]<dep[v])
		swap(u,v);
	for(int i=Maxlogn;i>=0;i--)
		if(dep[fa[i][u]]>=dep[v])
			u=fa[i][u];
	if(u==v)return u;
	for(int i=Maxlogn;i>=0;i--)
		if(fa[i][u]!=fa[i][v])
			u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}

int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	int Q;
	scanf("%d %d",&N,&Q);
	for(int i=1;i<N;i++) {
		int u,v,c,d;
		scanf("%d %d %d %d",&u,&v,&c,&d);
		addedge(u,v,c,d);
		addedge(v,u,c,d);
	}
	RT[1]=T.NIL;
	DFS(1,0,1);
	while(Q--) {
		int c,d,u,v;
		scanf("%d %d %d %d",&c,&d,&u,&v);
		int lca=CalcLCA(u,v);
		int c1,c2,c3,d1,d2,d3;
		T.query(RT[u],1,N,c,c1,d1),T.query(RT[v],1,N,c,c2,d2),T.query(RT[lca],1,N,c,c3,d3);
		int totc=c1+c2-2*c3,totd=d1+d2-2*d3,pred=dis[u]+dis[v]-2*dis[lca];
//		printf("%d %d %d %d\n",totc,totd,pred,lca);
		printf("%d\n",pred-totd+d*totc);
	}
	return 0;
}

Measured memory_bytes: 72832
n, *aa = open(0).read().split()

def bubble(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        for j in range(n-1, i, -1):
            if aa[j-1][1] > aa[j][1]:
                aa[j-1], aa[j] = aa[j], aa[j-1]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

def selection(aa):
    aa = list(map(list, aa))
    n = len(aa)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if aa[j][1] < aa[mini][1]:
                mini = j
        aa[mini], aa[i] = aa[i], aa[mini]
    aa = list(map(lambda x: ''.join(x), aa))
    return aa

bres = bubble(aa)
sres = selection(aa)

print(*bres)
print('Stable')
print(*sres)
if bres == sres:
    print('Stable')
else:
    print('Not stable')


Measured memory_bytes: 5580
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

const int N = 200005;

vi g[N];
int ans[N];
int nxt[N];

void dfs(int c, int p, int mx, int idx) {
  ans[idx]++;
  rep(i,0,g[c].size()) {
    int u = g[c][i];
    if(u != p) {
      nxt[c] = u;
      int tmp = mx;
      int tmpIdx = idx;
      while(tmp < u && tmpIdx != u) {
        tmp = max(tmp, tmpIdx);
        tmpIdx = nxt[tmpIdx];
      }
      dfs(u, c, tmp, tmpIdx);
    }
  }
}

void dfs2(int c, int p) {
  ans[c] += ans[p];
  rep(i,0,g[c].size()) {
    int u = g[c][i];
    if(u != p) {
      dfs2(u, c);
    }
  }
}

int main() {
  int n;
  S(n);
  rep(i,0,n-1) {
    int u,v;
    S2(u,v);
    g[u].pb(v);
    g[v].pb(u);
  }

  dfs(1, 0, 1, 1);
  ans[0] = ans[1] = 0;
  dfs2(1, 0);
  rep(i,2,n+1) printf("%d ",ans[i]); printf("\n");
  return 0;
}


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

int main()
{
    int A, B, X;
    cin >> A >> B >> X;
    if (A <= X && X <= A + B)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#pragma region header
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#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 rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 2000000000;
const int MINF=-2000000000;
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll kind(vi SYURUI) {//vector<int>型の配列の要素の種類数
    int size = SYURUI.size();
    sort(all(SYURUI));
    int cnt = 1;
    rep(i, size-1) {
        if (SYURUI[i] != SYURUI[i + 1])cnt++;
    }
    return cnt;
}
/* ----------------------end----------------------- */
#pragma endregion

signed main() {
    int N, M, X; cin >> N >> M >> X;
    vi A(M); rep(i, M)cin >> A[i];
    int cnt1 = 0;
    int cnt2 = 0;
    int kijun;
    for (int i = 0;; i++) {
        if (A[i] < X) {
            cnt1++;
        }
        else {
            kijun = i;
            break;
        }
    }
    for (int i = kijun; i < M; i++) {
        cnt2++;
    }
    cout << min(cnt1, cnt2) << endl;
}





Measured memory_bytes: 3764
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

int main(void) {
	int h, w, m;
	cin >> h >> w >> m;
	vector<int> y(m), x(m);
	vector<pair<int, int>> data;
	rep(i, 0, m) {
		cin >> y[i] >> x[i];
		data.push_back({x[i], y[i]});
	}
	map<int, int>mx, my;
	rep(i, 0, m) {
		mx[x[i]]++;
		my[y[i]]++;
	}
	int A = 0, B = 0, d = 1;
	vector<int> tx, ty;
	rep2(m, mx) {
		if (A < m.second)A = m.second, tx.resize(0), tx.push_back(m.first);
		else if (A == m.second)tx.push_back(m.first);
	}
	rep2(m, my) {
		if (B < m.second)B = m.second, ty.resize(0), ty.push_back(m.first);
		else if (B == m.second)ty.push_back(m.first);
	}
	sort(all(data));
	rep2(vx, tx) {
		rep2(vy, ty) {
			if (!binary_search(all(data), make_pair(vx, vy))) {
				d = 0;
			}
		}
		if (d == 0)break;
	}
	printf("%d\n", A + B - d);
	return 0;
}

Measured memory_bytes: 40316
import java.io.*;
 
class Main {
	public static void main (String args[]) {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String buf;
		int n[] = new int[11];
		int i = 0;

		try {
			while ((buf = br.readLine())!=null) {
				n[i] = Integer.parseInt(buf);
				if (n[i]==0) {
					System.out.println(n[i-1]);
					i--;
				}
				else i++;
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 16852
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <random>
#include <complex>

#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define reset(x, y) memset(x, y, sizeof(x))
#define BUG(x) cerr << #x << " = " << (x) << endl
#define BUGP(x) cout << #x << " = " << (x)._1 << ", " << (x)._2 << endl
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int dr[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dc[] = {0, -1, 0, 1, -1, 1, -1, 1};
// Head

const int N = 15;

int n, d;

vector<int> vec[N];

bool check(int u) {
    for (int i = 0; i < 200; i++) {
        if (i * i == u) return true;
    }
    return false;
}

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

    cin >> n >> d;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            int x;
            cin >> x;
            vec[i].pb(x);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int cur = 0;
            for (int k = 0; k < d; k++) {
                int tmp = vec[i][k] - vec[j][k];
                cur += tmp * tmp;
            }

            if (check(cur)) ++ans;
        }
    }

    cout << ans << '\n';
    return 0;
}

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

int main() {
	int mor, aft;
	while(1){
		vector<int> num;
		for(int i = 0; i < 5; i++){
			cin >> mor >> aft;
			if(mor == 0 && aft == 0)goto finished;
			num.push_back(mor + aft);
		}
	
		int ans = 0;
		char shop;
		for(int i = 0; i < 5; i++){
			if(ans < num[i]){
				ans = num[i];
				shop = 'A' + i;
			}
		}
	
		cout << shop << " " << ans << endl;
	}
	finished:
	return 0;
}

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


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




int main() {
	int n;
	cin>>n;
	bool ans = false;
	for(int i = 0;i <= 25; i++){
		for(int j = 0; j<=14; j++){
			if(4*i + 7*j == n) ans = true;
		}
	}
	if(ans) cout<< "Yes" << endl;
	else cout<<"No" <<endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using u32 = uint_fast32_t;
using i32 = int_fast32_t;
using u64 = uint_fast64_t;

struct Segtree {
	u32 n;
	vector<u32> data;
	u32 U = numeric_limits<u32>::min();
	Segtree(u32 N) : n(calc_n(N)), data(n*2, U) {}
	void set(u32 p, u32 v) {
		p += n;
		data[p] = v;
		while (p) {
			p /= 2;
			data[p] = max(data[p*2], data[p*2+1]);
		}
	}
	u32 get(u32 l, u32 r) {
		u32 res = U;
		for (l += n, r += n; l < r; l /= 2, r /= 2) {
			if (l & 1) res = max(res, data[l++]);
			if (r & 1) res = max(res, data[--r]);
		}
		return res;
	}
	u32 get(u32 p) {
		return data[p+n];
	}
private:
	u32 calc_n(u32 N) {
		u32 n = 1;
		while (n < N) n *= 2;
		return n;
	}
};

int main() {
	u32 N;
	cin >> N;
	vector<i32> X(N), D(N);
	{
		vector<pair<i32, i32>> v;
		for (u32 i = 0; i < N; i++) {
			u32 a, b; cin >> a >> b;
			v.emplace_back(a, b);
		}
		sort(v.begin(), v.end());
		for (u32 i = 0; i < N; i++) {
			X[i] = v[i].first;
			D[i] = v[i].second;
		}
	}
	Segtree R(N);
	for (u32 l = N - 1; ~l; l--) {
		R.set(l, l);
		u32 r = lower_bound(X.begin() + l, X.end(), X[l] + D[l]) - X.begin();
		R.set(l, R.get(l, r));
	}
	vector<u64> dp(N+1);
	dp[N] = 1;
	for (u32 i = N - 1; ~i; i--) {
		dp[i] = dp[i+1] + dp[R.get(i)+1];
		dp[i] %= 998244353;
	}
	cout << dp[0] << endl;
}

Measured memory_bytes: 9064
n = gets.to_i
sticks = gets.split.map(&:to_i).sort
sum = 0
sticks.each_with_index do |stick_1, index_1|
  sticks.each_with_index do |stick_2, index_2|
    next if index_2 <= index_1
    max = stick_1 + stick_2
    sum += (sticks.bsearch_index { |s| s >= max } || n) - index_2 - 1
  end
end
puts sum


Measured memory_bytes: 1912
package main

import (
	"fmt"
)

func main() {
	var n, k int64

	fmt.Scan(&n)
	fmt.Scan(&k)

	const M int64 = 1000000007

	answer := int64(0)

	for i := k; i <= n+1; i++ {
		answer += (n*i - i*i + i + 1)
		answer %= M
	}
	fmt.Println(answer)
}


Measured memory_bytes: 1756
X,N = map(int,input().split())

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

count = 0

flg = False

lis=[]

result=0

while True:
    
    up = X+count
    
    down = X-count
    
    if p.count(down) ==0:
        lis.append(down)
        flg = True
    
    if p.count(up)==0:
        lis.append(up)
        flg = True
        
    
    if flg ==True:
        break
    else:
        count+=1
        

lis.sort()

print(lis[0])
    

Measured memory_bytes: 9188
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

div = [a[i] - b[i] for i in range(n)]

if sum(div) < 0:
    print(-1)
    exit()

div.sort()
idx = bisect_left(div, 0)
positive = div[idx:]
negative = div[:idx]

if idx == 0:
    print(0)
    exit()

ans = len(negative)
changed = False

for x in negative:
    x = abs(x)
    while x > positive[-1]:
        x -= positive.pop(-1)
        if not changed:
            ans += 1
        changed = False
    positive[-1] -= x
    if not changed:
        ans += 1
        changed = True

print(ans)


Measured memory_bytes: 23836
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

long long MX = 1e18;

int main() {
    long long n;
    cin >> n;
    string s;
    while(n){
        n--;
        s += 'a' + n%26;
        n /= 26;
    }
    reverse(s.begin(), s.end());
    cout << s << endl;

return 0;
}


Measured memory_bytes: 3596
#include <cstdio>

int main()
{
int k, s;

scanf("%d %d", &k, &s);

int ans = 0;
for (int i = 0; i <= k; i++){
    int t = s - i;
    int buf;
    if (t <= k){
        buf = t + 1;
    } else {
        buf = 2 * k + 1 - t;
    }

    if (buf > 0){
        ans += buf;
    }
}

printf("%d\n", ans);

return 0;
}


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

const ll mod = 1e9 + 7;
const int MAX = 200;

ll hs[MAX];

void init() {
	mt19937 mt(random_device{}());
	for (int i = 0; i < MAX; i++) {
		hs[i] = mt() % mod;
	}
}

struct node {
	int a, b;
	ll val;
	int flag;
	node *lch, *rch;
	node(node* l = nullptr, node* r = nullptr) : lch(l), rch(r) {}
};

int it;
string s, ans;

node* get_tree() {
	if (s[it] == 'x') {
		++it;
		return new node;
	}
	assert(s[it++] == '(');
	auto lc = get_tree();
	assert(s[it++] == ' ');
	auto rc = get_tree();
	assert(s[it++] == ')');
	return new node(lc, rc);
}

ll get_hs(node* t, int d = 0) {
	if (!t->lch) return 1;
	return (hs[d] + get_hs(t->lch, d + 1)) * (hs[d] + get_hs(t->rch, d + 1)) % mod;
}

vector<int> get_val(node* t) {
	if (!t->lch) {
		t->a = 0, t->b = 1;
		t->val = 1;
		return{ 1 };
	}
	vector<int> res;
	auto x = get_val(t->lch), y = get_val(t->rch);
	t->a = 0, t->b = x.size() + y.size();
	for (auto v : x) {
		if (binary_search(y.begin(), y.end(), v)) {
			--t->b;
			++t->a;
		}
	}
	copy(x.begin(), x.end(), back_inserter(res));
	copy(y.begin(), y.end(), back_inserter(res));
	res.push_back(get_hs(t));
	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());
	return res;
}

int comp(node* t1, node* t2) {
	if (t2->b * t1->a != t1->b * t2->a) return t2->b * t1->a > t1->b * t2->a ? -1 : 1;
	if (!t1->lch && !t2->lch) return 0;
	node *p1 = t1->lch, *p2 = t1->rch, *p3 = t2->lch, *p4 = t2->rch;
	if (t1->flag < 0) swap(p1, p2);
	if (t2->flag < 0) swap(p3, p4);
	int tmp = comp(p1, p3);
	if (tmp != 0) return tmp;
	return comp(p2, p4);
}

void get_flag(node* t) {
	if (!t->lch) return;
	get_flag(t->lch);
	get_flag(t->rch);
	t->flag = comp(t->lch, t->rch);
}

void fix(node* t, bool left = true) {
	if (!t->lch) return;
	if (left) {
		if (t->flag < 0) swap(t->lch, t->rch);
	}
	else {
		if (t->flag > 0) swap(t->lch, t->rch);
	}
	fix(t->lch, true);
	fix(t->rch, false);
}

void make_tree(node* t) {
	if (!t->lch && !t->rch) {
		ans.push_back('x');
		return;
	}
	ans.push_back('(');
	make_tree(t->lch);
	ans.push_back(' ');
	make_tree(t->rch);
	ans.push_back(')');
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	init();
	while (getline(cin, s), s != "0") {
		it = 0;
		node *tree = get_tree();
		get_val(tree);
		get_flag(tree);
		fix(tree);
		make_tree(tree);
		cout << ans << endl;
		ans.clear();
	}
	return 0;
}



Measured memory_bytes: 3984
#include<iostream>
#include<map>

using namespace std;

int main(){
    int N;
    cin>>N;
    map<long ,long> mp;

    for(long i=0;i<N;++i){
        long long tmp;
        cin>>tmp;

        mp[tmp]++;
    }
    long ans=0;
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        if(itr->second>itr->first){
            ans+=abs(itr->second-itr->first);
        }else if(itr->second<itr->first){
            ans+=itr->second;
        }
    }


    cout<<ans<<endl;
}

Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N;
    cin >> N;
    vector<int> P(N);
    rep(i, N) cin >> P[i];

    int ans = 0;
    int MIN = 1e9;
    rep(i, N){
        if(MIN >= P[i]){
            MIN = P[i];
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    ll n,ans=0;cin>>n;
    vector<ll> a(n),b(n);
    rep(i,n){
        cin>>a[n-1-i]>>b[n-1-i];
    }

    for(int i=0;i < n;i++)
    {
        if(b[i]!=1 && ((a[i]+ans)%b[i])!=0) ans+=b[i]-((a[i]+ans)%b[i]);
    }

    cout<<ans<<endl;
}



Measured memory_bytes: 1792
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define X first
#define Y second
 
//#include <boost/unordered_map.hpp>
//using namespace boost;
 
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/
 
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;
 
ll power(ll a, ll b, ll p)
{
    if (!b) return 1;
    ll t = power(a, b/2, p);
    t = t*t%p;
    if (b&1) t = t*a%p;
    return t;
}
 
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll px, py;
    ll d = exgcd(b, a%b, px, py);
    x = py;
    y = px-a/b*py;
    return d;
}
 
template<class T>
inline void freshmin(T &a, const T &b)
{
    if (a > b) a = b;
}
 
template<class T>
inline void freshmax(T &a, const T &b)
{
    if (a < b) a = b;
}
 
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
 
int inp() {
    int x = 0, f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
ll inp_ll() {
    ll x = 0; int f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
template<class T>
bool read(T &x)
{
    x = 0;
    char ch = getchar();
    if (ch == EOF) return 0;
    for(; !isdigit(ch); )
    {
        ch = getchar();
        if (ch == EOF) return 0;
    }
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return 1;
}
 
template<class T>
void write(T x)
{
    static char s[22];
    static char *it = s+20;
    static char *end = s+20;
    if (!x)
        *-- it = '0';
    while (x)
    {
        *-- it = x%10+'0';
        x /= 10;
    }
    for (; it < end; ++ it)
        putchar(*it);
}
 
template<class T>
void writeln(T x)
{
    write(x);
    putchar('\n');
}
 
const int MAXN = 200010;
const int INF = 1000000000;
const int MOD = 1000000007;

int n, a[MAXN], f[MAXN][2];

int main()
{
	
	n = inp();
	for (int i = 1; i <= n; ++ i)
		a[i] = inp();
	f[1][0] = f[1][1] = 1;
	for (int i = 2; i <= n; ++ i)
	{
		for (int x = 0; x < 2; ++ x)
			for (int y = 0; y < 2; ++ y)
			{
				if (f[i-1][x] && a[i-1]-x <= a[i]-y) f[i][y] = 1;
			}
	}
	puts(f[n][0] || f[n][1] ? "Yes" : "No");
	
	return 0;
}


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

int main(){
    string a;
    cin>>a;
    int n=a.length();

    int res=0;
    int i=0,j=n-1;
    while(i<j){
        if(a[i]!=a[j]){
            if(a[i]!='x'&&a[j]!='x'){
                puts("-1");
                return 0;
            }
            if(a[i]=='x'){
                ++i;
            } else{
                --j;
            }
            ++res;
        } else{
            ++i;
            --j;
        }
    }

    printf("%d",res);
    return 0;
}

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

int main(){
	bool S[13] = {false},
		 H[13] = {false},
		 C[13] = {false},
		 D[13] = {false};
	int n, num;
	char c[1];
	
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> c[0] >> num;
		switch(c[0]){
		case 'S':
			S[num-1] = true;
			break;
		case 'H':
			H[num-1] = true;
			break;
		case 'C':
			C[num-1] = true;
			break;
		case 'D':
			D[num-1] = true;
			break;
		}
	}
	
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 13; j++){
			switch(i){
			case 0:
				if(S[j] == false){
					cout << "S " << j+1 << endl;
				}
				break;
			case 1:
				if(H[j] == false){
					cout << "H " << j+1 << endl;
				}
				break;
			case 2:
				if(C[j] == false){
					cout << "C " << j+1 << endl;
				}
				break;
			case 3:
				if(D[j] == false){
					cout << "D " << j+1 << endl;
				}
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    S = input().rstrip('\n')
    ans = deque()
    ans.append(S)
    q = int(input())
    rev = 1
    for _ in range(q):
        query = input().rstrip('\n')
        if query == '1':
            rev *= -1
        else:
            _, f, c = query.split()
            if rev == 1:
                if f == '1':
                    ans.appendleft(c)
                else:
                    ans.append(c)
            else:
                if f == '1':
                    ans.append(c)
                else:
                    ans.appendleft(c)
    ans = ''.join(ans)
    if rev == -1:
        ans = ans[::-1]
    print(ans)


if __name__ == '__main__':
    main()


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

bool is_integer( double x ){
  return floor(x)==x;
}

bool Check(int n){
    
   if(n == 1) return true;
   if(n == 1000) return true;
   else for(int i=2;i<=10;i++) if(is_integer(pow(n,1.0/i))) return true;
   return false;
}

int main(void){
    
    int X;
    cin >> X;
    for(int i=X;i>=1;i--){
        if(Check(i)) {
            cout << i << endl;
            return 0;   
        }
    }
}

Measured memory_bytes: 3992
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    H = [int(h) for h in input().split()]
    finished = [False] * (N + 1)
    finished[N] = True
    for i in range(N): 
        if H[i] == 0: finished[i] = True
    ch = [0] * N
    count = 0
    while False in finished:
        i = 0
        while i < N:
            if not finished[i]:
                count += 1
                start = i
                end = i + 1
                index = i
                while end <= N:
                    if not finished[end]:
                        end += 1
                    else:
                        for j in range(start, end):
                            ch[j] += 1
                            if ch[j] == H[j]:
                                finished[j] = True
                        break
                i = end
                #print(ch)
            else: i += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

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

using namespace std;

typedef long long ll;

int N, Q;
vector<vector<int>> E;
ll X[200000], ans[200000];

void dfs(int pos, int parent, ll plus) {
	ans[pos] = (plus + X[pos]);

	for (int i = 0; i < E[pos].size(); i++) {
		int next = E[pos][i];
		if (next == parent) continue;
		dfs(next, pos, ans[pos]);
	}
}

int main() {
	cin >> N >> Q;
	E.resize(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}

	for (int i = 0; i < Q; i++) {
		int p;
		ll x;
		cin >> p >> x;
		X[p - 1] += x;
	}

	dfs(0, -1, 0);

	for (int i = 0; i < N; i++) {
		cout << ans[i];
		if (i < N - 1)cout << " ";
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 25600
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

int main() {
	cout << fixed << setprecision(12);	
	int n;
	string s;
	cin >> n;
	cin >> s;
	int r = 0, b = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'R') {
			r++;
		} else {
			b++;
		}
	}
	if (r > b) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 3624