akhauriyash/Code-Regression huggingface dataset:
use proconio::{input, marker::Chars};
use std::collections::VecDeque;

fn main() {
    input! {
        _n: usize,
        s: Chars,
    }
    let mut count_l = 0;
    let mut ans = VecDeque::new();

    for c in s {
        match c {
            '(' => {
                ans.push_back('(');
                count_l += 1;
            },
            ')' => {
                if count_l > 0 {
                    count_l -= 1;
                } else {
                    ans.push_front('(');
                }
                ans.push_back(')');
            },
            _ => {},
        }
    }
    for _ in 0..count_l {
        ans.push_back(')');
    }

    let ans = ans.iter().collect::<String>();

    println!("{}", ans);
}


Measured memory_bytes: 2152
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e4 + 10;
int a[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s;
	cin >> s;
	for (int i = 0; i + 1 < s.length(); i++)
	{
		if (s[i] == s[i + 1])
		{
			printf("%d %d\n", i + 1, i + 2);
			return 0;
		}
	}
	for (int i = 0; i + 2 < s.length(); i++)
	{
		if (s[i] == s[i + 2])
		{
			printf("%d %d\n", i + 1, i + 3);
			return 0;
		}
	}
	puts("-1 -1");
	return 0;
}

Measured memory_bytes: 512
n=int(input())
p = []
for _ in range(n):
  x,y=map(int,input().split())
  p.append((x,y))

import itertools
perm = list(itertools.permutations(range(n)))
d = 0
for v in perm:
  lx,ly = p[v[0]]
  for v2 in v[1:]:
    x,y=p[v2]
    d += ((x-lx)**2+(y-ly)**2)**0.5
print(d/len(perm))
    

Measured memory_bytes: 13996
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::{min,max};

fn main() {
    input!{
        a: usize,
        b: usize,
        k: usize
    }
    let g = gcd(a, b);
    let mut c = 0;
    for i in (1..g + 1).rev() {
        if a % i == 0 && b % i == 0 {
            c += 1;
            if c == k {
                println!("{}", i);
                return;
            }
        }
    }
}


