akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define SIZE (10*10*10*10*10)

typedef struct _ab {
  int a;
  int b;
} ab_t;

int compare(ab_t *a, ab_t *b)
{
  return a->a - b->a;
}

void bsort(ab_t *ab, int size)
{
  int i;
  int change = 1;
  ab_t tmp;

  while (change) {
    change = 0;
    for(i=0; i<(size - 1); i++) {
      if (ab[i].a > ab[i+1].a) {
        tmp = ab[i];
        ab[i] = ab[i+1];
        ab[i+1] = tmp;
        change = 1;
      }
    }// for
  }//while

  return;
}

int main()
{
  int cnt;
  int  N, M;
  long long int  A[SIZE] = {0,};
  long long int  B[SIZE] = {0,};
  ab_t ab[SIZE] = {{0,0},};
  long long int cost;
  long long int num;
  int i,j;
  int result = 0;

  cnt = scanf("%d %d", &N, &M);

  for (i=0; i<N; i++) {
    cnt = scanf("%lld %lld", &A[i], &B[i]);
    ab[i].a = A[i];
    ab[i].b = B[i];
  }

  //bsort(&ab, N);
  qsort(ab, N, sizeof(ab_t), compare);

  cost = 0;
  result = 0;
  for (i=0; i<N; i++) {
    if (result < M) {
      num = M - result;
      if (num > ab[i].b) {
        num = ab[i].b;
      }
      cost += num * ab[i].a;
      result += num;
    } else {
      break;
    }
  }

  printf("%llu", (unsigned long long int)cost);

  return 0;
} 

Measured memory_bytes: 3324
from collections import Counter

n = int(input())
a_li = list(map(int, input().split()))

ans_sum = 0

counter = Counter(a_li)

for i in counter.values():
    ans_sum += i*(i - 1) // 2

for a in a_li:
    count = counter[a]
    if count == 1:
        print(ans_sum)
    else:
        print(ans_sum - count*(count - 1) // 2 + (count - 1)*(count - 2) // 2)


Measured memory_bytes: 26780
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define EPS 1e-9
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

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;}

#define MAX 200000

signed main(void) {
    int n;
    cin >> n;
    vi p(MAX, 1);
    p[0] = p[1] = 0;
    rep(i,MAX)if(p[i]){
        for(int j = 2; i*j < MAX; j++)p[i*j] = 0;
    }
    loop(i,n,MAX)if(p[i]){
        cout << i << endl;
        return 0;
    }
}


Measured memory_bytes: 1792
s = input()
t = input()


S = list(s)
T = list(t)

for i in range(len(s)):
  for j in range(len(S)-1):
    S.append(S[j])
  del S[0:len(s)-1]
  
  if ("".join(S)) == t:
    print("Yes")
    exit()
    
print("No")




Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int memo[5005][5005];
int n,ms;
string s;
int dp(int n,int m)
{
	if (n==0&&m==ms) return 1;
	if (n==0) return 0;
	if (memo[n][m]!=-1) return memo[n][m];
	int &res=memo[n][m];
	res=((m==0?dp(n-1,0):2*dp(n-1,m-1))%mod + dp(n-1,m+1))%mod;
	return res;
}

int main()
{
	scanf("%d",&n);
	getchar();
	getline(cin,s);
	ms=s.size();
	memset(memo,-1,sizeof(memo));
	printf("%d\n",dp(n,0));
}

Measured memory_bytes: 98304
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto whxy = readln.split.to!(double[]);
    auto W = whxy[0];
    auto H = whxy[1];
    auto X = whxy[2];
    auto Y = whxy[3];

    writefln("%.012f %d", W*H/2, W/2 == X && H/2 == Y ? 1 : 0);
}

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

int n, x, y;
vector<int> a;
vector<int> memox;
vector<int> memoy;

int recur(int index, bool turn) {
	if (turn) {
		if (memox[index] != -1) return memox[index];
		if (index > 0) memox[index] = max(abs(a[n-1] - a[index-1]), abs(a[n-1] - a[n-2]));
		else memox[0] = max(abs(a[n-1] - y), abs(a[n-1] - a[n-2]));
		for (int i = index+1; i < n; i++) {
			memox[index] = max(memox[index], recur(i, false));
		}
		return memox[index];
	}
	else {
		if (memoy[index] != -1) return memoy[index];
		memoy[index] = min(abs(a[n-1] - a[index-1]), abs(a[n-1] - a[n-2]));
		for (int i = index+1; i < n; i++) {
			memoy[index] = min(memoy[index], recur(i, true));
		}
		return memoy[index];
	}
}

