akhauriyash/Code-Regression huggingface dataset:
from collections import deque

def find_negative_loop():
    INF = float('inf')
    V, E, r = map(int ,input().split())

    dist = [INF] * V
    dist[r] = 0    
    es = deque()
    
    for i in range(E):
        s, t, d = map(int, input().split())        
        es.append((s, t, d))
    
    for i in range(V):
        for e in es:
            f, t, c = e
            if dist[f] != INF and dist[t] > dist[f] + c:
                dist[t] = dist[f] + c
                if i == V - 1: return True, dist
    return False, dist

def main():
    INF = float('inf')
    is_negative, dist = find_negative_loop()
    
    if is_negative: print('NEGATIVE CYCLE')
    else:
        for d in dist:
            if d == INF: print('INF')
            else: print(d)

if __name__ == '__main__':
    main()


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

void input()
{ 
    #ifndef ONLINE_JUDGE 
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    #endif
}
#define endl "\n"
#define ll long long int
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define tll tuple<ll,ll,ll>
#define mt make_tuple
#define len length
#define INF LONG_LONG_MAX
#define mod 1000000007ahhellllloou
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define cases ll t; cin>>t; while(t--)
#define array(a,n) ll a[n]; rep(i,0,n) cin>>a[i];
#define vector(a,n) vll a(n); rep(i,0,n) cin>>a[i];
#define sortall(a) sort(a.begin(),a.end())
#define printall(a,n) rep(i,0,n) cout<<a[i]<<" "; cout<<endl;

// --------------- My Template End --------------- //
int main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    //input();
  	ll a,c;
	string str;
	
  	cin>>a>>str;
  	c=(str[0]-'1'+1)*100+(str[2]-'1'+1)*10+((str[3]-'1'+1));
  

  		cout<<(ll)(a*c)/100;
}   