fn gcd(n: usize, m: usize) -> usize {
    let mut l = min(n, m);
    let mut r = max(n, m);
    while l > 0 {
        let t = l;
        l = r % l;
        r = t;
    }
    r
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int P = 5040;
int dp[110][P]={};

int fact[8];

inline vector<int> decode(int x)
{
    vector<int> ret(7);
    vector<bool> use(7,false);
    rep(i,7)
    {
        int num = x/fact[6-i];
        x -= fact[6-i]*num;

        int y = 0,ct = 0;
        while(y<7)
        {
            if(!use[y]) ++ct;

            if(ct==num+1) break;
            ++y;
        }
        use[y]=true;
        ret[i]=y;
    }
    return ret;
}

inline int encode(const vector<int> &p)
{
    int ret = 0;
    vector<bool> use(7,false);
    rep(i,7)
    {
        int ct = 0;
        for(int j=0; j<p[i]; ++j) ct += !use[j];
        ret += ct*fact[6-i];
        use[p[i]]=true;
    }

    return ret;
}

inline vector<int> normalize(const vector<int> &p)
{
    vector<int> t(p);
    sort(all(t));

    int ct=0;
    int id[10];
    for(const auto &v:t) id[v]=ct++;

    vector<int> ret(7);
    rep(i,7) ret[i]=id[p[i]];

    return ret;
}

int main()
{
    fact[0]=1;
    for(int i=1; i<8; ++i) fact[i] = fact[i-1]*i;

    int n;
    cin >>n;
    vector<int> d(n+7),a(n+7);
    rep(i,n) cin >>d[i+7];
    rep(i,n) cin >>a[i+7];

    n += 7;
    for(int i=7; i<n; ++i)rep(j,P)
    {
        vector<int> p = decode(j);

        // i??????????????????????£??????????
        rep(k,8)
        {
            vector<int> nx(all(p));
            for(auto &v:nx)if(v>=k) ++v;
            nx.pb(k);

            int NX = nx.size();
            int add = 0;
            for(int l=1; l<NX; ++l)
            {
                if(nx[NX-1]>nx[NX-1-l])
                {
                    // i???????????????????£??????????
                    if(d[i-l]>=l) add+=a[i-l];
                }
                else
                {
                    // i???????????????????£??????????
                    if(d[i]>=l && i-l>=7) add+=a[i];
                }
            }

            nx.erase(nx.begin());
            nx = normalize(nx);
            int idx = encode(nx);
            dp[i+1][idx] = max(dp[i+1][idx], dp[i][j]+add);
        }
    }

    cout << *max_element(dp[n],dp[n]+P) << endl;
    return 0;
}

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

int main() {
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;

	int tl = 0;

	for (int i = 1; i <= N; i++) {
		if (i < K + 1) tl += X;
		else tl += Y;
	}

	cout << tl << endl;

	return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>

using namespace std;

int main()
{
    int n, k; cin >> n >> k;

    int ans = 1;
    n -= k;

    ans += n / (k-1);
    n = n % (k-1);
    if (n)
        ans++;

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

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

int main()
{
    int num, current;
    cin >> num;
    vector<int> v;
    for(int i=0;i<num;i++){
        cin >> current;
        v.push_back(current);
    }
    current = v[0];
    bool judge = true;
    for(int i=1;i<num;i++){
        if(v[i]>current){
            current = v[i]-1;
        }else if(v[i]==current){
            current = v[i];
        }else{
            judge = false;
            break;
        }
    }
    if(judge){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    return 0;
}

Measured memory_bytes: 892
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define ln '\n'
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<MOD>;

mint modpow(mint a, int x) {
    mint ret = 1;
    while (x > 0) {
        if (x&1) ret *= a;
        x >>= 1;
        a *= a;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,K; cin >> N >> K;

    vector<mint> cnt(K+1);

    for (int i = 1; i <= K; i++) {
        int a = K/i;
        //cout << a << ln;
        mint z = a;
        cnt[i] = modpow(z,N);
        //cout << cnt[i].a << ln;
    }
    mint ans = 0;
    for (int i = K; i >= 1; i--) {
        //cout << cnt[i].a << ln;
        ans += cnt[i]*i;
        for (int j = 1; j*j <= i; j++) {
            if (i%j==0) {
                //cout << i << " " << j << ln;
                //cout << cnt[j].a << ln;
                cnt[j] -= cnt[i];
                if (j != 1 and j*j != i) {
                    //cout << i/j << ln;
                    cnt[i/j] -= cnt[i];
                }
            }
        }
    }

    cout << ans.a << ln;
}


Measured memory_bytes: 3992
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
typedef long long ll;

void Main()
{
	int n;
  	cin >> n;
  	vector<int> even(1e5), odd(1e5);
  	rep(i,n){
      	int v;
    	cin >> v;
      	if(i%2==0) even[v]++;
      	else odd[v]++;
    }
  	vector<pair<int, int>> e(1e5), o(1e5);
  	rep(i,1e5) {
      	e[i] = make_pair(even[i], i);
  		o[i] = make_pair(odd[i], i);
    }
  	sort(e.rbegin(), e.rend());
  	sort(o.rbegin(), o.rend());
  	/*
    rep(i,5) {
      	cout << e[i].first << ": " << e[i].second << ", "; 
      	cout << o[i].first << ": " << o[i].second;
  		cout << endl;
    }
  	*/
  	if(e[0].second != o[0].second) cout << n - e[0].first - o[0].first << endl;
  	else {
      	int temp = max(e[0].first+o[1].first, o[0].first+e[1].first);
      	cout << n - temp << endl;
    }
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define DEBUG
#define PI 3.141592653589793238462643383279
 
#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define REP1(i, n) for(ll i = 1; i <= n; i++)
#define REPR1(i, n) for(ll i = n; i >= 1; i--)
#define FOR1(i, m, n) for(ll i = m; i <= n; i++)
const ll INF = LLONG_MAX;
#define VEC(type,A,N) vector<type> A(N)
#define VECi(type,A,N,i) vector<type> A(N,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N,vector<type>(M))
#define VEC2i(type,A,N,M,i) vector<vector<type>> A(N,vector<type>(M,i))
#define ALL(v) v.begin(), v.end()
ll frac(ll k){
    int s = 1;
    for (ll i=1; i<=k; ++i)s *= i;
    return s;
}
ll gcd(ll a, ll b){
   if (a%b==0)return(b);
   else return(gcd(b, a%b));
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
ll antidiv(ll N,ll C,ll D){
    return N-floor(N/C)-floor(N/D)+floor(N/lcm(C,D));
}
vector<ll> yakusuu(ll N){
    vector<ll> ret;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ret.push_back(i);
            if (i * i != N) ret.push_back(N / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main(){
    ll N,M,F;
    cin>>N>>M>>F;
    //ll t=N*M;
    //cout<<fixed<<setprecision(20)<<N*M<<endl;
    //cout<<fixed<<setprecision(0)<<floor(t);
    N-=F;
    cout<<N/(M+F);
    //cout<<fixed<<setprecision(32)<<m;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

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

    ll N, A, B;
    cin >> N >> A >> B;
    ll ans = 0;
    ans += N / (A + B) * A;
    N %= A + B;
    ans += min(A, N);
    cout << ans << endl;
}

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

typedef unsigned long long ULL;
typedef long long LL;

using namespace std;

template<class T> void swap(T *a, T *b ){
    T temp;
    temp = *a;
    *a = *b;
    *b = temp;   
}
LL check(LL a, LL b);
int main(){
    int first,last;
    LL N,K;
    int *A;
    int *count;
    int *def_count;
    int i,j;
    LL ans;
    LL temp;
    cin >> N >> K;
    A = new int[N];
    count = new int[N];
    def_count = new int[N];
    for(i=0;i<N;i++){
        cin >> A[i];
        count[i] = 0;
        def_count[i] = 0;
    }
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            if( A[i] > A[j] ){
                if( i < j ){
                    def_count[j]++;
                }
                count[j]++;
            }
        }
    }
    ans = 0;
    for(i=0;i<N;i++){
        //temp = def_count[i];
        temp = check(( def_count[i] + def_count[i] + count[i] * (K-1)), K );
        ans += temp;
        ans = ans % 1000000007;
    }
    cout << ans << endl;
    return 0;
}
LL check(LL a, LL b){
    if( a % 2 == 0 ){
        a /= 2;
    }else if( b % 2 == 0 ){
        b /= 2;
    }
    a = a % 1000000007;
    b = b % 1000000007;
    return ( a * b ) %  1000000007;
}

Measured memory_bytes: 256
N,X = map(int,input().split())
bg_cnt = [1]
pan_cnt = [1]
for i in range(N):
    bg_cnt.append(bg_cnt[i] * 2 + 3)
    pan_cnt.append(pan_cnt[i] * 2 + 1)

def f(N,X):
    if N == 0:
        return 1
    elif X == 1:
        return 0
    elif X <= 1 + bg_cnt[N-1]:
        return f(N-1,X-1)
    elif X == 2 + bg_cnt[N-1]:
        return 1 + f(N-1,X-1)
    else:
        return pan_cnt[N-1] + 1 + f(N-1,X-2-bg_cnt[N-1])    
print(f(N,X))

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


ll combination(ll n, ll r){
    if(n < r) return 0;
    if(r == 0||r == n) return 1;
    else if(r == 1) return n;
    return (combination(n - 1, r - 1) + combination(n - 1, r));
}

bool checkKaibun(string str){
    string checkStr = str;
    reverse(checkStr.begin(), checkStr.end());
    if(str == checkStr) return true;
    else return false;
}


int main(){
    ll N;
    cin >> N;
    //まず一つも抜いていない状態での組み合わせ算出
    vector<ll> countNum(N,0);
    vector<ll> array(N);
    for(int i = 0; i < N; i++){
        int num;
        cin >> num;
        countNum.at(num - 1)++;
        array.at(i) = num - 1;
    }

    ll totalNum = 0;
    for(int i = 0; i < N; i++){
        totalNum += countNum.at(i) * (countNum.at(i) - 1) / 2;
    }
    

    for(int i = 0; i < N; i++){
        ll copy = totalNum;
        if(countNum.at(array.at(i)) > 1){
            copy -= countNum.at(array.at(i)) * (countNum.at(array.at(i)) - 1) / 2;
            copy += (countNum.at(array[i]) - 1) * (countNum.at(array.at(i)) - 2) / 2;
        }
        cout << copy << endl;
        
    }
}



Measured memory_bytes: 5760
from collections import defaultdict
from heapq import heappush, heappop

n = int(input())
red = [list(map(int, input().split())) for i in range(n)]
blue = [list(map(int, input().split())) for i in range(n)]
blue.sort()
# print(blue)

red_flag = [0] * n
ans = 0
for i in range(n):
    idx = -1
    for j in range(n):
        if red[j][0] >= blue[i][0] or red[j][1] >= blue[i][1] or red_flag[j] == 1:
            continue
        if idx == -1 or red[idx][1] < red[j][1]:
            idx = j

    if idx >= 0:
        red_flag[idx] = 1
        ans += 1

print(ans)


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

using namespace std;
int a,b,c,x,y;
int main() {
  cin >> a >> b >> c >> x >> y;
  if(x < y) {
    swap(a,b);
    swap(x,y);
  }
  
  int ans = 0;
  if(a + b >= 2 * c) {
    ans += 2 * c * y;
    if(a >= 2 * c) {
      ans += 2 * c * (x - y);
    }
    else ans += a * (x - y);
    
    cout << ans << endl;
  }
  else {
    cout << x * a + y * b << endl;
  }
    
}


Measured memory_bytes: 256
"""
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
セグメント木について
高速で区間クエリを実施する方法
(基本的な最小化問題のセグ木)
区間[a,b)にある要素の最小値を答えることを考える
※ 半開区間であることに注意しよう

要求区間 : クエリの範囲
対象区間 : 各ノードがカバーしている区間

1. 要求区間と対象区間が交わらない場合
    操作を進めても無意味なので、影響のない適当な値を返す
2. 要求区間が対象区間を完全に被覆している
    対象区間は要求区間の計算に必要なので、現状の答えと比較・更新する
3. 要求区間が対象区間の一部を被覆している場合
    対象区間の子に当たる区間に移動して、完全に被覆するまで操作を行う

最上段から下がっていきながらが、値を取得する
"""

class SegmentTree:
    def __init__(self,v):
        """
        :param v:元配列
        """
        size = len(v)
        self.n = 1
        while self.n < size:
            self.n *= 2
        # 木全体で必要なノード数は2n-1
        self.node = [0] * (2*self.n-1)
        # 最下段に値を代入
        for i, e in enumerate(v):
            self.node[i+self.n-1] = e
        # 上段は、下の段を利用する
        for i in range(self.n-2,-1,-1):
            self.node[i] = min(self.node[2*i+1], self.node[2*i+2])

    def update(self, x, val):
        """
        :param x: インデックス
        :param val: 更新する値
        """
        # 最下段にアクセス
        x += (self.n-1)
        # 上に登りながら更新していく
        self.node[x] = val
        while(x > 0):
            x = (x-1) // 2
            self.node[x] = min(self.node[2*x+1],self.node[2*x+2])
    
    def getmin(self, a, b, k=0, l=0, r=-1):
        """
        :param a: 要求区間の左 [
        :param b: 要求区間の右 )
        :param k: 現在のインデックス
        :param l: 対象区間の左
        :param r: 対象区間の右
        """
        INF = 2**31-1
        # 最初に呼び出されたとき、対象区間は[0,n)
        if (r < 0): r = self.n        
        # print("check",a,l,r,b)
        
        # 要求区間と対象区間が交わらない -> 適当に返す
        if (r<=a or b<=l): 
            return INF

        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
        if (a <= l and r <= b): 
            return self.node[k]

        # 要求区間が対象区間の一部を被覆 -> 子を探索
        # 左側をv1, 右側をv2
        vl = self.getmin(a, b, 2*k+1, l, (l+r)//2)
        vr = self.getmin(a, b, 2*k+2, (l+r)//2, r)
        return min(vl, vr)

if __name__ == '__main__':
    """
    テストケース含問題
    """
    n,q  = map(int, input().split())
    v = [2**31-1] * n
    st = SegmentTree(v)
    A = []
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:   
            st.update(x,y)
        else:
            ans = st.getmin(x,y+1)
            print(ans)



Measured memory_bytes: 9492
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod = 1000000007;
const int INF = 1e18;
int ans[1000005];
int a[200005], b[200005];

set <pair <int, int> > se;
int32_t main() {

	ios_base::sync_with_stdio(false);	cin.tie(NULL);

	int n, m, pos = 0;
	cin >> n >> m;

	ans[m + 1]++;

	f(i, 1, m + 1) {
		se.insert({i, 0});
		ans[0]++;
	}

	f(i, 1, n + 1) {
		cin >> a[i] >> b[i];

		if (pos > m) {
			cout << "-1\n";
			continue;
		}
		if (b[i] != m) {
			auto itr = se.lower_bound({b[i] + 2, 0});

			if (itr != se.begin()) {
				itr--;
				if ((*itr).ff != b[i] + 1) {
					int value = b[i] + 1 - (*itr).ff + (*itr).ss;
					se.insert({b[i] + 1, value});
					ans[value]++;
				}
			}
		}

		auto itr = se.lower_bound({a[i], 0});
		while (itr != se.end() && (*itr).ff <= b[i] ) {
			auto itrtmp = itr;
			itr++;
			ans[itrtmp->ss]--;
			se.erase(itrtmp);
		}

		while (ans[pos] <= 0) {
			pos++;
		}

		if (pos > m)
			cout << "-1\n";
		else
			cout << pos + i << '\n';
	}

	return 0;
}


Measured memory_bytes: 20596
#include<iostream>
#include<vector>
#include<string>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
using namespace std;


int main() {
	int N, M;

	cin >> N >> M;

	vector<bool> a(N,true);

	vector<long long > sum(N, 0);

	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		a[x-1] = false;
	}

	if (a[0] == true) {
		sum[0] = 1;
		if (a[1] == true)
			sum[1] = 2;
	}
	else {
		if (a[1] == true)
			sum[1] = 1;
	}

	for (int i = 2; i < N; i++) {
		if (a[i] == true) {
			sum[i] = (sum[i - 2] + sum[i - 1])%1000000007;
		}
	}

	cout << sum[N - 1] << endl;

}




Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
ll MOD=1000000007;
int main(){
  ll n;
  cin>>n;
 ll M=0; ll A=0; ll R=0; ll C=0; ll H=0;
  rep(i,n){
    string s;
    cin>>s;
    if(s[0]=='M') M++;
else if(s[0]=='A') A++;
else if(s[0]=='R') R++;
else if(s[0]=='C') C++;
else if(s[0]=='H') H++;
  }
 cout<<M*A*R+M*A*C+M*A*H+M*R*C+M*R*H+M*C*H+A*R*C+A*R*H+A*C*H+R*C*H<<endl;
return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int A, B, C;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> A >> B >> C;

  int cap = A - B;
  int ans = C < cap ? 0 : C - cap;

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

Measured memory_bytes: 256
import numpy as np
import copy

# 日数
D = int(input())
# type毎の満足度の下がりやすさ
c = np.array(list(map(int, input().split())))
# [d,i]の満足度
s = np.array([list(map(int, input().split())) for _ in range(D)])

# type毎に最後に開催された日を管理
lastday = np.zeros(26)

# d日目の終わりで低下する満足度
def cost(c, d, lastday, choicei):
    total = 0
    for i in range(26):
        # 調べたいtypeの場合は差分=0にしてマイナス計算させない
        lday = d if choicei == i else lastday[i]
        total += c[i] * (d - lday)
    return total

for d in range(D):
    # その日の満足度リストをソートしてindexを取得    
    # sd_sort = np.argsort(s[d])
    max_ans = -1
    typei = -1
    
    sd = s[d]
    for i in range(26):
        ans = sd[i] - cost(c, d+1, lastday, i)
        if ans > max_ans:
            typei = i

    lastday[typei] = d+1 # 日付なので+1
    typei = np.argmax(sd) + 1
    print(typei)


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

int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	map<int,string> verdict;
	map<int,int> count;
	int correct=0,penalty=0;
	while(m--)
	{
		int problem;
		string verd;
		cin>>problem>>verd;
		if(verdict[problem]=="AC")
		continue;
		else if(verd=="WA")
		{
			count[problem]++;
			verdict[problem]=verd;
		}
		else
		{
			penalty+=count[problem];
			correct++;
			verdict[problem]=verd;
		}
	}
	cout<<correct<<" "<<penalty;
	return 0;
}

Measured memory_bytes: 15872
#include<stdio.h>
int main(){
    int r;
    int D;
    int Xi;
    int a,b=1;
    scanf("%d",&r);
    scanf("%d",&D);
    scanf("%d",&Xi);
    int c=r*Xi-D;
    printf("%d\n",c);
    b=c;
    for(int i=1;i<10;i++){
        a=b*r-D;
        b=a;
        printf("%d\n",a);
    }
    return 0;

}


Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n;
    boolean[] primes;
    int[] numPrimes;
    int MOD = 1000000007;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        solve();
    }

    void solve() {
        // prime number s less than sqrt(1000)
        // 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
        primes = (new Primes(1000)).primeSieve(1000);
        numPrimes = new int[1001];
        for (int i = 2; i <= n; i++) {
            calcPrimes(i);
        }
        long ans = 1;
        for (int i = 0; i < numPrimes.length; i++) {
            ans *= numPrimes[i] + 1;
            ans %= MOD;
        }
        System.out.println(ans);
    }

    void calcPrimes(int n) {
        for (int i = 2; i < primes.length; i++) {
            if (!primes[i]) {
                continue;
            }
            while(n % i == 0) {
                numPrimes[i]++;
                n /= i;
            }
        }
    }

    class Primes {
        boolean[] isPrimes;

        Primes(int n) {
            isPrimes = new boolean[n + 1];
        }

        boolean[] primeSieve(int n) {
            for (int i = 2; i <= n; i++) {
                isPrimes[i] = true;
            }

            // mark non-primes <= n using Sieve of Eratosthenes
            for (int factor = 2; factor*factor <= n; factor++) {

                // if factor is prime, then mark multiples of factor as nonprime
                // suffices to consider mutiples factor, factor+1, ...,  n/factor
                if (isPrimes[factor]) {
                    for (int j = factor; factor*j <= n; j++) {
                        isPrimes[factor*j] = false;
                    }
                }
            }
            return isPrimes;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 20308
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[4][105];
int l[4],t[4],f1;
int main()
{
	scanf("%s%s%s",s[1]+1,s[2]+1,s[3]+1);
	l[1]=strlen(s[1]+1);
	l[3]=strlen(s[3]+1);
	l[2]=strlen(s[2]+1);
	f1=1;
	while(1)
	{
		t[f1]++;
		if(t[f1]>l[f1])
		{
			printf("%c",'A'+f1-1);
			return 0;
		}
		f1=s[f1][t[f1]]-'a'+1;
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string.h>
#include <iomanip>
#include <ctype.h>

#define ll          long long int
#define ull         unsigned long long int
#define pb          push_back
#define pii         pair<int,int>
#define F           first
#define S           second
#define vi          vector<int>
#define vli          vector<ll>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define M_PI        3.14159265358979323846
#define mp          make_pair
#define sz(x)       (int)x.size()
//#define hell        1000000007
#define matrix      vector<vector<ll>>
#define forn(i,a,b)  for(int i=a;i<b;i++)
#define eps 0.0000000001
#define all(a)      (a).begin(),(a).end()
const long long INF = (long long) 1e7+1;
const long long mod = (long long) 998244353 ;
const long long hell = (long long) 1000000007;

using namespace std;
#include <stdio.h>

ll power(ll x,ll y)
{
  ll res=1;
  while(y>0){
    if(y%2) res=(x%hell*res%hell)%hell;
    x=(x%hell*x%hell)%hell;
    y=y/2;
  }
  return res;
}

ll modinv(ll x){
  return power(x,hell-2);
}

void solve();


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

int main(){
   fastIO();
   int test;
   //cin>>test;
   test=1;
   
   while(test--)
   solve();
}
//void sieve();
ll pw(ll k,ll x);
ll gcd(ll x,ll y);

/*
  For freq or prime factors

for(auto pri:prime){
  while(k%pri==0){
    pcnt[pri]++;
    k/=pri;
  }
}*/

void solve(){
    string s;
    cin>>s;
    
    int q;
    cin>>q;
    int cur=0;    
    deque<char> f,b;
        
    while(q--){
        int t;
        cin>>t;
        
        if(t==1){
            cur++;
        }
        else{
            int y;
            cin>>y;
            char c;
            cin>>c;
            
            if(cur&1){
               if(y==1)
                b.push_back(c);
                else
                f.push_front(c);
            }
            else{
                if(y==1)
                f.push_front(c);
                else
                b.push_back(c);
            }
        }
    }
    if(cur&1){
        while(!b.empty())
        {
            cout<<b.back();
            b.pop_back();
        }
        reverse(s.begin(),s.end());
        cout<<s;
        while(!f.empty())
        {
            cout<<f.back();
            f.pop_back();
        }
    }else{
        while(!f.empty())
        {
            cout<<f.front();
            f.pop_front();
        }
        //reverse(s.begin(),s.end());
        cout<<s;
        while(!b.empty())
        {
            cout<<b.front();
            b.pop_front();
        
    }
    }
}    


///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1

ll gcd(ll a,ll b)
{
    while( b != 0)
	{
		ll  t = b;
		b= a %t;
		a = t;
	}
	return a;
}


ll pw(ll k,ll x){
  if(x==0)
  return 1;
  if(x&1)
  return ((pw(k,x-1))*k);
  else
  return ((pw(k,x/2))*(pw(k,x/2)));
}





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

string s, t;
int S, T;

bool watch (int k) {
    rep(i, T) {
        if (t[i] != s[i + k] && s[i + k] != '?') return false;
    }
    return true;
}

string construct (int k) {
    string ans = s;
    //tを当てはめる
    rep(i, T) {
        ans[k+i] = t[i];
    }
    //残りの？をaに置き換える
    rep(i, S) {
        if (ans[i] == '?') {
            ans[i] = 'a';
        }
    }

    return ans;
}

int main(){
    cin >> s >> t;
    S = s.size();
    T = t.size();

    string ans = " ";

    rep(i, S - T + 1) {
        if (watch(i)) {
            if(ans == " ") ans = construct(i);
            else ans = min(ans, construct(i));
        }
    }
    
    if (ans != " ") cout << ans << endl;
    else cout << "UNRESTORABLE" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

const int MN = int(2e+5) + 10;
mat G(MN, vec(0));
vector<bool> used(MN, false);
vec ans(MN, 0), c(MN, 0);
int dfs(map<int, int> &vmp, int v){
    used[v] = true;
    int num = 1;
    for(int to : G[v]){
        if(!used[to]){
            map<int, int> cmp;
            int cnum = dfs(cmp, to);
            num += cnum;
            ans[c[v]] -= ll(cnum - cmp[c[v]]) * (cnum - cmp[c[v]] + 1) / 2;
            if(vmp.size() < cmp.size()) swap(vmp, cmp);
            for(pair<int, int> p : cmp) vmp[p.fi] += p.se;
        }
    }
    vmp[c[v]] = num;
    return num;
}

int main() {
    cin>>N;
    rep(i,N) {
        cin>>c[i];
        --c[i];
    }
    rep(i,N - 1){
        int a, b;
        cin>>a>>b;
        --a;
        --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    map<int, int> pmp;
    dfs(pmp, 0);
    rep(i,N) ans[i] += (N + 1) * N / 2;
    rep(i,N){
        //cout<<pmp[i]<<endl;
        ans[i] -= (N - pmp[i]) * (N - pmp[i] + 1) / 2;
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 67416
#include <iostream>
#include <cstdio>
#include <cmath>

struct Point {
    double x;
    double y;
};

void koch(int n, Point point1, Point point2)
{
    if(n > 0)
    {
        Point s;
        Point t;
        Point u;
        s.x = (2.0 * point1.x + 1.0 * point2.x) / 3.0;
        s.y = (2.0 * point1.y + 1.0 * point2.y) / 3.0;
        t.x = (1.0 * point1.x + 2.0 * point2.x) / 3.0;
        t.y = (1.0 * point1.y + 2.0 * point2.y) / 3.0;
        double pi_third = M_PI * 60.0 / 180.0;
        u.x = (t.x - s.x) * cos(pi_third) - (t.y - s.y) * sin(pi_third) + s.x;
        u.y = (t.x - s.x) * sin(pi_third) + (t.y - s.y) * cos(pi_third) + s.y;

        koch(n - 1, point1, s);
        printf("%.8f %.8f\n", s.x, s.y);
        koch(n - 1, s, u);
        printf("%.8f %.8f\n", u.x, u.y);
        koch(n - 1, u, t);
        printf("%.8f %.8f\n", t.x, t.y);
        koch(n - 1, t, point2);
    }
}

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

    Point p1 = {0.0, 0.0};
    Point p2 = {100.0, 0.0};
    printf("%.8f %.8f\n", p1.x, p1.y);
    koch(n, p1, p2);
    printf("%.8f %.8f\n", p2.x, p2.y);
}


Measured memory_bytes: 3184
#include<cstdio>
#define N 200005
int n,a[N],b[N];
bool check(int x) {
	for(int i=1;i<2*n;++i) b[i]=(a[i]>=x);
	for(int i=1;i<n;++i) {
		if(b[n+i]==b[n+i-1]) return b[n+i];
		if(b[n-i]==b[n-i+1]) return b[n-i];
	}
	return b[1];
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<2*n;++i) scanf("%d",&a[i]);
	int l=1,r=2*n-1,ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = 998244353;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}


void solve(){
	string s = "";
	string t;
	int k;
	cin >> t >> k;
	vector<bool> good(10);
	if(t == "0" && !good[0]) {
		cout << 0 << '\n';
		return;
	}
	for(int i = 0; i < k; ++i) {
		int x;
		cin >> x;
		good[x] = 1;
	}
	queue<string> q;
	for(int i = 1; i <= 9; ++i){
		if(!good[i]) q.push(to_string(i));
	}
	while(!q.empty()){
		string f = q.front();
		q.pop();
		if(atoi(f.c_str()) >= atoi(t.c_str())){
			cout << f << '\n';
			return;
		}
		for(int i = 0; i < 10; ++i){
			if(!good[i]){
				f += char(i + '0');
				q.push(f);
				f.pop_back();
			}
		}
	}

}


 
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

#define N 100000
int n, m;
int max_path_length[N];
int indegree[N];
bool seen[N];
struct edge {
    int to;
    edge(int to) : to(to) {}
};
vector<edge> G[N];

int rec(int s) {
    if (seen[s])
        return max_path_length[s];
    seen[s] = true;
    int res = 0;
    for (const auto &e : G[s]) {
        res = max(res, rec(e.to) + 1);
    }
    return max_path_length[s] = res;
}
int main() {
    cin >> n >> m;
    rep(i, m) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        indegree[y]++;
        G[x].push_back(edge(y));
    }
    rep(i, n) {
        if (indegree[i] == 0) {
            rec(i);
        }
    }
    cout << *max_element(begin(max_path_length), end(max_path_length)) << endl;
    return 0;
}

Measured memory_bytes: 14560
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

vector<int> V[9];
bool b[9];
int N,M;
int ans;

void dfs(int q , int d){
	if(d == N){
		++ans;
		return;
	}
	repv(int,it,V[q]){
		if(b[*it]) continue;
		b[*it] = 1;
		dfs(*it,d+1);
		b[*it] = 0;
	}
}

int main(){
	scanf("%d%d" , &N , &M);
	repp(i,0,M){
		int a,b;
		scanf("%d%d" , &a , &b);
		V[a].PB(b);
		V[b].PB(a);
	}
	b[1] = 1;
	dfs(1,1);
	printf("%d\n" , ans);
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define int long long

signed main(){
    int n; cin >> n;
    vector<vector<int>> s(n+1, vector<int>(26,0));
    
    rep(i,n){
        string str;
        cin >> str;
        for(char c: str){
            s[i][c-'a']++;
        }
    }
    
    sort(ALL(s));
    
    int ans = 0, now = 0;
    rep(i,n+1){
        if(i==n || s[i] != s[i+1]){
            ans += now * (now-1) / 2;
            now = 0;
        }
        now++;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 24448
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int k;cin>>k;
  vector<int> a(k,7%k);
  for(int i=1; i<k; ++i) a[i]=(a[i-1]*10+7)%k;
  for(int i=0; i<k; ++i) if(a[i]==0){ cout<<i+1<<endl; return 0;}
  cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 7188
import java.util.*;
import java.util.stream.*;

public class Main {
  public static int MOD = 1_000_000_007;

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int H = in.nextInt(), W = in.nextInt(), K = in.nextInt();
    int[][] dp = new int[H + 1][W];
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) {
      for (int k = 0; k < Math.pow(2, W - 1); k++) {
        int val = k;
        int[] arr = new int[W - 1];
        for (int j = 0; j < W - 1; j++) {
          arr[j] = val % 2;
          val /= 2;
        }
        boolean valid = true;
        for (int j = 1; j < W - 1; j++) {
          if (arr[j - 1] == 1 && arr[j] == 1) {
            valid = false;
          }
        }
        if (!valid) {
          continue;
        }
        for (int j = 0; j < W; j++) {
          if (j - 1 >= 0 && arr[j - 1] == 1) {
            dp[i + 1][j - 1] += dp[i][j];
          }
          if (j + 1 < W && arr[j] == 1) {
            dp[i + 1][j + 1] += dp[i][j];
          }
          boolean left = j == 0 ? true : arr[j - 1] == 0;
          boolean right = j == W - 1 ? true : arr[j] == 0;
          if (left && right) {
            dp[i + 1][j] += dp[i][j];
          }
        }
        for (int j = 0; j < W; j++) {
          dp[i + 1][j] %= MOD;
        }
      }
    }
    System.out.println(dp[H][K - 1] % MOD);
  }
}


Measured memory_bytes: 23380
import sys
N,M=map(int,input().split())
slist=list(map(int,input()))

seq=0
for s in slist:
  if s==0:
    seq=0
  else:
    seq+=1
    if seq==M:
      print(-1)
      sys.exit(0)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)      
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res

#segfunc
def segfunc(x,y):
  return min(x,y) #最小値
#ide_ele
ide_ele=float("inf") #最小値
#init
seg=SegTree([float("inf")]*(N+1), segfunc, ide_ele)

dist_list=[float("inf")]*(N+1)
seg.update(N,0)
dist_list[N]=0
for i in reversed(range(N)):
  if slist[i]==0:
    left=i+1
    right=min(i+M,N)
    dist=seg.query(left,right+1)+1
    seg.update(i,dist)
    dist_list[i]=dist

answer_list=[]
i=0
while i<N:
  for j in range(1,M+1):
    if dist_list[i]>dist_list[i+j]:
      answer_list.append(j)
      i+=j
      break
    
print(*answer_list)

Measured memory_bytes: 83420
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if((a * b) % 2 == 0) {
     	System.out.println("Even");
    } else {
    	System.out.println("Odd");
    }
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
int main(){
	int W, H; 
	cin >> W >> H; 
	pair<long long int, int> A[200010] = {}; 
	for(int i = 0; i < W; i++){
		cin >> A[i].first; 
		A[i].second = 1;
	}
	for(int j = 0; j < H; j++){
		cin >> A[j+W].first; 
		A[j+W].second = 2; 
	}
	sort(A, A+H+W); 
	long long int horizontal = (long long) H+1; 
	long long int vertical = (long long) W+1; 
	long long int ans = 0; 
	for(int i = 0; i < H+W; i++){
		if(A[i].second == 1){
			ans += horizontal * A[i].first; 
			vertical --; 
		}
		if(A[i].second == 2){
			ans += vertical * A[i].first; 
			horizontal --; 
		}
	}
	cout << ans << endl;  
}

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

int main(int argc, char const *argv[])
{
    int n[3];
    for (int i=0; i<3; i++) cin >> n[i];
    sort(n, n + 3, greater<int>());

    cout << n[0] * 10 + n[1] + n[2] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c,n;
  int i,j,k,tmp,ans=0;
  scanf("%d%d%d%d",&a,&b,&c,&n);
  for(i=0;i<=a;i++){
    for(j=0;j<=b;j++){
      for(k=0;k<=c;k++){
        tmp = i*500 + j*100 + k*50;
        if(tmp==n)ans++;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
    int H,W;
    while(true){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
            printf("#");
            }
            printf("\n");
            }
            printf("\n");
}
}


Measured memory_bytes: 2608