int main() {
	scanf("%d %d %d", &n, &x, &y);
	a.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	if (n == 1) {
		printf("%d\n", abs(a[0] - y));
		return 0;
	}
	memox.resize(n+1);
	memoy.resize(n+1);
	for (int i = 0; i <= n; i++) {
		memox[i] = -1;
		memoy[i] = -1;
	}
	printf("%d\n", recur(0, true));
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define CLASS 9

struct ClassData {
	char name[16];
	int am_visitors;
	int pm_visitors;
	int all_visitors;
	unsigned int income;
};

int main(void) {

	struct ClassData data[CLASS];
	int i;

	for (i = 0; i < CLASS; i++) {
		scanf("%s %d %d",data[i].name, &data[i].am_visitors,&data[i].pm_visitors);
		data[i].income = 200 * data[i].am_visitors + 300 * data[i].pm_visitors;
		data[i].all_visitors = data[i].am_visitors + data[i].pm_visitors;
	}
	for (i = 0; i < CLASS; i++)
		printf("%s %d %lu\n",data[i].name,data[i].all_visitors,data[i].income);
	return 0;
}

Measured memory_bytes: 600
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string[] str = Console.ReadLine().Split();
		int ans = 0;
		int[]A = new int[N];
		for(var i=0;i<N;i++){
			A[i] = int.Parse(str[i]);
		}
		for(var i=0;i<N-2;i++){
			if((A[i]>A[i+1] && A[i+2]>A[i+1]) || (A[i]<A[i+1] && A[i+2]<A[i+1])){
			} else {
				ans += 1;
			}
		}
		Console.WriteLine(ans);
	}
}

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

using namespace std;

pair <int, int> a[100010];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int foo;
    scanf("%d", &foo);
    a[i] = make_pair(foo, i);
  }
  sort(a, a + n);
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i].second % 2 != i % 2) {
      ++ans;
    }
  }
  printf("%d\n", ans / 2);
  return 0;
}

Measured memory_bytes: 1152
n, k, q = map(int, input().split())

score = [ k-q for i in range(n)]

for i in range(q):
  score[int(input())-1] += 1

for i in range(n): 
  if score[i] > 0: print('Yes', sep='\n')
  else: print('No', sep='\n')

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

ll int maxProfit(ll a[],ll v[],int w,int n){

    vector<vector<ll>> dp(n+1,vector<ll>(w+1,0));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){

            if(a[i-1]<=j){
                dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-a[i-1]]);

            }else{
                dp[i][j]=dp[i-1][j];

            }

        }
    }

    return dp[n][w];



}

int main() {
    int n,w;
    cin>>n>>w;
    
    ll a[n];
    ll v[n];


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

    }

    cout<<maxProfit(a,v,w,n);





}


Measured memory_bytes: 83120
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n,k = I2()
    l = [1]*n
    for i in range(k):
        d = I()
        a = Intl()
        for i in a:
            l[i-1] = 0
    print(sum(l))

Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	//input
	int d; cin >> d;
	vector<int>c(26);
	for (int i = 0; i < 26; i++)cin >> c.at(i);
	vector<vector<int>>s(d, vector<int>(26));
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < 26; j++)cin >> s.at(i).at(j);
	}
	//好奇心
	for (int i = 0; i < 365; i++) {
		cout << (i%26)+1 << endl;
	}
}

Measured memory_bytes: 3680
import java.util.*;

public class Main {
    
    static int[] L;
    static int[] R;
    static int[] p;
    static int[] q;
    static long[][] table;
    static int N;
    static int M;
    static int Q;
    
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        Q = sc.nextInt();
        
        L = new int[M];
        R = new int[M];
        p = new int[Q];
        q = new int[Q];
        table = new long[N+1][N+1];
        
        for(int i = 0; i < M; i++){
            L[i] = sc.nextInt();
            R[i] = sc.nextInt();
        }
        
        for(int i = 0; i < Q; i++){
            p[i] = sc.nextInt();
            q[i] = sc.nextInt();
        }
        
        buildTable();
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < Q; i++){
            sb.append( getSum(p[i], q[i]) ).append("\r\n");
        }
        System.out.println( sb.toString() );
        
    }
    
    static void buildTable(){
        
        for(int i = 0; i < M; i++){
            table[R[i]][L[i]]++;
        }
        
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                if( j > 1 ) table[i][j] += table[i][j-1];
                if( i > 1 ) table[i][j] += table[i-1][j];
                if( i > 1 && j > 1 ) table[i][j] -= table[i-1][j-1];
            }
        }
        
    }
    
    static long getSum(int L, int R){
        return table[R][R] - table[R][L-1] - table[L-1][R] + table[L-1][L-1];
    }
}


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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n,a,b;

main() {
    cin >> n;
    b = n;
    while(b) {
        a += b%10;
        b /= 10;
    }
    if (n%a) ct("No")
    else ct("Yes")
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sz 1000100
ll dp[102][sz];
int w[102];
int v[102];
int main()
{
    int n, W;
    scanf("%d", &n); scanf("%d", &W);
    for (int j = 0; j < sz; ++j)
    {
        dp[0][j] = INT_MAX;
    }
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &w[i]);
        scanf("%d", &v[i]);
    }
    dp[0][0] = 0;
    dp[0][v[0]] = w[0];
// by taking/not taking ith item min possible wieght to obtain value v
    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j < sz; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (v[i] <= j)
                dp[i][j] = min(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
        }
    }
    int mx = 0;
    for (int i = 0; i < sz; i++)
    {
        if (dp[n - 1][i] <= W)
            mx = i;
    }
    cout << mx;
    return 0;
}