Measured memory_bytes: 3664
#include<iostream>
#include<cstdio>
using namespace std;
int m,d;
int main()
{
	scanf("%d%d",&m,&d);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		for(int d10=2;d10<=d/10;d10++)
			if(i%d10==0)
			{
				int d1=i/d10;
				if(d1>=2&&d1<=9&&d10*10+d1<=d) ans++;
			}
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 3756
#include <stdio.h>

int main(){

  int i,j,N,flag,A[100],count=0,tmp;

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  flag=1;
  while(flag){
    flag=0;
    for(j=N-1;j>=1;j--){
      
      if(A[j] < A[j-1]){
	tmp=A[j];
	A[j]=A[j-1];
	A[j-1]=tmp;
	flag=1;
	count++;
      }
      
    }
    
  }
  for(j=0;j<N;j++){
    if(j>0) printf(" ");
    printf("%d",A[j]);
  }
  printf("\n");
  printf("%d\n",count);

  return 0;
}



Measured memory_bytes: 2140
import java.util.Scanner;



public class Main {
	//C - Prison


	public static void main(String[] args){
		int N;int M;
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();

		boolean[]Ans=new boolean[N+1];
		for(int i=0;i<N+1;i++) {
			Ans[i]=true;
		}
		for(int i=0;i<M;i++) {
			int L=sc.nextInt();
			int R=sc.nextInt();
			for(int j=0;j<L;j++) {
				Ans[j]=false;
			}
			for(int j=R+1;j<N+1;j++) {
				Ans[j]=false;
			}
		}
		int num=0;
		for(int i=0;i<N+1;i++) {
			if(Ans[i])num++;
		}
		System.out.println(num);


	}
}

Measured memory_bytes: 64972
#include <stdio.h>

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long llong;

static llong comb(int n) {
  return (llong)n * (n - 1) / 2;
}

void DBannedK(std::istream& in, std::ostream& out) {
  int N;
  in >> N;
  vector<int> data;
  map<int, int> hist;
  for (int i = 0; i < N; ++i) {
    int a;
    in >> a;
    data.push_back(a);
    auto it = hist.find(a);
    if (it == hist.end()) {
      hist.insert({a, 1});
    } else {
      ++(it->second);
    }
  }

  llong all = 0;
  for (const auto& it : hist) {
    all += comb(it.second);
  }

  for (int i = 0; i < N; ++i) {
    llong orig = comb(hist[data[i]]);
    llong nval = comb(hist[data[i]] - 1);
    out << (all - (orig - nval)) << endl;
  }
}

int main(int argc, char** argv) { DBannedK(cin, cout); return 0; }


Measured memory_bytes: 8308
s=list(map(ord,list(input())))
k=int(input())

for i in range(len(s)):
    s[i]-=97

c=0
while k>0:
    if c==len(s)-1:
        s[c]=(s[c]+k)%26
        k=0
    elif s[c]==0:
        c+=1
    elif s[c]+k>=26:
        k-=26-s[c]
        s[c]=0
        c+=1
    else:
        c+=1

seq=""
for i in range(len(s)):
    seq+=chr(s[i]+97)

print(seq)
    

Measured memory_bytes: 4792
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
int dp[1<<16],d[16][17],n;
int b(int s){
  if(dp[s]!=-1)return dp[s];
  if(s==(1<<n)-1)return dp[s]=0;
  int res=1<<26;
  r(i,n)if(!((s>>i)&1)){
    int p=d[i][0];
    r(j,n)if((s>>(j))&1)
      p=min(p,d[i][j+1]);
    res=min(res,b(s|(1<<i))+p);
  }
  return dp[s]=res;
}
main(){
  while(cin>>n,n){
    r(i,n)r(j,n+1)cin>>d[i][j];
    memset(dp,-1,sizeof(dp));
    cout<<b(0)<<endl;
  }
}

Measured memory_bytes: 3324
import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, k, q = map(int, input().split())
    a = []
    for _ in range(q):
        a.append(int(input()))
    a = collections.Counter(a)
    for i in range(1, n+1):
        if k - (q - a[i]) > 0:
            print('Yes')
        else:
            print('No')

if __name__ == '__main__':
    main()

Measured memory_bytes: 16692
#include <iostream>
#include <cmath>

int main(void)
{
    int L, R;
    std::cin >> L >> R;

    int _L = L % 2019;
    int _R = R % 2019;
    
    int min = (_L * _R) % 2019;
    
    if(L % 2019 == 0 || R % 2019 == 0)
    {
        min = 0;
    }

    else if(L < 2019 && R > 2019)
    {
        min = 0;
    }

    else if(R - L >= 2019)
    {
        min = 0;
    }

    else
    {
        int tmp;

        for(int i = L; i <= R; i++)
        {
            tmp = i % 2019;
            if(_L > tmp)
            {
                _L = tmp;
            }

            if(_R < tmp)
            {
                _R = tmp;
            }
        }

        for(int i = _L; i < _R; i++)
        {
            for(int j = i + 1; j <= _R; j++)
            {
                int res = (i * j) % 2019;
                if(res < min)
                {
                    min = res;
                }
            }
        }
    }
    std::cout << min << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char S[100010][15];
int n;
map<string,int> mp;
map<string,bool> vis;
long long ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%s",S[i]+1);
	for(int i=1;i<=n;i++){
		int len=strlen(S[i]+1);
		sort(S[i]+1,S[i]+1+len);
		string res="";
		for(int j=1;j<=len;j++)res+=S[i][j];
		mp[res]++;
	}
	for(int i=1;i<=n;i++){
		int len=strlen(S[i]+1);
		string res="";
		for(int j=1;j<=len;j++)res+=S[i][j];
		if(vis[res]==false)ans+=1LL*mp[res]*(mp[res]-1)/2,vis[res]=true;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 26752
fn main() {
    let s = read::<String>().chars().collect::<Vec<char>>();
    let t = s.clone().into_iter().rev().collect::<Vec<char>>();
    let len = s.len();

    let mut count = 0;
    for i in 0..len / 2 {
        if s[i] != t[i] {
            count += 1;
        }
    }
    println!("{}", count);
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<stdio.h>
int main()
{
	int x,i,c=0;
	scanf("%d",&x);
	while(1){
		for(i=1;i<=x;i++){
			if(x%i==0) c++;
		}
		if(c==2){
			break;
		}
		c=0;
		x++;
	}
	printf("%d\n",x);
	return 0;
}


Measured memory_bytes: 1724
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	input := scanner.Text()
	inputList := strings.Split(input, " ")
	r, _ := strconv.Atoi(inputList[0])

	fmt.Println(r * r)
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
string s,d="CODEFESTIVAL2016";
int ans=0;
signed main(){
    cin>>s;
    rep(i,16){
        if(s[i]!=d[i])ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORE(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define SP cout << fixed << setprecision(10)
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int N, M, Q, L[200009], R[200009], X[509][509], C[509][509];

int main(void) {
    // code
    cin >> N >> M >> Q;
    for (int i = 1; i <= M; i++) {
        cin >> L[i] >> R[i];
        X[L[i]][R[i]]++;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) C[i][j] = C[i][j - 1] + X[i][j];
    }
    for (int i = 1; i <= Q; i++) {
        int p, q;
        cin >> p >> q;
        int sum = 0;
        for (int j = p; j <= q; j++) sum += C[j][q] - C[j][p - 1];
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
const int maxn=2e5+10;
const int mod=998244353;
int a[3005][3005];
ll dp[3005][3005][5];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r,c,k;
    cin>>r>>c>>k;
    while(k--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=z;
    }
    ll ans=0;
    for(int i=1;i<=r;i++)
    {
        dp[i][1][0]=dp[i-1][1][1];
        dp[i][1][1]=dp[i-1][1][1]+a[i][1];
        dp[i][1][2]=dp[i][1][3]=dp[i][1][1];
        ans=max(ans,dp[i][1][1]);
    }
    /*for(int i=1;i<=c;i++)
    {
        for(int x=1;x<=3;x++)
        {
            dp[1][i][x]=max(dp[1][i-1][x],dp[1][i-1][x-1]+a[1][i]);
            ans=max(ans,dp[1][i][x]);
        }
    }*/

    for(int i=1;i<=r;i++)
    {
        for(int j=2;j<=c;j++)
        {
            dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][3]);
            ans=max(ans,dp[i][j][0]);
            for(int x=1;x<=3;x++)
            {
                dp[i][j][x]=max(dp[i-1][j][3]+a[i][j],max(dp[i][j-1][x],dp[i][j-1][x-1]+a[i][j]));
                ans=max(ans,dp[i][j][x]);
            }
        }
    }
    cout<<ans<<'\n';


}


Measured memory_bytes: 390888
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();
		sc.close();
		if (Math.abs(a - b) <= d && Math.abs(b - c) <= d||Math.abs(a-c)<=d) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


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

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

using namespace std;

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

int main(){
	int n; scanf("%d",&n);
	int ans=0;
	rep(i,n){ int a; scanf("%d",&a); ans=gcd(ans,a); }
	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.array, std.conv;

long solve(long x, long y) {
    import std.numeric;
    long d = gcd(x, y);
    long[] factors = [1];
    while (d % 2 == 0) {
        d /= 2;
        if (factors[$-1] != 2) factors ~= 2;
    }
    for (long i = 3; i * i <= d; i += 2) {
        while (d % i == 0) {
            d /= i;
            if (factors[$-1] != i) factors ~= i;
        }
    }
    if (d != 1) factors ~= d;
    return factors.length;
}

void main() {
    long[] tmp = readln.chomp.split.to!(long[]);
    long a = tmp[0], b = tmp[1];
    solve(a, b).writeln;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <cstring>
#include <functional>
//#include<unordered_map>
//#include<unordered_set>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF ((Int)1<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P; 
const int N = 200005;
//////////////////////////////

int h, w;
char s[111][111];
int dp[111][111];

void solve()
{
	cin >> h >> w;
	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++)
			cin >> s[i][j];

	for (int i = 0; i <= h; i++) dp[i][0] = INF;
	for (int j = 0; j <= w; j++) dp[0][j] = INF;
	dp[1][1] = s[1][1] == '.' ? 0 : 1;

	for (int i = 1; i <= h; i++)
		for (int j = 1; j <= w; j++) {
			if (i == 1 && j == 1) continue;
			
			if (s[i][j] == '.') {
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
			}
			else {
				dp[i][j] = min(dp[i - 1][j] + (s[i - 1][j] == '.'), dp[i][j - 1] + (s[i][j - 1] == '.'));
			}
		}
	cout << dp[h][w] << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);
	solve();
	return 0;
}


Measured memory_bytes: 3704
A,B=map(int,input().split())
k=len(bin(B))-2
ans=0
for i in range(k):
  diff=(B- max(2**i,A))
  t=2**(i+1)
  l=2**i
  tmp=((diff+1)//t)*l
 
  C=max(A,l)+tmp*t - 1
  if B%t >= C%t:
    tmp+= max(0,(B%t -(l-1)) - max(0,(C%t-(l-1))))
  else:
    tmp+= max(0,B%t-(l-1)) +(min(l,t-1-C%t))
  if tmp%2==1:
    ans+=2**i
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
#include <bitset>
#include <unordered_map>

using namespace std;



unordered_map<bitset<21>, int> memo;

const int M = 1000000007;
int dfs(const vector<vector<int> > &m, int i, bitset<21> &s) {
	auto it = memo.find(s);
	if(it != memo.end()) return it->second;
	int N = m.size();
	if(s.count() == N) return 1;

	int out = 0;
	for(int j = 0; j < N; j++) {
		if(s[j] == false && m[i][j] == 1) {
			auto z = s;
			z[j] = true;
			out += dfs(m, i + 1, z);
			out %= M;
		}
	}
	memo.emplace(s, out);
	return out;
}

int main() {
	int N;
	cin >> N;
	vector<vector<int> > m(N, vector<int>(N));

	for(auto &r: m)
		for(auto &x: r) cin >> x;
	bitset<21> s;
	cout << dfs(m, 0, s) << endl;
}


Measured memory_bytes: 124228
#include<iostream>

bool inNine(int n){
  if(n%10 == 9)  return true;
  else if((n/10) > 0)  return inNine(n/10);
  else  return false;
}

int main(void){
  int n;  std::cin >> n;
  if(inNine(n))  std::cout << "Yes" << std::endl;
  else  std::cout << "No" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dep[N],a[N],val[N];
vector<int> e[N];
struct node{
	int id,dep;
	bool friend operator <(node i,node j){
		return i.dep<j.dep;
	}
}c[N];
int cnt,vl[N],ans;
void redfs(int x,int fath){
	for(int i=0;i<e[x].size();++i)
		if(e[x][i]!=fath) ans+=min(vl[x],vl[e[x][i]]),redfs(e[x][i],x);
}
void dfs(int x,int fath){
	dep[x]=dep[fath]+1;
	c[++cnt].id=x; c[cnt].dep=dep[x];
	for(int i=0;i<e[x].size();++i)
		if(e[x][i]!=fath) dfs(e[x][i],x);
}
signed main(){
	int n,u,v;
	cin>>n;
	for(int i=1;i<n;++i){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i)
		cin>>val[i];
	dfs(1,0);
	sort(c+1,c+n+1);
	sort(val+1,val+n+1,greater<int>());
	for(int i=1;i<=n;++i)
		vl[c[i].id]=val[i];
	redfs(1,0);
	cout<<ans<<endl;
	for(int i=1;i<=n;++i)
		cout<<vl[i]<<" ";
	return 0;
}

Measured memory_bytes: 6860
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout(val) cout << std::fixed << std::setprecision(20) << val;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };

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

  int n; cin >> n;
  vector<int> b(n);
  rep(i, n) cin >> b[i];

  deque<int> ans;

  while(true) {
    bool found = 0;
    vector<int> next;
    for(int i = b.size() - 1; i >= 0; --i) {
      if(!found && b[i] == i + 1) {
        found = 1;
        ans.push_front(b[i]);
      } else {
        next.push_back(b[i]);
      }
    }
    if(!found) break;
    reverse(next.begin(), next.end());
    b = next;
  }

  if(ans.size() == n) {
    rep(i, n) {
      cout << ans[i] << endl;
    }
  } else {
    cout << -1 << endl;
  }
}


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

int mylast(int x){
    while(x >= 10){
        x /= 10;
    }
    return x;
}
int main(){
    int N;
    cin >> N;


    vector<vector<int>> count(10, vector<int>(10));
    for(int i = 1;i <= N;i++){
        int first = i % 10;
        int last = mylast(i);
        count[first][last]++;
    }

    long long ans = 0;
    for(int i = 1;i <= 9;i++){
        for(int j = i + 1;j <= 9;j++){
            ans += count[i][j] * count[j][i] * 2;
        }
        ans += count[i][i] * count[i][i];
    }
    cout << ans << endl;


    // for(int i = 1;i <= 9;i++){
    //     for(int j = 1;j <= 9;j++){
    //         cout << i << ", " << j << ", " << count[i][j] << endl;
    //     }
    // }




}


Measured memory_bytes: 256
//marico el que lo lea
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <assert.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;

void fastIO() {
	std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
}

#define FOR(i,f,t) for(int i=f; i<(int)t; i++)
#define FORR(i,f,t) for(int i=f; i>(int)t; i--)
#define FORE(i,c) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define all(obj) obj.begin(), obj.end()
#define ms(obj, val) memset(obj, val, sizeof(obj))
#define ms2(obj, val, sz) memset(obj, val, sizeof(obj[0])*sz)

#define fst first
#define snd second

template<typename T, typename U> inline void mnze(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void mxze(T &x, U y) { if(x < y) x = y; }

void _scan( int &x ) { scanf("%d",&x); }
void _scan( long long &x ) { scanf("%lld",&x); }
void _scan( double &x ) { scanf("%lf",&x); }
void _scan( char &x ) { scanf(" %c",&x); }
void _scan( char *x ) { scanf("%s",x); }
void scan() {}
template<typename T, typename... U>
void scan( T& head, U&... tail ) { _scan(head); scan(tail...);}

template<typename T> void _dbg(const char* sdbg, T h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename T, typename... U> void _dbg(const char* sdbg, T h, U... t) {
	while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(_i, (x)) cerr <<*_i <<", "; cerr <<"\n"; }}
#define debuga(x, sz) {{cerr <<#x <<" = "; FOR(_i, 0, sz) cerr << x[_i] <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define debuga(x, sz)
#define cerr if(0)cout
#endif

///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 2e5+5;

char S[MAXN];
int N, a[MAXN];
vi occ[26];
vector<ii> v;

int BIT[MAXN];
void BIT_upd(int p, int val){
	p++;
	for(; p <= N; p += p & -p)
		BIT[p] += val;
}

int BIT_sum(int p){
	int ret = 0;
	p++;
	for(; p; p -= p & -p)
		ret += BIT[p];
	return ret;
}

ll invcnt(){
	ll ret = 0;
    FORR(i,N-1,-1){
        ret += BIT_sum(a[i]);
        BIT_upd(a[i],1);
    }
    return ret;
}

int main(){
    scan(S);
    N = strlen(S);
    FOR(i,0,N) occ[S[i]-'a'].pb(i);
    int cnt=0;
    FOR(i,0,26){
        int x = occ[i].size();
        FOR(j,0,x/2){
            v.pb({occ[i][j], occ[i][x-1-j]});
        }
        if(x%2){
            v.pb({N,occ[i][x/2]});
            cnt++;
        }
    }
    if(cnt>1){
        printf("-1\n");
        return 0;
    }
    sort(all(v));
    FOR(i,0,v.size()){
        a[v[i].fst]=i;
        a[v[i].snd]=N-1-i;
        if(v[i].fst == v[i].snd) a[v[i].fst] = N;
    }
    printf("%lld\n",invcnt());
}


Measured memory_bytes: 4596
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;
 
int main(){
    
    char S[60]={};
    int K,N;

    cin>> N>>K;
    
    for(int i=1;i<=N;i++){
        cin >> S[i];
    }

    if(S[K]=='A'){
        S[K]='a';
    }else if(S[K]=='B'){
        S[K]='b';
    }else{
        S[K]='c';
    }

    for(int i=1;i<=N;i++){
        cout << S[i];
    }

    return 0;
}

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

int main()
{
    int height[10];
    for(int i=0; i<10; i++) std::cin >> height[i];
    std::sort(height, height+10);
    for(int i=9; i>6; i--) std::cout << height[i] << std::endl;;
    return 0;
}


Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = sz(s);
    string t = "";
    rep(i, n) {
        if (i+1 < n && s[i] == 'B' && s[i+1] == 'C') {
            i++;
            t += 'D';
        } else {
            t += s[i];
        }
    }
    
    int m = sz(t);
    ll cntA = 0;
    ll ans = 0;
    rep(i, m) {
        if (t[i] == 'A') cntA++;
        else if (t[i] == 'D') ans += cntA;
        else cntA = 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 916
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;


//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用

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

	int n;
	cin >> n;

	vector<int> p(n);
	rep(i, n)
	{
		cin >> p[i];
	}

	int ans = 0;

	for (int i = 1; i < n - 1; i++)
	{
		if (p[i - 1] <= p[i] && p[i] <= p[i + 1])
		{
			ans++;
		}
		else if (p[i + 1] <= p[i] && p[i] <= p[i - 1])
		{
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  $b = [];
  for ($i=0; $i<$n; $i++) {
    list($a[$i]) = explode(" ", trim(fgets(STDIN)));
    $b[$i] = [];
    for ($j=0; $j<$a[$i]; $j++){
      list($y, $z) = explode(" ", trim(fgets(STDIN)));
      $b[$i][$y] = $z;
    }
  }

  $max_honest_cnt = 0;

  // bit全探索 (2^n通り)
  for ($bit=0; $bit<(1<<$n); $bit++) {
    // 初期化
    $honest_cnt = 0;
    $valid = true;
    // 1～N番目までをチェック
    for ($i=1; $i<=$n; $i++) {
      // i番目が正直者の場合
      if($bit & (1<<($i-1))){
        $honest_cnt++;
//        if($bit === 7){
//          echo $honest_cnt.PHP_EOL;
//        }

        // i番目の証言で矛盾がないかチェック
        foreach($b[$i-1] as $key => $value){
          // 正直者が正直者リストの中にいない
          if($value == 1){
            if(!($bit & (1<<($key-1)))) {
              $valid = false;
              break;
            }
          }
          // 不親切が正直者リストの中にいる
          else {
            if($bit & (1<<($key-1))) {
              $valid = false; 
              break;
            }
          }
        }
        if(!$valid){
          break;
        }
      }
    }
    // 矛盾なし
    if($valid){
//      echo $bit.PHP_EOL;
      $max_honest_cnt = max($max_honest_cnt, $honest_cnt);
    }
  }

  echo $max_honest_cnt;

Measured memory_bytes: 4856
#include <iostream>

using namespace std;

int main()
{
	int a,b, count;
	while( cin >>a>>b ) {
		count = 1;
		a += b;
		while( a > 9 ){
			a /= 10;
			count++;
		}
		cout << count << endl;
	}


	return 0;
}

Measured memory_bytes: 0
S=input()

if S[0]!="A":
  print("WA")
else:
  cnt_C=0
  for i in range(2,len(S)-1):
    if S[i]=="C":
      cnt_C+=1
      
  if cnt_C!=1:
    print("WA")
  else:
    cnt_upper=0
    for i in range(len(S)):
      if S[i].isupper():
        cnt_upper+=1
        
    if cnt_upper!=2:
      print("WA")
    else:
      print("AC")
  

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] c = br.readLine().toCharArray();
		System.out.println(++c[0]);
	}

}


Measured memory_bytes: 21204
//ÕÅ¼ÒÆæÔõÃ´ÓÖAKIOIÁËÑ½£¬ÔõÃ´CSPÒ²Âú·Ö°¡...ÔõÃ´Çå±±ÌìÌì¸øËû´òµç»°°¡...ÔõÃ´»áÓÐÕâÃ´Ç¿µÄÈË°¡
#include<bits/stdc++.h>
#define writeln(x)  write(x),puts("")
#define writep(x)   write(x),putchar(' ')
using namespace std;
inline int read(){
	int ans=0,f=1;char chr=getchar();
	while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
	while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
	return ans*f;
}void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(){
	int a=read(),b=read();
	if(a<10&&b<10)cout<<a*b;
	else cout<<-1;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MOD = 1e9+7;
const int maxn = 2e5+5;
typedef long long ll;
int prime[maxn];
int p[maxn];
int v[maxn];
int c[maxn];
void primes(int n){
	memset(v,0,sizeof(v));
	int m = 0;
	for(int i = 2;i<=n;i++){
		if(v[i]==0){
			v[i] = i;
			prime[++m] = i;  //存储素数的数组
		}
		for(int j = 1;j<=m;j++){
			if(prime[j]>v[i]||prime[j]>(n/i)) break;
			v[i*prime[j]] = prime[j];  //对于每个数的标记
		}
	}
}
int divide(ll n){
    int m = 0;
    int sum = 0;
    ll nn = n;
    for(int i = 1;prime[i]<=sqrt(n);i++){  //注意这里的n其实是一直在变化的，但是因为传了参数n，所以不影响主函数中的n
        if(n%prime[i]==0){
            //i是质数
            p[++m] = prime[i];
            c[m] = 0;
            while(n%prime[i]==0){
                n/=prime[i];
                c[m]++;
            }
        } 
    }
    sum = 1;
    if(n>1) p[++m] = n,c[m] = 1;  //一定要写，不然的话最后一个质因子不能被放到数组里（6=2*3）
    for(int i = 1;i<=m;i++){
    	//printf("%d\n",prime[i]);
        sum = sum*(c[i]+1);  //sum是因子的个数
    }
    return m;
}
int F[maxn], Finv[maxn], inv[maxn];//F是阶乘，Finv是逆元的阶乘 
void init(){
    inv[1] = 1;
    for(int i = 2; i < maxn; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < maxn; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){//comb(n, m)就是C(n, m) 
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}
int main(){
	int n,m;
	primes(maxn-3);
	init();
	scanf("%d%d",&n,&m);
	int mm = divide(m);
	long long ans = 1; 
	//printf("%d\n",mm);
	for(int i = 1;i<=mm;i++){
		m = c[i];
		//cout<<m<<endl;
		//printf("%d\n",comb(m+n-1,n-1));
		ans=ans*comb(m+n-1,n-1)%MOD;
		//cout<<ans<<endl;
	}
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 4352
#include <stdio.h>

int main(void)
{
	char c1, c2;
	char ball;
	
	ball = 'A';
	while (scanf("%c,%c", &c1, &c2) != EOF){
		if (c1 == ball){
			ball = c2;
		}
		else if (c2 == ball){
			ball = c1;
		}
	}
	
	printf("%c\n", ball);
	
	return (0);
}

Measured memory_bytes: 544
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		int M = scn.nextInt();
		int[] A = new int[M+1];
		long[] fib = new long[N + 1];
		final long MOD = 1000000007;
		long ans = 1;
		boolean can = true;
		for (int i = 0; i < M; i++) {
			A[i] = scn.nextInt();
			if (i != 0 && A[i] - A[i - 1] == 1)
				can = false;
		}
		A[M] = N+1;
		if (can) {
			fib[1] = 1;
			fib[0] = 1;
			for (int i = 2; i <= N; i++) {
				fib[i] = fib[i - 1] + fib[i - 2];
				fib[i] %= MOD;
			}
			int b = 0;

			for (int i = 0; i < M+1; i++) {
				int a = A[i];
				ans *= fib[a - b-1];
				ans %= MOD;
				b = a+1;
			}
		} else {
			ans = 0;
		}
		System.out.println(ans);
	}

}


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

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

		process: {
			int num = sc.nextInt();
			String[] input = new String[num];
			for (int j = 0; j < num; j++) {
				input[j] = sc.next();
			}
			for (int k = 0; k < num; k++) {
				if (input[k].equals("0")) {
					System.out.println(0);
					break process;
				}
			}
			for (int k = 0; k < num; k++) {
				if (input[k].length() >= 18) {
					System.out.println(-1);
					break process;
				}

			}
			BigInteger[] bigArray = new BigInteger[num];
			for (int i = 0; i < num; i++) {
				bigArray[i] = new BigInteger(input[i]);
			}
			BigInteger ans = new BigInteger(input[0]);
			for (int i = 1; i < num; i++) {
				ans = ans.multiply(bigArray[i]);
			}

			if (ans.compareTo(new BigInteger("1000000000000000000")) == 1) {
				System.out.println(-1);
			} else {
				System.out.println(ans);
			}
			sc.close();
		}
	}// main
}
// class


Measured memory_bytes: 70696
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
using ll = long long;

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

int main() {
  int n;
  ll k;
  cin >> n >> k;
  int a[n];
  rep(i, n) {
    cin >> a[i];
    --a[i];
  }

  vector<int> d;
  set<int> v;
  d.push_back(0);
  v.insert(0);
  int loop = 0;
  for (int i = 0; i < n - 1; ++i) {
    int nx = a[d[i]];
    if (v.find(nx) != v.end()) {
      loop = d.size() - distance(d.begin(), find(d.begin(), d.end(), nx));
      break;
    }
    d.push_back(nx);
    v.insert(nx);
  }

  int noLoop = d.size() - loop;
  if (k <= noLoop) {
    int ans = d[k];
    cout << ++ans << '\n';
    return 0;
  }
  int ans = d[noLoop + (k - noLoop) % loop];
  cout << ++ans << '\n';

  return 0;
}


Measured memory_bytes: 14016
// C - Pyramid
#include <bits/stdc++.h>
using namespace std;
using TP = tuple<int,int,int>;//<x,y,h>
using VT = vector<TP>;//[i]<x,y,h>
#define rp(i,n) for(int i=0;i<(n);i++)
#define eb(x,y,h) emplace_back((x),(y),(h))
#define manhattan(x1,y1,x2,y2) abs((x1)-(x2))+abs((y1)-(y2))
#define XMAX 100
#define YMAX 100

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

	VT A;//h!=0
	VT B;//h==0
	VT C;//center candidate

	rp(i, N){
		int x,y,h; cin>>x>>y>>h;
		if(h!=0) A.eb(x,y,h);
		else B.eb(x,y,h);
	}

	rp(y0, YMAX+1){
		rp(x0, XMAX+1){
			bool exist = true;
			int x,y,h;
			tie(x,y,h) = A[0];
			int h0 = h + manhattan(x0,y0, x,y);//h0: hight of center candidate

			for(int i=1; i<A.size(); ++i){
				tie(x,y,h) = A[i];
				if(h0 != h + manhattan(x0,y0, x,y)){
					exist = false;
					break;
				}
			}

			if(exist) C.eb(x0,y0,h0);//set center candidate
		}
	}

	for(auto c:C){// hight zero check & output
		int x0,y0,h0; tie(x0,y0,h0) = c;

		bool exist = true;
		for(auto b:B){
			int x,y,h; tie(x,y,h) = b;

			int m = manhattan(x0,y0, x,y);
			int hi = max(0, h0 - m);
			if(hi != h){
				exist = false;
				break;
			}

		}

		if(exist) cout<<x0<<" "<<y0<<" "<<h0<<"\n";
	}

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
using namespace std;
int main(){
    int n,m;
    map<int,int>d,t;
    cin>>n;
    REP(i,n){
        int a;
        cin>>a;d[a]++;
    }
    cin>>m;
    bool f=true;
    REP(i,m){
        int a;
        cin>>a;
        if(d[a]>0){
            d[a]--;
        }else{
            f=false;
        }
    }
    if(f){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int k = s.length();
    int cnt = 0;
    
    rep(i, k) {
        if (s[i] == 'o') {
            cnt++;
        }
    }
    
    cout << (((cnt + (15 - k)) >= 8) ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Here your code !

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

for i in range(len(a) - 1):
    for j in range(len(a) - 1, i, -1):
        if a[j] < a[j - 1]:
            t = a[j]
            a[j] = a[j - 1]
            a[j - 1] = t
        

for i in range(len(a)):
    if i == len(a) - 1:
        print(a[i])
    else:
        print(str(a[i]) + " ", end = "")

Measured memory_bytes: 7644
def resolve():
  a = int(input())
  b = int(input())
  c = int(input())
  x = int(input())
  ans = 0
  for i in range(a+1):
    for j in range(b+1):
      for k in range(c+1):
        if 500 * i + 100 * j + 50 * k == x:
          ans += 1
  print(ans)
  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 9052
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    vector<long long int>v;
    for(int i=0;i<n;i++)
    {
        long int x;
        cin>>x;
        v.push_back(x);
    }
    vector<long long int>v1;
    long long int a=v[0];
    for(int i=0;i<v.size();i++)
    {
        if(a>v[i])
        {
            long long int b=a-v[i];
            v1.push_back(b);
        }
        else
        {
            a=v[i];
            v1.push_back(0);
        }
    }
    long long int sum=0;
    for(int i=0;i<v1.size();i++)
    {
        sum+=v1[i];
    }
    cout<<sum<<endl;
} 

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

int main() {
	int W, H, x, y, r;
	cin >> W >> H >> x >> y >> r;
	if (x >= -100 && x <= 100 && y >= -100 && y <= 100 && W > 0 && W <= 100 && H > 0 && H <= 100 && r > 0 && r <= 100) {
		if (x > W || y > H) {
			cout << "No" << endl;
		}
		else {
			if (x - r < 0 || x + r > W) {
				cout << "No" << endl;
			}
			else if (y - r < 0 || y + r > H) {
				cout << "No" << endl;
			}
			else {
				cout << "Yes" << endl;
			}
		}
	}
}


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

int main() {
  ll n,m,sum=0;
  ll H[100000];
  set<ll> v[100000];
  cin>>n>>m;

  rep(i,n){
    scanf("%lld",&H[i]);
  }
  ll a,b;
  rep(i,m){
    scanf("%lld %lld", &a,&b);
    if(v[a-1].find(b-1)==v[a-1].end()){
      v[a-1].insert(b-1);
      v[b-1].insert(a-1);
    }
  }
  rep(i,n){
    int c=1;
    for(auto it=v[i].begin();it!=v[i].end();it++){
      if(H[i]<=H[*it]){
        c=0;
        break;
      }
    }
    sum+=c;
  }

  cout<<sum<<endl;
}


Measured memory_bytes: 18468
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define ALL(x) (x).begin(),(x).end()
#define C(x) cout << #x << " : " << x << endl
#define scanf scanf_s

using int32 = int_fast32_t;
using int64 = int_fast64_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;

using namespace std;

template<typename Monoid>
class SegTree {
public:
	Monoid* tree;
	size_t size;
	int32 i;
	//?????????????????????
	SegTree(size_t length) {
		--length;
		size = length & 0xffff0000 ? length & 0xffff0000 : length;
		size = size & 0xff00ff00 ? size & 0xff00ff00 : size;
		size = size & 0xf0f0f0f0 ? size & 0xf0f0f0f0 : size;
		size = size & 0xcccccccc ? size & 0xcccccccc : size;
		size = size & 0xaaaaaaaa ? size & 0xaaaaaaaa : size;
		size = length ? size << 1 : 1;
		++length;
		tree = (Monoid *)calloc(size << 1, sizeof(Monoid));
	}
	//?????????
	void set() {
		size <<= 1;
		for (i = 0;i < size;++i) tree[i].set();
		size >>= 1;
	}
	//tree[index]???data?????´??°
	void update(size_t index, Monoid &data) {
		index += size;
		tree[index] = data;
		while (index >>= 1) tree[index] = tree[index << 1] + tree[index * 2 + 1];
	}
	//[begin,end)??????????????????
	Monoid range(size_t begin, size_t end) {
		Monoid retL, retR;
		for (begin += size, end += size;begin < end;begin >>= 1, end >>= 1) {
			if (begin & 1) retL = retL + tree[begin++];
			if (end & 1)  retR = tree[--end] + retR;
		}
		return retL + retR;
	}
};

struct MIN {
	int32 e;
	MIN() { set(); }
	MIN(int32 x) { e = x; }
	void set() { e = 2147483647; }
	void update(MIN b) { e = b.e; }
	MIN operator+(MIN &other) {
		return e < other.e ? MIN(e) : MIN(other.e);
	};
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	//*
	int32 n, q;
	cin >> n >> q;
	int32 c, x,y1;
	MIN y2;
	SegTree<MIN> t(n);
	t.set();
	rep(i, 0, q) {
		cin >> c;
		if (c) {
			cin >> x >> y1;
			printf("%d\n", t.range(x, y1 + 1).e);
		}
		else {
			cin >> x >> y2.e;
			t.update(x, y2);
		}
	}
	//*/
	return 0;
}

Measured memory_bytes: 5236
// Aizu Vol-15 1500: ID
// 2017.9.4 bal4u@uu

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

#define N       1000000000
#define MAXINT  50

void mpNum2Str(char *str, int *num)
{
    int  i, j;
    char *ss;
    int  x;

    if (*num == 0 || (*num == 1 && *(num+1) == 0)) {
        *str++ = '0';
        *str = '\0';
        return;
    }

    ss = str - 1;
    for (i = *num; i > 0; i--) {
        x = *++num;
        for (j = 1; j < N; j *= 10) {
            *++ss = x % 10 + '0';
            x /= 10;
        }
    }
    while (*ss == '0') ss--;

    *(ss + 1) = '\0';    
    while (str < ss) {
        x = *str;
        *str++ = *ss;
        *ss-- = x;
    }
}

void mpAdd(int *ret, int *a, int *b)
{
    int  i;
    int  lr, la, lb;
    int  *rr;
    int  x;

    la = *a;
    lb = *b;
    lr = (la >= lb) ? la : lb;

    rr = ret;
    x = 0;
    for (i = 1; i <= lr; i++) {
        if (i <= la) x += *++a;
        if (i <= lb) x += *++b;
        if (x < N) {
            *++rr = x;
            x = 0;
        } else {
            *++rr = x - N;
            x = 1;
        }
    }
    *++rr = x;
    *ret = lr + x;
}

void mpCpy(int *des, int *src)
{
    memcpy(des, src, (1+*src)*sizeof(int));
}

char id[100003];
char a[10];
int t[10] = { 0,2,4,6,8,1,3,5,7,9 };

int p[2][10][MAXINT], tmp[MAXINT];
char buf[510];

int main()
{
	int n, m, i, j, d, x, k, k1, k2, even;

	scanf("%d%s%d", &n, id+1, &m);
	for (i = 0; i < m; i++) scanf("%d", &d), a[d] = 1;
	p[0][0][0] = p[0][0][1] = 1, even = !(n & 1);
	for (k1 = 0, k2 = 1, i = 1; i <= n; i++, k1 = k2, k2 = !k2, even = !even) {
		for (j = 0; j < 10; j++) p[k2][j][0] = 0;
		if (id[i] == '*') {
			for (k = 0; k < 10; k++) {
				if (!a[k]) continue;
				d = even ? t[k] : k;
				for (j = 0; j < 10; j++) {
					if ((x = d + j) >= 10) x -= 10;
					mpAdd(tmp, p[k2][x], p[k1][j]);
					mpCpy(p[k2][x], tmp);
				}
			}
		} else {
			k = id[i] - '0';
			d = even ? t[k] : k;
			for (j = 0; j < 10; j++) {
				if ((x = d + j) >= 10) x -= 10;
				mpAdd(tmp, p[k2][x], p[k1][j]);
				mpCpy(p[k2][x], tmp);
			}
		}
	}
	mpNum2Str(buf, p[k1][0]);
	puts(buf);
	return 0;
}

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

int main() {
  int N, l, r, sum;
  cin>> N;
  sum = 0;
  for (int i = 0; i < N; i++) {
  cin >> l >> r;
    sum= r - l + 1 + sum;
  }
  cout<<sum;


}


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

int main(){
    string S,T;
    cin >> S >> T;
    bool flag=0;
    if(S==T){
        flag=1;
    }
    char c;
    for(int i=0;i<S.size();i++){
        c=S[0];
        for(int j=0;j<S.size()-1;j++){
            S[j]=S[j+1];
        }
        S[S.size()-1]=c;
        if(S==T){
            flag=1;
        }
    }
    if(flag)
    cout << "Yes" << endl;
    else
    cout << "No" << endl;
}

Measured memory_bytes: 256
A= [list(map(int,input().split())) for _ in range(3)]
N=int(input())
b=[0]*N
for i in range(N):
  b[i]=int(input())
  
flag=False

#よこちぇっく
for i in range(3):  
  if A[i][0] in b:
    if A[i][1] in b:
      if A[i][2] in b:
        flag=True
#たてちぇっく
for j in range(3):  
  if A[0][j] in b:
    if A[1][j] in b:
      if A[2][j] in b:
        flag=True      
#ななめちぇっく1
if A[0][0] in b:
  if A[1][1] in b:
    if A[2][2] in b:
      flag=True
#ななめちぇっく2
if A[0][2] in b:
  if A[1][1] in b:
    if A[2][0] in b:
      flag=True      

if flag:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
 
 
int main(){

    string S,T;
    cin >> S >> T;
    long long int ans = 0;
    for(long long int i = 0; i < S.size(); i++){
        if(S.at(i) != T.at(i)){
            ans ++;
        }
    }
    cout << ans << endl;

}


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

using namespace std;

typedef long long ll;

const double pi = 3.14159265358979323846;

#define rep(i, n) for (ll i = 0; i < n; i++)
#define mod 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()

int main() {
  int A, B;
  cin >> A >> B;
  if ((B % A) == 0) {
    cout << A + B << endl;
  } else {
    cout << B - A << endl;
  }

  return 0;
}


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

long read_long() {
	long ret=0;char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') {
		ret=ret*10+c-'0';
		c=getchar();
	}	return ret;
}

const long MAXN=200100;
long prefix[MAXN],ans;
long n,k;

int main() {
	n=read_long();k=read_long();
	register long i;
	long p;
	for(i=1;i<=n;++i) {
		p=read_long();
		prefix[i]=prefix[i-1]+p;
	}
	
	for(i=k;i<=n;++i)
		ans=max(ans,prefix[i]-prefix[i-k]);
	printf("%lf",(ans+k)*0.5);
//	cout<<(long double)(ans+k)/2<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int N;
    long A[100000];
    long B[100000];
    long diff[100000];
    long sum_diff;
    long sumA = 0;
    long sumB = 0;
    int cnt = 0;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        sumA+=A[i];
    }
  
    for(int i = 0; i < N; i++){
        cin >> B[i];
        sumB+=B[i];
        diff[i] = A[i] - B[i];
        if(diff[i] < 0){
            sum_diff += diff[i];
            cnt++;
        }
    }
    if(sumA < sumB){
        cout << -1 << endl;
        return 0;
    }
    sort(diff, diff+N, greater<int>());
    int i = 0;
    while(sum_diff < 0){
        sum_diff+=diff[i];
        i++;
    }
    cout << i+cnt << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second
main(){
	int n;
	cin>>n;
	vector<int>a(n),b;
	r(i,n)cin>>a[i];
	sort(a.begin(),a.end());
	if(n%2==0){
      r(i,(n+1)/2){
		b.push_back((i)*2+1);
	    b.push_back((i)*2+1);
	  }
	}
	else r(i,(n+1)/2){
		b.push_back(i*2);
	    if(i)b.push_back(i*2);
	}
	sort(b.begin(),b.end());
	if(a!=b){
		cout<<0<<endl;
		return 0;
	}
	int ans=1;
	for(int i=0;i<n/2;i++){
		ans*=2;
		ans=ans%1000000007;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 2168
def main():
    N = int(input())
    any = 0
    A = map(int, input().split())
    colors = set([])
    for a in A:
        if 1 <= a <= 399:
            colors.add('gray')
        elif 400 <= a <= 799:
            colors.add('brown')
        elif 800 <= a <= 1199:
            colors.add('green')
        elif 1200 <= a <= 1599:
            colors.add('light blue')
        elif 1600 <= a <= 1999:
            colors.add('blue')
        elif 2000 <= a <= 2399:
            colors.add('yellow')
        elif 2400 <= a <= 2799:
            colors.add('orange')
        elif 2800 <= a <= 3199:
            colors.add('red')
        else:
            any += 1

    if any == 0:
        print(len(colors), len(colors))
    elif len(colors) == 0:
        print(1, any)
    else:
        print(len(colors), len(colors) + any)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61984
"use strict";

function main(input){
  const n = input.trim().split(' ');
  const a = n[0] == "H";
  const b = n[1] == "H";
  if(a ===b)
  	console.log("H");
  else
    console.log("D");
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

Measured memory_bytes: 7372
n,m=map(int,input().split())
l=[1 for i in range(n+1)]
for i in range(m):
    s=int(input())
    l[s]=0
if n!=1:
    for i in range(2,n+1):
        if l[i]!=0:
            a=max(1,l[i-2]) if l[i-2]!=0 else 0
            b=max(1,l[i-1]) if l[i-1]!=0 else 0
            l[i]=a+b
print(l[n]%(10**9+7))

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

struct activity{
    int A, B, C;
};

int main() {
    int n; cin>>n;
    activity arr[n];
    for(int i=0; i<n; i++) {
        cin>>arr[i].A;
        cin>>arr[i].B;
        cin>>arr[i].C;
    }

    int dp[n][3];
    dp[0][0] = arr[0].A;
    dp[0][1] = arr[0].B;
    dp[0][2] = arr[0].C;

    for(int i=1; i<n; i++) {
        dp[i][0] = arr[i].A + max(dp[i-1][1] , dp[i-1][2]);
        dp[i][1] = arr[i].B + max(dp[i-1][0] , dp[i-1][2]);
        dp[i][2] = arr[i].C + max(dp[i-1][0] , dp[i-1][1]);
    }

    cout<<max( dp[n-1][0] , max(dp[n-1][1] , dp[n-1][2] ))<<endl;
    return 0;
}


Measured memory_bytes: 5944
def abc054_c_one_stroke_paths():
    N, M = map(int, input().split())

    # create graph G
    G = {}
    for m in range(M):
        a, z = map(int, input().split())
        G[a] = G.get(a, [])
        G[a].append(z)
        G[z] = G.get(z, [])
        G[z].append(a)

    # print(G)

    # find all paths
    if G.get(1, 0) == 0:
        print(0)
        return

    def dfs(a, path):
        path.append(a)
        if len(path) == N:
            return 1

        paths = 0
        for z in G.get(a):
            if z in path:
                continue
            paths += dfs(z, path[:])

        return paths

    print(dfs(1, []))


##########
if __name__ == "__main__":
    abc054_c_one_stroke_paths()


Measured memory_bytes: 3064