akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;

int main() {
	int n;
	scanf("%d", &n);
	int minn = 1e9;
	int maxx = -1;
	int cntmin = 0;
	int cntmax = 0;
	for (int i=0 ; i<n ; i++) {
		int x;
		scanf("%d", &x);
		if (x > maxx) {
			maxx = x;
			cntmax = 0;
		}
		if (x < minn) {
			minn = x;
			cntmin = 0;
		}
		if (x == maxx) cntmax++;
		if (x == minn) cntmin++;
	}
	if (maxx - minn >= 2) printf("No\n");
	else if (maxx == minn) {
		if (maxx == n-1 or maxx <= n/2) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	} else {
		maxx -= cntmin;
		n -= cntmin;
		if (minn >= cntmin and maxx <= n/2) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
}

Measured memory_bytes: 256
import std.stdio,std.conv,std.string,std.algorithm;
void main(){
	auto args = readln().chomp().split();
	auto a = to!int(args[0]);
	auto b = to!int(args[1]);
	auto c = to!int(args[2]);
	auto arg = [a,b,c].sort();
	writeln(arg[0]," ",arg[1]," ",arg[2]);
}

Measured memory_bytes: 1064
from collections import Counter

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

if __name__ == '__main__':
    n, m = map(int, input().split())
    ans = 1
    cnt = Counter(prime_factors(m))
    for i in cnt.values():
        ans *= nCr(i+n-1, i)
        ans %= 10**9+7
    print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;

using namespace std;

int a[20005];
int b[20005];
int p[20005];

int main()
{
	int N;
	cin >> N;
	REP(i, N)
	{
		cin >> p[i];
	}

	REP(i, N)
	{
		a[i] = 1 + 20000 * i;
		b[N - 1 - i] = 1 + 20000 * i;
	}
	REP(i, N)
	{
		a[p[i] - 1] += i;
	}
	REP(i, N)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	REP(i, N)
	{
		cout << b[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define je 1000000007
using namespace std;

int n;
long long fact[1000005];
long long inv[1000005];

long long ginv(long long x){
    long long ret = 1;
    long long gop = x;
    int lft = je - 2;
    while(lft){
        if(lft&1) ret = (ret * gop) % je;
        gop = (gop * gop) % je;
        lft >>= 1;
    }
    return ret;
}

int main(){
    scanf("%d",&n);
    fact[0] = 1; inv[0] = 1;
    fact[1] = 1; inv[1] = 1;
    for(int i=2;i<=n+1;i++){
        fact[i] = (fact[i-1] * i) % je;
        inv[i] = ginv(fact[i]);
    }
    long long ans = fact[n];
    int one = n-2, two = 0;
    for(int i=n;i>=1;i--){
        if(one<0) break;
        long long nCr = fact[one+two];
        nCr = (nCr * inv[one]) % je;
        nCr = (nCr * inv[two]) % je;
        long long calc = (nCr * fact[i-1]) % je;
        calc = (calc * fact[n-i]) % je;
        ans = (ans + je - calc) % je;
        one -= 2; two += 1;
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int n,m;
char grid[1009][1009];
int vis[1009][1009];
ll num[1009][1009];
ll dp(int x,int y){
    if(x==n&&y==m)return 1;
    if(x>n||y>m||grid[x][y]=='#')return 0;
    if(vis[x][y])return num[x][y];
    vis[x][y]=1;
//    num[x][y]=(num[x][y]+dp(x,y+1))%mod;
//    num[x][y]=(num[x][y]+dp(x+1,y))%mod;
    num[x][y]=(dp(x,y+1)%mod+dp(x+1,y)%mod)%mod;
    return num[x][y]%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>grid[i][j];
    cout<<dp(1,1)%mod<<endl;
    return 0;
}


Measured memory_bytes: 13312
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, N = lr()
U = 20000 # max(H)+max(A) これ以上は関係ない
INF = 10 ** 8
dp = np.full(U, INF, np.int64)
dp[0] = 0
for i in range(N):
    a, b = lr()
    n = (U + (-U)%a)
    #列のサイズはa
    dp = np.resize(dp, n).reshape(-1, a)
    dp -= (np.arange(n//a) * b)[:, None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n//a) * b)[:, None]
    dp = np.ravel(dp)[:U]

print(min(dp[H:]))
#34

Measured memory_bytes: 13148
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;


int main() {

    long K, N;
    cin >> K >> N;
    vector<long> as;
    for (int i = 0; i < N; ++i) {
        long A;
        cin >> A;
        as.push_back(A);
    }

    vector<long> ts;

    for (int j = 0; j < N - 1; ++j) {
        ts.push_back(as[j + 1] - as[j]);
    }
    ts.push_back(K - (as[N - 1] - as[0]));

    std::cout << (K - *max_element(ts.begin(), ts.end())) << "\n";

    return 0;
}


Measured memory_bytes: 4848
s=input()
up=s[0:2]
bot=s[2:4]
bot_m=True
up_m=True
if bot == "00" or int(bot) > 12:
        bot_m=False
if up == "00" or int(up) > 12:
        up_m=False
if bot_m and up_m:
        print("AMBIGUOUS")
elif bot_m and not up_m:
        print("YYMM")
elif not bot_m and up_m:
        print("MMYY")
else:
        print("NA")

Measured memory_bytes: 3064
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<math.h>
#include<unordered_map>
#include<map>

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

int main()
{
	int N, K;
	vector<pair<int, int>> ans;

	cin >> N >> K;
	if (K > (N-1)*(N-2)/2)
	{
		
		cout << -1 << endl;
		return 0;
	}

	int d = 0;
	for (int i = 2; i <= N; ++i)
	{
		ans.emplace_back(1,i);
		//cout << 1 << " " << i << endl;
		if (K < d)
		{
			for (int j = 0; j < d-K; ++j)
			{
				ans.emplace_back(j+2, i);
				//cout << i << " " << j+2 << endl;
			}
			K = 0;
		}
		else
		{
			K -= d;
		}
		++d;
	}

	cout << ans.size() << endl;
	for(auto & a : ans)
	{
		cout << a.first << " " << a.second << endl;
	}

	return 0;
}

Measured memory_bytes: 384
var input = require("fs").readFileSync("/dev/stdin", "utf8");

var words = input.split(' ');

var operand;
if (words[0][0] === words[1][0]) {
    operand = '=';
} else if (words[0] < words[1]) {
    operand = '<';
} else {
    operand = '>';
}
console.log(operand);


Measured memory_bytes: 7372
#include <iostream>

using namespace std;

void attack(int S,int W){
    if(W>S){
        cout << "unsafe";
    }else if (W==S){
        cout << "unsafe";
    }else{
        cout << "safe";
    }


}
int main()
{
    int S,W;
    cin >> S;
    cin >> W;
    attack (S,W);
    return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;

int main() {

	int a, b, ans;

	cin >> a >> b;

	if (a < b * 2) {
		ans = 0;
	}
	else {
		ans = a - b * 2;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[25][25];
bool vis[25][25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct PP {
	int x, y;
	int res;
} s, q;
queue <PP> qua;
int ans;

void Init() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) scanf(" %c", &a[i][j]);
	}
}

bool Chk(int x, int y) {
	if(vis[x][y] || x < 1 || x > n || y < 1 || y > m || a[x][y] == '#') return false;
	return true;
}

int Bfs(int x, int y) {
	int res = 0;
	s.x = x, s.y = y, s.res = 0;
	vis[x][y] = 1;
	qua.push(s);
	while(!qua.empty()) {
		s = qua.front();
		qua.pop();
		res = max(res, s.res);
		for(int i = 0; i < 4; i++) {
			q.x = s.x + dx[i], q.y = s.y + dy[i];
			if(!Chk(q.x, q.y)) continue;
			q.res = s.res + 1;
			vis[q.x][q.y] = 1;
			qua.push(q);
		}
	}
	return res;
}

int main() {
	Init();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(a[i][j] == '.') {
				memset(vis, 0, sizeof(vis));
				while(!qua.empty()) qua.pop();
				int tmp = Bfs(i, j);
				ans = max(ans, tmp);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

ll dp[100010][13]={0};

long long modpow(long long a, long long n, long long mod) {//a^n(mod)を求める
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;//次の準備
        n >>= 1;
    }
    return res;
}

signed main(){
  string s;cin>>s;
  reverse(all(s));

  if(s.at(0)=='?')rep(i,10)dp[0][i]=1;
  else dp[0][s[0]-'0']=1;

  for(int i=1;i < siz(s);i++)
  {
    if(s.at(i)=='?'){
      for(int j=0;j < 13;j++)
      {
        for(int k=0;k < 10;k++)//?
        {
            dp[i][(j+modpow(10,i,13)*k)%13]+=dp[i-1][j];
            dp[i][(j+modpow(10,i,13)*k)%13]%=mod;
          
        }
      }
    }else{
      int x=s[i]-'0';
      for(int j=0;j < 13;j++)
      {
        dp[i][(j+modpow(10,i,13)*x)%13]+=dp[i-1][j];
        dp[i][(j+modpow(10,i,13)*x)%13]%=mod;
      }
    }
  }

  cout<<dp[siz(s)-1][5]<<endl;

}



Measured memory_bytes: 10624
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

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

using namespace std;

typedef long long ll;

int main() {
  ll a,b;
  cin >> a >> b;
  ll c = min(a,(ll)(b/2LL));
  a -= c;
  b -= c * 2LL;
  c += (ll)(b/4LL);
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int a,b,k;
  scanf("%d%d%d",&a,&b,&k);

  int i,c[100],j=0;
  for(i=1;(i<=a)||(i<=b);i++)
    if((a%i==0)&&(b%i==0)){
      j++;
      c[j]=i;
    }

  printf("%d\n",c[j-k+1]);
  return 0;
}


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

int main() {
        int a, b, c, cnt = 0;
        scanf("%d %d %d", &a, &b, &c);
        if( a&1 || b&1 || c&1 ) {
                cout << 0 << endl;
                return 0;
        }
        if( a == b && a == c ) {
                cout << -1 << endl;
                return 0;
        }
        while( a%2 == 0 && b%2 == 0 && c%2 == 0 ) {
                int x, y, z;
                x = b/2 + c/2;
                y = a/2 + c/2;
                z = a/2 + b/2;
                a = x, b = y, c = z;
                cnt++;
                if( a == b && a == c ) {
                        cout << -1 << endl;
                        return 0;
                }
        }
        cout << cnt << endl;

        return 0;
}


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

using namespace std;

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

    vector<int> vec(N);

    for (int i = 0; i < N; i++)
    {
        cin >> vec.at(i);
    }
    
    sort(vec.rbegin(), vec.rend());

    int sumA = 0;
    int sumB = 0;

    for (int i = 0; i < N; i = i + 2)
    {
        sumA += vec.at(i);
    }
    
    for (int i = 1; i < N; i = i + 2)
    {
        sumB += vec.at(i);
    }

    cout << sumA - sumB << endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <functional>
#include <tuple>
#include <climits>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <iomanip>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> D(K);
    for(auto &d : D) cin >> d;
    while(true) {
start:
        stringstream ss;
        ss << N;
        for(auto &d : D) {
            stringstream ss2;
            ss2 << d;
            if(ss.str().find(ss2.str()) != string::npos) {
                N++;
                goto start;
            }
        }
        break;
    }
    cout << N << endl;
}


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

using namespace std;

int main(){
	int n,a,b,c;
	int m=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a[3];
		for(int j=0;j<3;j++)scanf("%d",&a[j]);
		std::sort(a,a+3);
		
		int d = 20;
		if(a[0]>d || a[1]>d || a[2]>d)puts("hogehogehoge");
		
		if(a[0]*a[0]+a[1]*a[1] == a[2]*a[2]){
			puts("YES");
		}else{
			puts("NO");
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int N, dp[2][12];
int main(){
    cin>>N;
    for(int i=0;i<10;i++)dp[0][i]=dp[1][i]=-1e9;
    dp[0][0]=0;
    while(N--){
        int x;
        cin>>x;
        for(int i=0;i<10;i++){
            int y = (i+x)%10;
            dp[1][i] = max(dp[1][i], dp[0][i]);
            dp[1][y] = max(dp[1][y], dp[0][i] + x);
        }
        swap(dp[0],dp[1]);
    }
    cout<<*max_element(dp[0]+1,dp[0]+11);
    
    return 0;
}


Measured memory_bytes: 256
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define LL long long
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define lc (x<<1)
#define rc ((x<<1)|1)

int main(){
  //  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    int i,n,sum;
    cin>>n;
    for (sum=0,i=1;sum<n;sum+=i,i++);
    cout<<i-1<<endl;
    
  //  system("pause");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
const ll INF = 1e18;
#define print(x) cout << (x) << endl;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    string answer = "Good";
    for (int i= 0; i< 3; i++) {
        if(S[i] == S[i+1]) answer = "Bad";
    }
    print(answer);
}

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    string s;
    cin >> s;
    bool f = true;
    for (int i = 0; i < 3; i++)
    {
        if (s[i] == s[i + 1])
            f = false;
    }
    cout << (f ? "Good" : "Bad") << endl;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var A float64
	fmt.Scan(&A)
	var B float64
	fmt.Scan(&B)
	numPlug := math.Floor(B / (A - 1))
	numEmpty := numPlug*(A-1) + 1

	if numEmpty < B {
		numPlug++
	} else if B == 1 {
		numPlug = 0
	} else if A == 2 {
		numPlug--
	}
	fmt.Println(numPlug)
}


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

using namespace std;

int main()
{
	int deta[11];

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

	sort (deta, deta + 10);

	for (int i = 9; i >= 7; i--){
		cout << deta[i] << endl;
	}

	return 0;
}

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

/* define const */

/* end up defineing const */

int main()
{
  int A, B;
  cin >> A >> B;

  int sum = A + B;
  int sub = A - B;
  int w = A*B;

  cout << max(sum , max(sub,w)) << endl;
}


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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

ll gcd(ll x, ll y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

int main() {
  ll n;
  cin >> n;

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

  vector<ll> l(n);
  l[0] = a[0];
  for (ll i = 1; i < n; ++i) {
    l[i] = gcd(l[i-1], a[i]);
  }

  vector<ll> r(n);
  r[n-1] = a[n-1];
  for (ll i = n-2; i >= 0; --i) {
    r[i] = gcd(r[i+1], a[i]);
  }

  ll ans = 0;
  for (ll i = 0; i < n; ++i) {
    ll x = (i == 0) ? 0 : l[i-1];
    ll y = (i == n-1) ? 0 : r[i+1];
    ans = max(ans, gcd(x, y));
  }

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

Measured memory_bytes: 2560
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func NextFloat() float64 {
  n, _ := strconv.ParseFloat(NextLine(), 64)
  return n
}
func NextFloatVec() []float64 {
  L := strings.Split(NextLine(), " ")
  N := make([]float64, len(L))
  for i := range N {
    N[i], _ = strconv.ParseFloat(L[i], 64)
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

const p = 1000000007
const p2 = 500000004

func main() {
  N := NextInt()
  C := NextIntVec()
  sort.Ints(C)
  cnt := 0
  for i, c := range C {
    cnt += ((c * p2 % p) * ((1 + (N - 1 - i) * p2) % p)) % p
    cnt %= p
  }
  d := 1
  for i := 0; i < N; i++ {
    d *= 2
    d %= p
  }
  ans := (cnt * (d * d % p)) % p
  Write(ans)
  Output()
}

Measured memory_bytes: 12800
A, B, C = map(int, input().split())
if A == B == C and A%2 == 0:
  print(-1)
else:
  D = 0
  while A%2 == 0 and B%2 == 0 and C%2 == 0:
    D += 1
    AA = B/2 + C/2
    BB = A/2 + C/2
    CC = A/2 + B/2
    A = AA
    B = BB
    C = CC
  print(D)

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

using namespace std;

const long long INF = (1ll<<31)-1;

template<typename T>
class lazy_segment_tree{
	int n;
	T fval;
	vector<T> dat, lazy;
	vector<bool> lazyFlag;
	
public:
	
	lazy_segment_tree(){
		
	}
	
	lazy_segment_tree(int n_, T val){
		init(n_, val);
	}
	
	~lazy_segment_tree(){
		
	}
	
	void init(int n_, T val){
		fval = val;
		
		n = 1;
		
		while(n < n_) n *= 2;
		
		dat.resize(2 * n - 1);
		lazy.resize(2 * n - 1, fval);
		lazyFlag.resize(2 * n - 1, false);
	
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = fval;
	}
	
	void eval(int k, int l, int r){
		
		if(lazyFlag[k]){
			dat[k] = lazy[k] * (r - l);
			
			if(r - l > 1) {
				lazy[2*k+1] = lazy[2*k+2] = lazy[k];
				lazyFlag[2*k+1] = lazyFlag[2*k+2] = lazyFlag[k];
			}
			
			lazyFlag[k] = false;
		}
	}
	
	void update(int a, int b, T x, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) {return ;}
		if(a <= l && r <= b){
			lazy[k] = x;
			lazyFlag[k] = true;
			eval(k, l, r);
		} else {
			update(a, b, x, 2*k+1, l, (l+r)/2);
			update(a, b, x, 2*k+2, (l+r)/2, r);
			dat[k] = (dat[2*k+1] + dat[2*k+2]);
		}
	}
	
	T query(int a, int b, int k = 0, int l = 0, int r = -1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(r <= a || b <= l){
			return fval;
		}
		if(a <= l && r <= b){
			return dat[k];
		}else {
			T vl = query(a, b, k * 2 + 1, l, (l + r) / 2 );
			T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return (vl + vr);
		}
	}
};

signed main(){
	
	lazy_segment_tree<long long> lseg;
	
	int n, q;
	
	cin>>n>>q;
	
	lseg.init(n+10, 0);
	
	for(int i = 0; i < q; i++){
		int com, s, t, x;
		cin>>com>>s>>t;
		s++, t++;
		if(com){
			cout<<lseg.query(s,t+1)<<endl;
		} else {
			cin>>x;
			lseg.update(s, t+1, x);
		}
	}
	
	return 0;
}



Measured memory_bytes: 7060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;
using namespace std;
const long long INF = 1LL << 60;
ll mod = 1e9 + 7;

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

    return 0;
}


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



int main(int argc, char **argv)
{
	ll a,b,c,d;
  cin>>a>>b>>c>>d;
  
  ll ans_1=max(a*c,a*d);
  ll ans_2=max(b*c,b*d);
  
  cout<<max(ans_1,ans_2);
  
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    for(int i=0;i<n-1;i++){
        if(s[i]=='A' && s[i+1]=='C'){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;

int main()
{
    int n,m;
    cin >> n >> m;
    int mi = -1,ma = mod;
    for(int i = 0; i < m; i++){
        int l,r;
        cin >> l >> r;
        mi = max(l,mi);
        ma = min(r,ma);
    }
    if(ma-mi >= 0){
        cout << ma - mi + 1;
    }else{
        cout << 0;
    }
}

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

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using usize = std::size_t;
template<typename T>
using Vector = std::vector<T>;
using String = std::string;
template<typename T>
using UniquePointer = std::unique_ptr<T>;
using namespace std;

#define rep(i, max) for(usize i = 0; i < max; ++i)
#define loop while(true)

UniquePointer<String> readLine() {
    UniquePointer<String> line(new String());
    getline(cin, *line);
    return line;
}

template<typename T1, typename T2>
pair<T1, T2> readPair(){
    T1 res1;
    cin >> res1;
    T2 res2;
    cin >> res2;
    readLine();
    return make_pair(res1, res2);
}

template<typename T>
UniquePointer<Vector<T>> readVector(usize num) {
    UniquePointer<Vector<T>> list(new Vector<T>(num));
    rep(i, num) {
        cin >> (*list)[i];
    }
    readLine();
    return list;
}

void readValues()
{
    readLine();
}

template<typename H, typename... T>
void readValues(H& head, T&&... tails){
    H a;
    cin >> a;
    head = a;
    readValues(forward<T>(tails)...);
}

template<typename T>
void writeLine(T arg) {
    cout << arg << endl;
}

template<typename T>
void write(T arg) {
    cout << arg << std::flush;
}

void program();

int main()
{
    ios::sync_with_stdio(false);
    program();
}

void program() {
    i32 h, a;
    readValues(h, a);
    writeLine((i32)ceil((double)h / a));
}

Measured memory_bytes: 3660
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long num = gcd(a, b);
		long count = 0;
		for (long i = 2; i <= Math.sqrt(num); i++) {
		    if (num % i == 0 && isPrime(i)) {
		        count++;
		        while (num % i == 0) {
		            num /= i;
		        }
		    }
		}
		if (num > 1) {
		    count++;
		}
		System.out.println(count + 1);
   }
   
   static boolean isPrime(long x) {
       for (long i = 2; i <= Math.sqrt(x); i++) {
           if (x % i == 0) {
               return false;
           }
       }
       return true;
   }
   
   static long gcd(long x, long y) {
       if (x % y == 0) {
           return y;
       } else {
           return gcd(y, x % y);
       }
   }
}




Measured memory_bytes: 23636
#include <iostream>
using namespace std;
int main(){
    int a[3]={},b[3]={};
    int x=0;
    
    for(int i=0;i<10;i++){
        cin>>x;
        if(x>a[0]){
             a[2]=a[1];
            a[1]=a[0];
            a[0]=x;
            }
        else if(x>a[1]){
            a[2]=a[1];
            a[1]=x;
        }
        else if(x>a[2])a[2]=x;
    }
    for(int j=0;j<10;j++){
        cin>>x;
        if(x>b[0]){
            b[2]=b[1];
            b[1]=b[0];
            b[0]=x;
        }
        else if(x>b[1]){
            b[2]=b[1];
            b[1]=x;
        }
        else if(x>b[2])b[2]=x;
    }
    
    int q=0,y=0;
    q=a[0]+a[1]+a[2];
    y=b[0]+b[1]+b[2];
    
    cout<<q<<" "<<y<<endl;
    


}

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define loop(i,x,n) for(ll i = x;i<n;i++)
#define loopr(i,x,n) for(ll i = n-1;i>=x;i--)
#define S(v) sort(v.begin(), v.end());
#define ff first
#define ss second    

int main()
{    // freopen("in.txt", "r", stdin);
	ll n;
	cin>>n;
	vector<ll> v(n);
	loop(i,0,n)cin>>v[i];
	ll ans = 0;
	if(n <= 2){
		cout<<0;
		return 0;
	}
	loop(i,0,n){
		loop(j,i+1, n){
			loop(k, j+1, n){
				if(v[i] == v[j] || v[j] == v[k] || v[i] == v[k])continue;
				vector<ll> temp = {v[i], v[j], v[k]};
				S(temp);
				if(temp[0] + temp[1] > temp[2])ans++;
			}
		}
	}
	cout<<ans;
}
/*

*/




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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n;
    cin >> n;
    vector<pair<ll,ll>> t(n);
    ll tmp = -1;
    for(i = 0;i < n;++i){
        cin >> t.at(i).first;
        t.at(i).first != tmp ? t.at(i).second = 1 : t.at(i).second = 0;
        tmp = t.at(i).first;
    }
    vector<pair<ll,ll>> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i).first;
    }
    tmp = -1;
    for(i = 0;i < n;++i){
        a.at(n-1-i).first != tmp ? a.at(n-1-i).second = 1 : a.at(n-1-i).second = 0;
        tmp = a.at(n-1-i).first;
    }
    ll ans = 1;
    ll MOD = 1e9+7;
    for(i = 0;i < n;++i){
        if(t.at(i).second == 0 && a.at(i).second == 0){
            ans *= min(t.at(i).first, a.at(i).first);
            ans %= MOD;
        }else if(t.at(i).second == 1 && a.at(i).second == 1){
            if(t.at(i).first != a.at(i).first){
                cout << 0 << endl;
                return 0;
            }
        }else{
            if(t.at(i).second == 0){
                if(t.at(i).first < a.at(i).first){
                    cout << 0 << endl;
                    return 0;
                }
            }else{
                if(a.at(i).first < t.at(i).first){
                    cout << 0 << endl;
                    return 0;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
use std::io;

fn main() {
    loop {
        let mut buf = String::new();
        io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();

        let a: i32 = iter.next().unwrap().parse().unwrap();
        let op: String = iter.next().unwrap().parse().unwrap();
        let b: i32 = iter.next().unwrap().parse().unwrap();

        println!(
            "{}",
            match op.as_ref() {
                "+" => a + b,
                "-" => a - b,
                "*" => a * b,
                "/" => a / b,
                "?" => break,
                _ => panic!("Invalid operation!"),
            }
        );
    }
}


Measured memory_bytes: 5024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using LL = long long;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<long> VL;

#define NIL -1;
struct Node {
  int parent;
   int left;
  int right;
};

int sibling(int id, vector<Node> L) {
  int p = L.at(id).parent;
  if (p == -1) return -1;
  int r = L.at(p).right;
  int l = L.at(p).left;

  if (r == id) {
    return l;
  } else {
    return r;
  }
}

int degree(int id, vector<Node> L) {
  Node n = L.at(id);
  if (n.right != -1 && n.left != -1) {
    return 2;
  } else if (n.right == -1 && n.left == -1){
     return 0;
  } else {
    return 1;
  }
}

int depth(int id, vector<Node> L) {
  int dep = 0;
  Node n = L.at(id);
  while (n.parent != -1) {
    n = L.at(n.parent);
    dep++;
  }
  return dep;
}

int height(int id, vector<Node> L) {
  if (id == -1) return -1;
  Node n = L.at(id);
  return max(height(n.left, L)+1, height(n.right, L)+1);
}

string node_type(int id, vector<Node> L) {
  Node n = L.at(id);

  if (n.parent == -1) {
    return "root";
  }
  else if (n.right == -1 && n.left == -1) {
    return "leaf";
  } else {
    return "internal node";
  }
}

int main() {
  int n; cin >> n;
  vector<Node> L(n);

  rep(i, n) {
    L.at(i).parent = NIL;
  }

  rep(i, n) {
    int id, r, l; cin >> id >> l >> r;
    L.at(id).left = l;
    L.at(id).right = r;

    if (l != -1) {
      L.at(l).parent = id;
    }
    if (r != -1) {
      L.at(r).parent = id;
    }
  }

  rep(i, n) {
    cout << "node" << " " << i << ":" << " ";
    cout << "parent" << " = " << L.at(i).parent << ", ";
    cout << "sibling" << " = " << sibling(i, L) << ", ";
    cout << "degree" << " = " << degree(i, L) << ", ";
    cout << "depth" << " = " << depth(i, L) << ", ";
    cout << "height" << " = " << height(i, L) << ", ";
    cout << node_type(i, L);
    cout << endl;
  }
}



Measured memory_bytes: 3160
K = int(input())
S = list(input())
total = 0
R,G,B = 0,0,0

for a in range(0,K):
  if S[a]=="R":
    R += 1
  elif S[a]=="G":
    G += 1
  else :
    B += 1
    
total = R*G*B

for i in range(0,K):
  for j in range(i,K):
    k = 2*j-i
    if k<K:
      if S[i] != S[k] and S[i] != S[j] and S[j] != S[k]:
        total -= 1
print(total)

Measured memory_bytes: 9216
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

int func(int n){
    if(n==1)return 300000;
    else if(n==2)return 200000;
    else if(n==3)return 100000;
    else return 0;
}

void solve(){
    int x,y;
    cin>>x>>y;
    int ans=0;
    ans=func(x)+func(y);
    if(x==1&&y==1)ans+=400000;
    cout<<ans<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}

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

#define ll long long
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MAX 1e9
#define MIN -1e9
#define MOD 1000000007
#define println(x) cout << "[" << #x << ":" << x << "]\n"; 
#define print(x) cout << "[" << #x << ":" << x << "] "; 

int main(){
	ios::sync_with_stdio(0); 
    cin.tie(0); 
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	ll n, ans = 0;
	string s;
	cin >> n;
	ll ac=0, wa=0, tle=0, re=0;
	while(n--){
		cin >> s;
		if(s == "AC")
			ac++;
		else if(s == "WA")
			wa++;
		else if(s == "RE")
			re++;
		else
			tle++;
	}
	cout << "AC x " << ac << "\n";
	cout << "WA x " << wa << "\n"; 
	cout << "TLE x " << tle << "\n"; 
	cout << "RE x " << re << "\n"; 

	return 0;
}

Measured memory_bytes: 3644
import sys
input = sys.stdin.readline
from math import floor

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)] + [0]

    for i in range(n):
        if a[i+1] == 0:
            yield a[i] // 2
        else:
            yield a[i] // 2 + a[i] % 2
            a[i+1] -= a[i] % 2


print(sum(main()))


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

int main(){
  int n;
  long ans=0;
  unordered_map<string,long> a;
  string s;
  cin >> n;
  
  for(int i=0;i<n;i++){
  	cin >> s;
    sort(&s[0],&s[9]+1);
    a[s]+=1;
  }
  for(auto itr=a.begin();itr!=a.end();itr=next(itr,1)){
  	if(itr->second!=1)ans+=itr->second*(itr->second-1)/2;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 10660
using System;
using System.Collections.Generic;
using System.Linq;

namespace AOJ
{
    class PrimeNumber
    {
        public static void Main()
        {
            // 6桁の素数をすべて求める
            var prime = new List<int>() { 2 };
            for (int i = 3; i <= 999999; i = i + 2)
            {
                bool is_prime = true;
                foreach (var p in prime)
                {
                    if (i % p == 0)
                    {
                        is_prime = false;
                        break;
                    }
                    else if (p > Math.Sqrt(i)) { break; }
                }
                if (is_prime) { prime.Add(i); }
            }

            while (true)
            {
                string test = Console.ReadLine();
                if (string.IsNullOrEmpty(test)) { break; }
                Console.WriteLine(prime.Count(x => x <= int.Parse(test)));
            }
        }
    }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        b[a[i]-1]++;
    }
    for (int i = 0; i < n; i++) {
        cout << b[i] << endl;
    }
}


Measured memory_bytes: 4720
fun run(): String {
	val num = readLine()!!.toInt()
	val list = readLine()!!.split(Regex("\\s"), num)
	list.forEachIndexed { i, it ->
		if (it == "Y") {
			return "Four"
		}
	}
	return "Three"
}

fun main(args: Array<String>) {
	println(run())
}

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

using namespace std;

vector<int> divisor(int n) {
	vector<int> tmp;
	for (int i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			tmp.push_back(i);
			if (i != n / i) tmp.push_back(n / i);
		}
	}
	sort(tmp.begin(), tmp.end(), greater<int>());
	return tmp;
}

int main() {
	int n, k; cin >> n >> k;
	vector<int> a(n), r(n), div;
	int sum = 0, ans = 1;
	for (int i = 0; i < n; ++i) cin >> a[i], sum += a[i];
	div = divisor(sum);
	for (int d : div) {
		for (int i = 0; i < n; ++i)
			r[i] = a[i] % d;
		sort(r.begin(), r.end());
		vector<int> tsum(n); tsum[0] = r[0];
		for (int i = 1; i < n; ++i)
			tsum[i] = r[i] + tsum[i - 1];
		bool flag = false;
		for (int i = 0; i < n; ++i) {
			int r = tsum[i], l = (n - i - 1) * d - (tsum[n - 1] - tsum[i]);
			if (r == l && r <= k) flag = true;
		}
		if (flag) {
			ans = d;
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <cstring>
#include <cctype>
#include <ctype.h>

#define INF 100000000

using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    bool flag = true;
    int cnt = 0;
    while (flag)
    {
        cnt++;
        for (int i = 0; i < n; i++)
        {
            if (a[i] % 2 == 0)
            {
                a[i] /= 2;
            }
            else
            {
                flag = false;
                cnt--;
                break;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
    #include<vector>
    #define _GLIBCXX_DEBUG

    using namespace std;
    int main()
    {

        string S;
        cin >> S;
        long long K;
        cin >> K;
        vector<long long> sameCharLength(S.size() + 1, 0);
        int i = 1;
        int j = 1;
        int firstLength = -1;
        while(i < S.size()){
            if(S[i - 1] == S[i]){
                j++;
            } else {
                sameCharLength.at(j)++;
                if(firstLength == -1){
                    firstLength = j;
                }
                j = 1;
            }
            i++;
        }
        int lastLength = j;
        if(j == S.size()){
            long long allSameLength = j * K;
            cout << allSameLength / 2 << endl;
            return 0;
        }else if(S[S.size()-1] == S[0]){
            sameCharLength.at(firstLength)--;
            sameCharLength.at(lastLength + firstLength)++;
            for(int i = 1; i <= S.size(); i++){
                sameCharLength.at(i) *= K;
            }
            sameCharLength.at(lastLength + firstLength)--;
            sameCharLength.at(lastLength)++;
            sameCharLength.at(firstLength)++;
        } else {
            sameCharLength.at(lastLength)++;
            for(int i = 1; i <= S.size(); i++){
                sameCharLength.at(i) *= K;
            }
        }
        long long result = 0;
        for(int i = 1; i <= S.size(); i++){
            result += sameCharLength.at(i) * (i / 2);
        }
        cout << result << endl;
        return 0;
    }

Measured memory_bytes: 256
a, b, c, d = map(int,input().split())

# 単にif min(b, d) >= max(a, c): min(b, d) - max(a, c) else 0でいいじゃん
# めっちゃ集中力切れてた

if min(b, d) >= max(a, c):
    print(min(b, d) - max(a, c))
else:
    print(0)

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

int main() {
  int n;
  cin >> n;
  map<int, int> m;
  rep(i, n) {
    int a;
    cin >> a;
    m[a]++;
  }
  int ans = 0;
  for (auto x : m) {
    if (x.second % 2 == 1) ++ans;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4864
import sys

input = sys.stdin.readline

P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    for k in reversed(range(1, (N+1)+1)):
        a = (N + (N-k+1))*k//2
        b = k*(k-1)//2
        ans += a - b + 1
        ans %= P

        if k == K :
            break

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9192
#include "bits/stdc++.h"
using namespace std;
#define all(v) (v).begin(), (v).end()
#define io ios::sync_with_stdio(0)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rson rt << 1 | 1, mid + 1, r
#define lson rt << 1, l, mid
#define lll __int128
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eps 1e-12
#define int long long
const int mod = 998244353;
inline int ksm(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            ans = ans * a % mod;
    return ans;
}

int dp[300000][2];
pii a[300000];
int nxt[300000];
int mx[300000*4];
void upd(int rt,int l,int r,int p,int v){
    if(l==r){mx[rt]=v;return ;}int mid=l+r>>1;
    if(p<=mid)upd(lson,p,v);else upd(rson,p,v);
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
int que(int rt,int l,int r,int L,int R){
   // cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
    if(L<=l&&r<=R)return mx[rt];int mid=l+r>>1;
    int res=0;if(L<=mid)res=max(res,que(lson,L,R));
    if(R>mid)res=max(res,que(rson,L,R));
    return res;
}
signed main()
{
    io; int n;
    cin>>n;
    rep(i,1,n)cin>>a[i].fi>>a[i].se;
    sort(a+1,a+1+n);
    nxt[n]=n+1;
    for(int i=n-1;i;i--){
        if(a[i].fi + a[i].se -1 >= a[i+1].fi) {
            int p=upper_bound(a+1,a+1+n,mp(a[i].fi+a[i].se-1,1000000000ll))-(a+1);
           // cout<<i<<"----"<<p<<endl;
            nxt[i]=max(p+1,que(1,1,n,i,p));
        }
        else nxt[i]=i+1;
      //  cout<<i<<" "<<a[i].fi<<" "<<a[i].se<<" "<<nxt[i]<<endl;
       upd(1,1,n,i,nxt[i]);
    }
    dp[n+1][0]=1;
    for(int i=n;i;i--){
        dp[i][0] += dp[i+1][0];
        dp[i][0] += dp[i+1][1];
        dp[i][0]%=mod;
        dp[i][1]+=dp[nxt[i]][0];
        dp[i][1]+=dp[nxt[i]][1];
        dp[i][1]%=mod;
    }
    cout<<(dp[1][1] + dp[1][0])%mod<<endl;




    getchar();getchar();
}
/*

3

1 10
2 20
3 20

*/

Measured memory_bytes: 18688
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;
int dp[105][4][2];
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int K;
    cin >> K;
    dp[0][0][0] = 1;
    rep(i, n)rep(j, 4)rep(k, 2) {
        int nd = s[i] - '0';
        rep(d, 10) {
            int ni = i+1, nj = j, nk = k;
            if (d != 0 ) nj++;
            if (nj > K) continue;
            if (k == 0) {
                if (d > nd) continue;
                if (d < nd) nk = 1;
            }
            dp[ni][nj][nk] += dp[i][j][k];
        }
    }
    int ans = dp[n][K][0] + dp[n][K][1];
    cout << ans << endl;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin>>n;
  int count=0;
  for(int i=1;i<10;i++){
    for(int k=1;k<10;k++){
      if(i*k==n){
        count+=1;
      }
      else{
        count+=0;
      }
    }
  }
  if(count!=0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


 

Measured memory_bytes: 256
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long

using namespace std;

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

const int N = 5000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, k, a[N];
bitset<N> dp[N], dp2[N];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++){
		dp[i] = (dp[i - 1] | (dp[i - 1] << a[i]));
	}
	dp2[n + 1][0] = 1;
	for (int i = n; i >= 1; i--){
		dp2[i] = (dp2[i + 1] | (dp2[i + 1] << a[i]));
	}
  	
	for (int i = 0; i <= n + 1; i++){
		dp2[i][N - 1] = 1;
		dp[i][N - 1] = 1;
	}
	//cout << "YES" << endl;
  	int ans = n;
	for (int i = 1; i <= n; i++){
		bool f = 0;
		//cout << "YES" << endl;
      	for (int j = max(0ll, k - a[i]); j < k; j++){
			//cout << "YES" << endl;
          	//cout << j << endl;
          	if (dp[i - 1][j] | dp2[i + 1][j]) f = 1;
			//cout << "YES2" << endl;
        }
      	//cout << "YES2" << endl;
		//cout << dp[i + 1][3] << '\n';
		for (int j = 0; j < k - a[i]; j++){
			if(!dp[i - 1][j]) continue;
			//cout << "YES" << endl;
          	int x = dp2[i + 1]._Find_next(k - a[i] - j - 1);
			//cout << "YES2" << endl;
          	if (j + x < k) f = 1;
		}
		if (f) ans--;
	}
	cout << ans;







	return 0;
}


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

int main(void) {
	int n, m,c;
	cin >> n >> m >> c;
	vector<vector<int>> a(n, vector<int>(m));
	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];	
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = 0; j < m; j++) {
			sum += a[i][j] * b[j];
		}
		sum += c;
		if (sum > 0) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n,s,a[3010],ans;
int dp[3010][3010];
signed main(){
    cin>>n>>s;
    rep(i,n)cin>>a[i];
    rep(i,n){
        if(a[i]<=s){
            dp[i+1][a[i]]+=i+1;//new
            dp[i+1][a[i]]%=998244353;
        }
        for(int j=s-1;j>=1;j--){
            if(j+a[i]<=s){
                dp[i+1][j+a[i]]+=dp[i][j];//use
                dp[i+1][j+a[i]]%=998244353;
            }
            dp[i+1][j]+=dp[i][j];//unuse
            dp[i+1][j]%=998244353;
        }
        ans+=dp[i+1][s]*(n-i);
        ans%=998244353;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 71936
#include<stdio.h>
#include<math.h>
int main(void){
    double xa,ya,ra,xb,yb,rb,sa,wa,d;
    int i,n;
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%lf%lf%lf%lf%lf%lf",&xa,&ya,&ra,&xb,&yb,&rb);
        d=(xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);
        sa=(ra-rb)*(ra-rb);
        wa=(ra+rb)*(ra+rb);
        if(d>wa){
            printf("0\n");
        }else if(wa>=d && d>=sa){
            printf("1\n");
        }else if(ra>rb){
            printf("2\n");
        }else{
            printf("-2\n");
        }
    }
    return 0;
}

Measured memory_bytes: 620
n = gets.to_i
sprev = gets.chomp

count = Hash.new(0)
count[sprev] += 1
(n-1).times do |i|
	snext = gets.chomp
	count[snext] += 1
	if count.values.include?(2)
		print("No\n")
		exit
	end
	if sprev[-1] == snext[0]
		sprev = snext
		next
	else
		print("No\n")
		exit
	end

end

print("Yes\n")

Measured memory_bytes: 1788