Measured memory_bytes: 782592
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main() {
	char w[11] = { 0 };
	char p[1000] = { 0 };
	int cnt = 0;
	int i;

	scanf("%s", w);

	while (1) {
		scanf("%s", p);

		if (strcmp(p, "END_OF_TEXT") == 0) {
			break;
		}

		for (i = 0; p[i] != '\0'; i++) {
			p[i] = tolower(p[i]);
		}

		if (strcmp(p, w) == 0) {
			cnt++;
		}
	}

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

	return 0;
}


Measured memory_bytes: 2104
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int i,j,n,m=0,minj,x;
  int *a;

  scanf("%d",&n);
  a = (int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++) scanf("%d",&a[i]);

  for(i=0;i<n;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(a[j] < a[minj]) minj = j;
    }
    x = a[i];
    a[i] = a[minj];
    a[minj] = x;
    if(a[minj] != a[i]) m++;
  }
  
  for(i=0;i<n;i++){
    if(i > 0) printf(" ");
    printf("%d",a[i]);
  }
  printf("\n");
  printf("%d\n",m);
  free(a);
  return 0;
}

Measured memory_bytes: 604
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	n = readline() |> parseInt
	p = readline() |> split |> parseMap
	k = 0
	for i in 1:n-1
		if p[i]==i
			p[i+1] = i
			p[i] = i+1
			k += 1
		end
	end
	if p[n] == n
		k += 1
	end
	println(k)
end
main()


Measured memory_bytes: 116876
#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,m;
  cin>>n>>m;  //入力
  vector<ll> broken(n + 1);  //壊れた段を記録する配列
   rep(i,m){
    ll a;
     cin>>a;
    broken[a]++;
 } //壊れた段を1として記録
  vector<ll> dp(n+1); //DP配列
    dp[1]=1; dp[2]=2;   //1、2段目が壊れていないときの初期条件
if(broken[1]!=0){
  dp[1]=0;
  dp[2]=1;
}  //1段目が壊れているときの初期条件
if(broken[2]!=0) dp[2]=0; //2段目が壊れているときの初期条件
  rep2(i,3,n+1){
   if(broken[i]==0) dp[i]=dp[i-1]%MOD+dp[i-2]%MOD;
else dp[i]=0;
    } //3段目以降DPをする
    cout<<dp[n]%MOD<<endl;  //出力
  return 0;
}


Measured memory_bytes: 1792
N = int(input())
V = list(map(int, input().split()))

dict_odd = dict()
dict_even = dict()

for i in range(N):
	if i % 2 == 1:
		if V[i] in dict_odd:
			dict_odd[V[i]] += 1
		else:
			dict_odd[V[i]] = 1
			
	else:
		if V[i] in dict_even:
			dict_even[V[i]] += 1
		else:
			dict_even[V[i]] = 1
			
odd_sorted = sorted(dict_odd.items(), key=lambda x:x[1], reverse = True)
even_sorted = sorted(dict_even.items(), key=lambda x:x[1], reverse = True)

if odd_sorted[0][0] != even_sorted[0][0]:
	print(N - odd_sorted[0][1] - even_sorted[0][1])
else:
	if len(odd_sorted) == 1 and len(even_sorted) == 1:
		print(int(N / 2))
	elif len(odd_sorted) == 1:
		print(N - odd_sorted[0][1] - even_sorted[1][1])
	elif len(even_sorted) == 1:
		print(N - even_sorted[0][1] - odd_sorted[1][1])
	else:
		print(N - max(odd_sorted[0][1] + even_sorted[1][1], odd_sorted[1][1] + even_sorted[0][1]))

Measured memory_bytes: 63852
function main(input){
    num = parseInt(input);
    sum = 0;
    for(i=0;i<=num;i++){
        if(i%3!=0 && i%5!=0){
            sum=sum+i;
        }
    }

    console.log(sum);

}

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

Measured memory_bytes: 35184
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;
//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}









int main()
{
     int n;
     cin>>n;
     vector<pi> vec(n);
     for(int i=0;i<n;i++){
         ll x,y;
         cin>>x>>y;
         vec[i].fi=x+y;
         vec[i].se=x-y;
     }
     sort(vec.begin(),vec.end());
     ll cur=-1LL<<60;
     int ans=0;
     for(int i=0;i<n;i++){
          if(vec[i].se>=cur){
               ans++;
               cur=vec[i].fi;
          }
     }
     cout<<ans;



}
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
#define fir first
#define sec second
typedef long long ll;
////////////////////////////////////////////////////////////

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

	vector<pair<int,int>> v;
	rep(i,0,m){
		int a,b;
		cin >> a >> b;
		a--; b--;
		v.push_back( pair<int,int> (b,a) );
	}

	vsort(v);

	//rep(i,0,m) cout << v[i].fir << " " << v[i].sec << endl;

	int cnt = 1;
	int x = v[0].fir;


	rep(i,1,m){
		//cout << "x:"<< x << " " << "v:"<<v[i].sec << endl;
		if( x <= v[i].sec ){
			x = v[i].fir;
			cnt++;
		}
	}

	cout << cnt << endl;

	ret 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define mp(x, y) make_pair(x, y)
#define F first
#define S second
using namespace std;
const ll mod = 998244353;
ll n, q, pw[800005], p[800005], t[800005], la[800005];
ll comb(ll x, ll y) { return (x + y + mod * 1000LL) % mod; }
ll get(ll l, ll r) { return (p[r] - p[l - 1] + mod * 1000LL) % mod; }
void push(int v, int l, int r) {
  if (la[v]) {
    if (l != r) la[v + v] = la[v], la[v + v + 1] = la[v];
    t[v] = (la[v] * get(l, r)) % mod;
    la[v] = 0;
  }
}
void upd(int v, int l, int r, int x, int y, int z) {
  push(v, l, r);
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
    la[v] = z;
    push(v, l, r);
    return;
  }
  int tm = (l + r) / 2;
  upd(v + v, l, tm, x, y, z);
  upd(v + v + 1, tm + 1, r, x, y, z);
  t[v] = comb(t[v + v], t[v + v + 1]);
}
int get(int v, int l, int r, int x, int y) {
  push(v, l, r);
  if (r < x || y < l) return 0;
  if (x <= l && r <= y) return t[v];
  int tm = (l + r) / 2;
  return comb(get(v + v, l, tm, x, y), get(v + v + 1, tm + 1, r, x, y));
}
int main() {
  speed;
  oprecision;
  // code
  cin >> n >> q;
  pw[1] = p[1] = 1;
  for (int i = 2; i <= n; i++)
    pw[i] = (pw[i - 1] * 10LL) % mod, p[i] = (p[i - 1] + pw[i]) % mod;
  upd(1, 1, n, 1, n, 1);
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    l = n - l + 1, r = n - r + 1;
    upd(1, 1, n, r, l, x);
    cout << get(1, 1, n, 1, n) << "\n";
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 15016
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N;cin>>N;
	int W[N];
	int temp=0;int sum[N];
	for(int i=0;i<N;i++){
		cin>>W[i];
		temp+=W[i];
		sum[i]=temp;
	}
	int ans=sum[N-1];
	for(int i=0;i<N;i++){
		ans=min(ans,abs(sum[N-1]-2*sum[i]));
	}cout<<ans<<endl;
}

Measured memory_bytes: 256
object Main extends App {
  
  val sc = new java.util.Scanner(System.in)
  val n, a, b = sc.nextInt()
  var  ans = 0
  for (i <- 1 to n) {
    val sum = i.toString.toList.foldLeft(0)((x, y) => x + y.asDigit)
    if (a <= sum && sum <= b) {
      ans += i
    }
  }
  println(ans)
}

Measured memory_bytes: 55456
n = int(input())
a = [int(i) for i in input().split()]

# print(n)
# print(a)

b = sorted(a, reverse=True)
# print(b)

flag = False

i = 0

tate = 0
yoko = 0
# for i in range(n-1):
while i < n - 1:
    # print(i)
    if b[i] == b[i+1]:
        # print('test1')
        if flag:
            yoko = b[i]
            # print('test2')
            break
        else:
            tate = b[i]
            flag = True
            i += 1
            # print('test3')
    i += 1

print(tate*yoko)


Measured memory_bytes: 14252
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

md = 998244353

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,m,k=MI()
    ans=mint(0)
    for i in range(k+1):
        ans+=m*pow(m-1,n-1-i,md)*nCr(n-1,i)
    print(ans)

main()

Measured memory_bytes: 88356
#include<stdio.h>
#define N 101


int main(){
  int i,j,k,l,m,n;
  int a[N][N];

  scanf("%d",&n);
  
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      a[i][j]=0;


  for(i=0;i<n;i++){
    scanf("%d %d",&m,&k);
    for(j=0;j<k;j++){
    scanf("%d",&l);
    a[m-1][l-1]=1;
    }
  }
  
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      printf("%d",a[i][j]);
      if(j!=n-1)printf(" ");
    }
    printf("\n");
  }

  return 0;
}

    



Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s[20];
	cin>>s;
	int k=strlen(s),ans=15-k;
	for(int i=0;i<k;i++)ans+=(s[i]=='o');
	cout<<(ans>=8?"YES":"NO")<<'\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main()
{
	int n;
	cin>>n;
	long long ans=1;
	for(int i=1;i<=n;i++)
		ans=(ans*i)%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;

class Dice{
    int[] sides = new int[6];
    int j = 0;

    Dice(int[] sides){
        this.sides = sides;
    }

    void N(){
        int tmp = sides[0];
        sides[0] = sides[1];
        sides[1] = sides[5];
        sides[5] = sides[4];
        sides[4] = tmp;
    }

    void S(){
        int tmp = sides[0];
        sides[0] = sides[4];
        sides[4] = sides[5];
        sides[5] = sides[1];
        sides[1] = tmp;
    }

    void W(){
        int tmp = sides[0];
        sides[0] = sides[2];
        sides[2] = sides[5];
        sides[5] = sides[3];
        sides[3] = tmp;
    }

    void E(){
        int tmp = sides[0];
        sides[0] = sides[3];
        sides[3] = sides[5];
        sides[5] = sides[2];
        sides[2] = tmp;
    }

    int getSide(int i){
        return sides[i];
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        char[] order = br.readLine().toCharArray();
        int[] sides = new int[6];

        for(int i = 0; i < 6; i++){
            sides[i] = Integer.parseInt(str[i]);
        }

        Dice dice = new Dice(sides);

        for(char c : order){
            switch (c){
                case 'N':
                    dice.N();
                    break;
                case 'S':
                    dice.S();
                    break;
                case 'E':
                    dice.E();
                    break;
                case 'W':
                    dice.W();
                    break;
                default:
                    break;
            }
        }
        System.out.println(dice.getSide(0));
    }
}

Measured memory_bytes: 24236
#include <stdio.h>
  void factorial(long long n){
  long i;
  long long sum=1;

  for(i=1;i<=n;i++){
    sum=sum*i;
  }
    printf("%lld\n",sum);




  }
int main()
{


    long long n;
    while(scanf("%lld",&n)==1){



    factorial(n);

    }
    return 0;
}

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

using namespace std;
typedef long long ll;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<ll> f(n + 1);
    vector<ll> sum(n + 1);
    vector<int> l(k), r(k);
    const ll M = 998244353ll;
    for(int i = 0; i < k; ++i)
        cin >> l[i] >> r[i];
    f[1] = 1;
    sum[1] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j = 0; j < k; ++j){
            if(i - l[j] <= 0)
                continue;
            if(i - r[j] <= 0){
                f[i] = (f[i] + sum[i - l[j]]) % M;
                continue;
            }
            f[i] = (f[i] + sum[i - l[j]] - sum[i - r[j] - 1] + M) % M;
        }
        sum[i] = (f[i] + sum[i - 1]) % M;
    }
    cout << f[n] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 6364
# Multiple of 9


def main(n):
    s = 0
    for u in list(n):
        s += int(u)
        if 8 < s:
            s = s % 9
    return s == 0


N = input().strip()
result = main(N)
if result:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 10316
n, k = map(int, input().split())
a = list(map(int, input().split()))
cumsum = [0]
cumsum_pos = [0]
for i in range(n):
	cumsum.append(cumsum[-1] + a[i])
	cumsum_pos.append(cumsum_pos[-1] + max(0, a[i]))
def range_sum(l, r):
	if l > r:
		return 0
	else:
		return cumsum[r + 1] - cumsum[l]
def range_pos(l, r):
	if l > r:
		return 0
	else:
		return cumsum_pos[r + 1] - cumsum_pos[l]

ans = -float("inf")

for i in range(n - k + 1):
	ans = max(ans, range_sum(i, i + k - 1) + range_pos(0, i - 1) + range_pos(i + k, n - 1), range_pos(0, i - 1) + range_pos(i + k, n - 1))

print(ans)

Measured memory_bytes: 17508
x, y = list(map(int, input().split()))

A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
C = [2]

if (x in A and y in A) or (x in B and y in B) or (x in C and y in C):
    print('Yes')
else:
    print('No')


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

using namespace std;

int main() {
	int n; cin >> n;
	vector<int> a(n);
	for(auto&e:a) cin >> e;
	sort(a.begin(),a.end());
	long long ans=n,sum=a[0];
	for(int i=1;i<n;++i) {
		if(2*sum<a[i]) ans=n-i;
		sum+=a[i];
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

#define PI acos(-1)
typedef long long ll;
#define INF 0x3f3f3f3f
int mod = 1000000007;
char s1[55], s2[55];
int main()
{
	//freopen("in.txt", "r", stdin);
	string f = "UNRESTORABLE";
	while (~scanf("%s%s", s1, s2))
	{
		int l1 = strlen(s1);
		int l2 = strlen(s2);
		for (int i = l1 - l2; i >= 0; i--)
		{
			bool flag = true;
			for (int j = 0; j < l2; j++)
				if (s1[i+j] == '?')
					continue;
				else if (s1[i+j] == s2[j])
					continue;
				else
				{
					flag = false;
					break;
				}
			if (flag)
			{
				for (int j = 0; j < l1; j++)
					if (j >= i && j < i + l2)
						s1[j] = s2[j-i];
					else if (s1[j] == '?')
						s1[j] = 'a';
				puts(s1);
				return 0;
			}
		}
		cout<<f<<endl;
	}
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<utility>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, a,b) for(i=a;i<b;i++) 
#define REP1(i,b,a) for(i=b-1;i>=a;i--)
#define output(x) cout<<x<<endl;
#define pb(x) push_back(x);
typedef long long int ll;
const int MAX = 510000;
const int MOD = 1000000007;

int main()
{

	ll i, j, k, l, m, flag, N, M, K, H, W, X, P;
	cin >> N;
	//エラトステネスの篩で素数をnまで列挙
	ll n = 150;

	ll prime[200] = {};
	bool is_prime[200];
	ll primecc[200] = {};//i番目の素数を何個素因数に持つか
	for (i = 0; i <= n; i++) {
		is_prime[i] = true;
	}
	int p = 0;
	is_prime[0] = is_prime[1] = false;
	for (i = 2; i <= n; i++) {
		if (is_prime[i]) {
			prime[p++] = i;
			for (j = 2 * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	//ここからPの素因数分解
	for (P = 2; P <= N; P++) {
		k = 0;
		ll temp;
		for (i = 0; prime[i] <= P; i++) {
			temp = P;
			while (P%prime[i] == 0) {
				P /= prime[i];
				primecc[i]++;
			}
			P = temp;
		}
	}
	ll ans = 0;
	ll cc24, cc2, cc4, cc14;
	cc24 = 0;
	cc2 = 0;
	cc4 = cc14 = 0;
	for (i = 0;prime[i]<=N; i++) {
		if (primecc[i] >= 74) {
			ans++;
		}
		if (primecc[i] >= 24) {
			cc24++;
		}
		if (primecc[i] >= 14) {
			cc14++;
		}
		if (primecc[i] >= 4) {
			cc4++;
		}
		if (primecc[i] >= 2) {
			cc2++;
		}
	}

  
	ans += cc24 * (cc2 - 1)+cc14*(cc4-1)+((cc4*(cc4-1))/2*(cc2-2));
	output(ans);
  
	return 0;
}





Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>

int main(void){
  int i,j,k;
  char str[82];
  int len;
  int tmp;
  int sum;

  sum = 0;
  while(fscanf(stdin,"%s ",str)!=EOF){
    len = strlen(str);
    for(i=0;i<len;i++){
      tmp = str[i] - '0';
      if( tmp >= 0 && tmp < 10 ){
	j = 0;
	do{
	  j++;
	  tmp = str[i+j] - '0';
	}while( tmp >=0 && tmp < 10 );
	
	for(k=0;k<j;k++){
	  sum += (str[i+k] - '0') * pow(10,j-k-1);
	}
	i+=j;
      }
    }
  }

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

  return 0;
}

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

using namespace std;

int main() {
	int K, A, B;
	cin >> K >> A >> B;
	bool ok = false;
	for (int i = A; i <= B; i++) {
		if (i % K == 0) {
			ok = true;
			break;
		}
	}
	if (ok) cout << "OK" << endl;
	else cout << "NG" << endl;

	return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

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

int main(void)
{
    int k;
    cin >>k;

    long long sum = 0;

    for(int a = 1; a <= k; a++){
        for(int b = 1; b <= k; b++){
            for(int c = 1; c <= k; c++){
                int g = gcd(a,b);
                g = gcd(g,c);
                sum += g;
            }
        }
    }

    printf("%lld\n", sum);
    return 0;
}

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

int main()
{
  	string a;
  	cin>>a;
  	int m[26] = {0};
  	for(int i = 0; i < a.size(); i++)
    {
    	m[a[i]-'a']++;
    }
  	bool flag = true;
  	for(int i = 0; i < 26; i++)
    {
    	if(m[i] % 2 != 0)
        {
          	flag = false;
          	break;
        }
    }
  	if(flag == true)
      	cout<<"Yes\n";
  	else
      	cout<<"No\n";
	return 0;
}

Measured memory_bytes: 256
/*input
32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9
*/

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long int ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define fi first
#define se second
#define INF    1<<30
#define NEGINF -(1<<30)
#define LINF   1<<60
#define EPS 1e-10
#define PI 2 * acos(0)
#define NULO -1
#define endl '\n'

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int cmp(double x, double y = 0, double tol = EPS){ return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1; }

ll fat[112345], inv[112345];
ll a[112345],cont=0;
bool cnt[112345];

void fatorial() {
        fat[0] = 1;
        for (int i = 1; i < 112345; i ++) fat[i] = fat[i - 1] * i % mod;
}

void inv_multiplicativo(){
	for(int i=0;i<112345;i++){
		inv[i] = powmod(fat[i], mod-2)%mod;
	}
}

ll coeficiente_binominal(ll n, ll k){
	if(n<k) return 0;

	return fat[n]*(inv[k]*inv[n-k]%mod)%mod; 
}

int main(){
	fatorial();
	inv_multiplicativo();
	ll n,d,v;
	//puts("YES");
	memset(cnt,0,sizeof cnt);
	scanf("%lld",&n);
	rep(i,0,n+1){
		scanf("%lld",&a[i]);
		if(cnt[a[i]]==1) v=a[i];
		cnt[a[i]]++;
	}
	bool fi=0;
	rep(i,0,n+1){
		if(fi&&a[i]==v){
			d = i - d;
			break;
		}
		if(a[i]==v){
			d=i;
			fi=1;
		}
	}
	rep(i,1,n+2){
		ll ans = coeficiente_binominal(n+1,i);
		ans-= coeficiente_binominal(n-d,i-1);
		if(ans<0) ans+=mod;
		printf("%lld\n",ans);
	}
return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <tuple>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
constexpr ll INF = 1000000007;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if ((a + b + c) >= 22) {
		cout << "bust" << endl;
	}
	else {
		cout << "win" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4

int main(){
  int N,M; cin >> N >> M;
  int k[M], s[M][N], p[M];

  rep(i,M){
    cin >> k[i];
    rep(j,k[i]) cin >> s[i][j];
  }
  rep(i,M) cin >> p[i];

  int retval = 0;
  for (int tmp=0;tmp<(1<<N);tmp++){
    bitset<10> S(tmp);
    bool flag = true;
    
    rep(i,M){ //電球についての探索
      int cnt = 0;
      rep(j,k[i]) cnt += S.test(s[i][j]-1);

      if (cnt%2!=p[i]) {
        flag = false;
        break;
      }
    }

    if (flag) retval++;

  }

  cout << retval << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

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

    vector<int> k(M);
    vector<vector<int>> s(M);
    REP(i,M) {
        cin>>k[i];
        s[i].resize(k[i]);
        REP(j, k[i]){
            cin>>s[i][j];
            s[i][j]--;
        }
    }
    vector<int> p(M);
    REP(i, M) cin>>p[i];

    //スイッチ
    int cnt_total=0;
    for(int bit=0; bit<(1<<N); bit++){
        //cout<<bitset<2>(bit)<<": ";
        //電球
        bool flg = true;
        REP(m,M){
          	//cout<<m<<"> ";
            int cnt=0;
            for(auto x:s[m]){
              	//cout<<x<<" ";
                if(bit&1<<x) cnt++;
            }
          	//cout<< "[cnt:"<<cnt<<"] ";
            if(cnt%2!=p[m]){
                flg=false;
                break;
            }
        }
      	//cout<<endl;
        if(flg) cnt_total++;
    }

    cout << cnt_total << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  string s, t;
  cin >> s >> t;

  int N = s.size();
  int M = t.size();
  
  int ans = INF;
  REP(i, N-M+1){
    int ret = 0;
    REP(j, M){
      if(s[i+j] != t[j]) ret++;
    }

    chmin(ans, ret);
  }

  cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
    }
    
    int cnt = 0;
    int flag = 1;
    while ( flag ) {
        flag = 0;
        for (int j = N-1; j > 0; j-- ) {
            if ( A[j] < A[j-1] ) {
                int t = A[j];
                A[j] = A[j-1];
                A[j-1] = t;
                flag = 1;
                cnt++;
            }
        }
    }
    
    for ( int i = 0; i < N; i++ ) {
        cout << (i!=0 ? " " : "") << A[i];
    }
    cout << '\n';
    cout << cnt << '\n';
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

const int MAX_N = 1e6;

struct UnionFind{
    int N;
    int par[MAX_N];

    UnionFind(int N): N(N){
        for (int i=0;i<N;i++){
            par[i] = i;
        }
    }

    int root(int x){
        if(par[x] == x) return x;
        int rx = root(par[x]);
        par[x] = rx;
        return rx;
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx==ry) return;
        par[rx] = ry;
    }

    bool find(int x, int y){
        return root(x) == root(y);
    }
};

int main(){
	ll N, M;
	cin >> N >> M;
	UnionFind uf(N);
	vector<ll> moto(M, -1);
	REP(i, N){
		ll K;
		cin >> K;
		REP(j, K){
			ll L;
			cin >> L;
			L--;
			if(moto[L]==-1){
				moto[L] = i;
			}else{
				uf.unite(moto[L], i);
			}
		}
	}
	bool flag = true;
	REP(i, N-1) if(uf.root(N-1)!=uf.root(i)) flag = false;
	cout << (flag?"YES":"NO") << endl;
    return 0;
}

Measured memory_bytes: 4224
#include <iostream>
#include <sstream>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define max 251
#define nil 2000000001
int h[max];

void print(int n){
  for(int i=0;i<n;i++){
    cout<<"node "<<i+1
	<<": key = "<<h[i]<<", ";
    if(i!=0)cout<<"parent key = "<<h[(i-1)/2]<<", ";
    if(i*2+1<n)cout<<"left key = "<<h[i*2+1]<<", ";
    if((i+1)*2<n)cout<<"right key = "<<h[(i+1)*2]<<", ";
    cout<<endl;
  }
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++)cin>>h[i];
  print(n);
  return 0;
}



Measured memory_bytes: 3092
package main

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

var sc = bufio.NewScanner(os.Stdin)
var X []float64
var Y []float64

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanFloat() float64 {
	return float64(scanInt())
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func Permute(nums []int) [][]int {
	n := factorial(len(nums))
	ret := make([][]int, 0, n)
	permute(nums, &ret)
	return ret
}

func permute(nums []int, ret *[][]int) {
	*ret = append(*ret, makeCopy(nums))

	n := len(nums)
	p := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		p[i] = i
	}
	for i := 1; i < n; {
		p[i]--
		j := 0
		if i%2 == 1 {
			j = p[i]
		}

		nums[i], nums[j] = nums[j], nums[i]
		*ret = append(*ret, makeCopy(nums))
		for i = 1; p[i] == 0; i++ {
			p[i] = i
		}
	}
}

func factorial(n int) int {
	ret := 1
	for i := 2; i <= n; i++ {
		ret *= i
	}
	return ret
}

func makeCopy(nums []int) []int {
	return append([]int{}, nums...)
}

func calDist(from, to int) float64 {
	x := math.Pow(X[from]-X[to], 2)
	y := math.Pow(Y[from]-Y[to], 2)
	return math.Sqrt(x + y)
}

func main() {
	n := scanInt()
	t := make([]int, n)
	X = make([]float64, n)
	Y = make([]float64, n)
	for i := range t {
		t[i] = i
		X[i] = scanFloat()
		Y[i] = scanFloat()
	}

	total := 0.0
	cnt := 0.0
	for _, towns := range Permute(t) {
		cnt += 1
		from := towns[0]
		for i := 1; i < n; i++ {
			to := towns[i]
			total += calDist(from, to)
			from = to
		}
	}
	fmt.Println(total / cnt)
}


Measured memory_bytes: 4224
package main

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

func main() {
	var ww map[string]int
	ww = make(map[string]int)
	N := oneInt()
	for index := 0; index < N; index++ {
		ww[oneStr()]++
	}

	var ss sortable
	for k, v := range ww {
		ss = append(ss, kv{k, v})
	}
	sort.Sort(ss)

	var forSort []string

	max := ss[0].Value
	for _, kv := range ss {
		if max == kv.Value {
			forSort = append(forSort, kv.Key)
		}
	}

	sort.Strings(forSort)
	for _, s := range forSort {
		fmt.Println(s)
	}

}

type kv struct {
	Key   string
	Value int
}

type sortable []kv

func (a sortable) Len() int           { return len(a) }
func (a sortable) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a sortable) Less(i, j int) bool { return a[i].Value > a[j].Value }

func exp(val int) float64 {
	var temp float64
	for index := 1; index <= val; index++ {
		temp += float64(index)
	}
	return temp / float64(val)
}

func searchAbove(slice []int, target int, index int) int {
	for i := index + 1; i < len(slice); i++ {
		v := slice[i]
		if v >= target {
			return i
		}
	}
	return -1
}

var sc = bufio.NewScanner(os.Stdin)

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}
func oneStr() string {
	var a string
	fmt.Scan(&a)
	return a
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func scanNums() (nums []int) {
	s := nextLine()
	numStr := strings.Split(s, " ")

	for _, n := range numStr {
		i, _ := strconv.Atoi(n)
		nums = append(nums, i)
	}
	return nums
}

func scanStrings() (strs []string) {
	s := nextLine()
	list := strings.Split(s, " ")
	strs = append(strs, list...)
	return strs
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func sortAsc(a []int) []int {
	sort.Ints(a)
	return a
}

func sortDesc(a []int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	if a == 0 && b == 0 {
		return 0
	}
	return a * b / gcd(a, b)
}


Measured memory_bytes: 41872
#include <cstdio>
#include <string>

#define MAXN 100007

int mayRed[MAXN];
int numOfBall[MAXN];

int main()
{
    int N,M;
    int i,x,y;
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)
    {
        numOfBall[i]=1;
        mayRed[i]=0;
    }
    mayRed[1]=1;
    for(i=0;i<M;i++)
    {
        scanf("%d%d",&x,&y);
        if(mayRed[x])
        {
            mayRed[y]=1;
        }
        numOfBall[x]-=1;
        numOfBall[y]+=1;
        if(numOfBall[x]==0)
        {
            mayRed[x]=0;
        }
    }
    int r = 0;
    for(i=1;i<=N;i++)
    {
        r+=mayRed[i];
    }
    printf("%d\n",r);
    return 0;
}

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

int main() {
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int dx = x2 - x1, dy = y2 - y1;
  cout << x2 - dy << " " << y2 + dx << " " << x1 - dy << " " << y1 + dx << endl;
}


Measured memory_bytes: 256
#親要素を示す
par = {}
sum_union = {}
len_union = {}

# 初期化 -- すべての要素が根である --
def init(n):
  for i in range(n):
    par[i] = i
    sum_union[i] = Cs[i]
    len_union[i] = 1
  return 
  
# 根を求める
def root(x):
  if par[x] == x:
    return x
  else:
    #根の直下にxを置く
    par[x] = root(par[x])
    return par[x]

#　同じ集合に属するかどうかは根が同じかで判定
def same(x, y):
  return root(x) == root(y)

#　別々のUnion同士を融合する
def unite(x, y):
  rx = root(x)
  ry = root(y)
  if rx == ry:
    return
  else:
    par[rx] = ry
    tmp_sum = sum_union[rx] + sum_union[ry]
    tmp_len = len_union[rx] + len_union[ry]
    sum_union[ry] = tmp_sum
    len_union[ry] = tmp_len
    return
  
N, K = map(int, input().split())
Ps = list(map(lambda x: int(x) - 1, input().split()))
Cs = list(map(int, input().split()))


init(N)

# 結合
for i in range(N):
  unite(i, Ps[i])
  
max_result = -(10**9+1)
for i in range(N):
  ri = root(i)
  if sum_union[ri] <= 0:
    partial_range = min(K, len_union[ri])
    roop_sum = 0
  elif K < len_union[ri]:
    partial_range = K
    roop_sum = 0
  else:
    partial_range = (K % len_union[ri]) + len_union[ri]
    roop_sum = sum_union[ri] * ((K // len_union[ri])-1)
  pc = i
  sum_list = []
  sum_c = 0
  for _ in range(partial_range):
    pn = Ps[pc]
    sum_c += Cs[pn]
    sum_list.append(sum_c)
    pc = pn
    
  max_result = max(max_result, roop_sum + max(sum_list))
  
print(max_result)
  




Measured memory_bytes: 110936