akhauriyash/Code-Regression huggingface dataset:
let make_list f t step =
  let rec make_list_inner c t lst =
    if c >= t then lst else make_list_inner (c+step) t (c::lst)
  in
  List.rev (make_list_inner f t [])

type side = Left | Right | On

let side x1 y1 x2 y2 px py =
  match px *. (y1 -. y2) +. x1 *. (y2 -. py) +. x2 *. (py -. y1) with
    x when x > 0.0 -> Left
  | x when x < 0.0 -> Right
  | _ -> On

let inside_triangle x1 y1 x2 y2 x3 y3 px py =
  let s1 = side x1 y1 x2 y2 px py
  and s2 = side x2 y2 x3 y3 px py
  and s3 = side x3 y3 x1 y1 px py
  in
  s1 = s2 && s2 = s3 && s1 <> On
    
let () =
  let rec read () =
    try let ans = (Scanf.scanf "%f %f %f %f %f %f %f %f\n" inside_triangle) in
        Printf.printf "%s\n" (if ans then "YES" else "NO");
        read ()
    with End_of_file ->
         ()
  in
  read ()
;;

Measured memory_bytes: 2436
#include <iostream>
#include<vector>
using namespace std;
#define ll long long
ll frog1(ll d[],ll b){
    //if b==0 no steps to jump
    if(b<=1)
    return 0;
    
    //he may jump 1 or 2 steps
    //with minimum cosst
      int p=abs(d[b-1]-d[b-2])+frog1(d,b-1);
      int r=(b<=2)? 10000:abs(d[b-1]-d[b-3])+frog1(d,b-2);
     return min(p,r);
}
ll frog(ll d[],ll b){
    //if b==0 no steps to jump
    ll dp[b+1];
    //he may jump 1 or 2 steps
    //with minimum cost
    dp[1]=0;
    for(int i=2;i<=b;i++){
      int p=abs(d[i]-d[i-1])+dp[i-1];
      int r=(i==2)? 1000000:abs(d[i]-d[i-2])+dp[i-2];
     dp[i]= min(p,r);
    // cout<<dp[i]<<" ";
    }
     return dp[b];
     
}
int main(){
    ll b;
	    cin>>b;
	    ll d[b];
	    for(ll i=1;i<=b;i++)
	    cin>>d[i];
	    cout<<frog(d,b)<<endl;
	
	return 0;
}

Measured memory_bytes: 1792
//https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
    ll N; cin>>N;
    ll x=(double)N/1.08;
    ll x2=x+1;

    ll tmp=(double)x*1.08;
    ll tmp2=(double)x2*1.08;
    dump(tmp,tmp2);

    if(tmp==N){
        cout<<x<<endl;
    }else if(tmp2==N){
        cout<<x2<<endl;
    }else{
        cout<<":("<<endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(c) (c).begin(), (c).end()
const int INF = 1e9 + 1;
const ll LINF = 1e18 + 1;
const ll MOD = 1e9 + 7;

template <class T>
T fast_pow(T n, int exp) {
  T ret = 1, mul = n;
  while (exp > 0) {
    if (exp & 1) ret *= mul;
    mul *= mul;
    exp /= 2;
  }
  return ret;
}

class modint {
 public:
  ll n;
  int mod = MOD;

  modint(const ll x = 0) noexcept : n(x) {}
  modint inverse() { return fast_pow(*this, mod - 2); }
  modint& operator+=(const modint a) {
    n += a.n;
    n %= mod;
    return *this;
  }
  modint operator+(const modint a) { return modint(*this) += a; }
  modint& operator-=(const modint a) {
    n += (mod - a.n);
    n %= mod;
    return *this;
  }
  modint operator-(const modint a) { return modint(*this) -= a; }
  modint& operator*=(const modint a) {
    n *= a.n;
    n %= mod;
    return *this;
  }
  modint operator*(const modint a) { return modint(*this) *= a; }
  modint& operator/=(modint a) { return (*this) *= a.inverse(); }
  modint operator/(const modint a) { return modint(*this) /= a; }
};
ostream& operator<<(ostream& o, const modint& m) {
  o << m.n;
  return o;
}

int N;
vector<int> size;
vector<vector<int>> G;
modint E_edges = 0;

void dfs(int v, int p) {
  for (auto u : G[v]) {
    if (u == p) continue;
    dfs(u, v);
    size[v] += size[u];
  }
}

void dfs2(int v, int p) {
  for (auto u : G[v]) {
    if (u == p) continue;
    dfs2(u, v);
    modint one = 1;
    int x = size[u];
    E_edges += (one - fast_pow(one / 2, x)) * (one - fast_pow(one / 2, N - x));
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N;

  G.resize(N);
  size.resize(N, 1);

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

  dfs(0, -1);
  dfs2(0, -1);

  modint E_nodes = E_edges + 1 - fast_pow(modint(1) / 2, N);
  modint ans = E_nodes - modint(N) / 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 20864
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n, m;
int s[10000];
int t[10000];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<m;i++)cin>>t[i];
    ll dp[n+1][m+1];
    for(int i=0;i<n+1;i++){
        for(int j=0;j<m+1;j++){
            dp[i][j]=1;//空集合
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD;//ダブルカウントを引く
            if(s[i-1]==t[j-1])dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD; //i-1,j-1の分だけ増える(部分列にs[i]とt[j]を加える)
            if(dp[i][j]<0)dp[i][j]+=MOD;
        }
    }


    cout <<dp[n][m] << "\n";
}

Measured memory_bytes: 31616
import           Control.Monad
import           Control.Applicative
import           Data.IORef
import           Data.List.Split
import           Data.Maybe
import           Data.List

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine
  img    <- replicateM n getLine
  timg   <- replicateM m getLine

  putStrLn $ if solve n m img timg then "Yes" else "No"

solve :: Int -> Int -> [String] -> [String] -> Bool
solve n m img timg
  | n < m
  = False
  | otherwise
  = isInfixOf timg (map (take m . drop (n - m)) img)
    || solve (n - 1) m img timg

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

int n,dp[3][111],in[3][111];

int rec(int r,int c)
{
    if(r>2 || c>n) return 0;
    int &ret=dp[r][c];
    if(ret!=-1) return ret;
    ret=0;
    ret=max(ret,rec(r+1,c));
    ret=max(ret,rec(r,c+1));
    return ret=ret+in[r][c];
}

int main()
{
    cin >> n;
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=n; j++) cin >> in[i][j];
    }
    memset(dp,-1,sizeof dp);
    cout<<rec(1,1)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1, (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

class Tree{
private:
    int N;
    vector<vector<int>> depth;
    map<int,vector<int>> mp;
    pair<int,int> counter;

public:
    Tree(int n) : N(n), depth(2, vector<int>(n,0)), counter({0,0}){}

    void setlist(int a, int b){
        mp[a].push_back(b);
    }

    void dfs(int var, int par, int cost, int pl){
        depth[pl][var] = cost;
        for(auto i : mp[var]){
            if(i == par){
                continue;
            }
            dfs(i, var, cost + 1, pl);
        }
    }

    string result(){
        for(int i=0; i<N; i++){
            if(depth[0][i] <= depth[1][i]){
                counter.first++;
            }else{
                counter.second++;
            }
        }
        if(counter.first > counter.second){
            return "Fennec";
        }else{
            return "Snuke";
        }
    }

};

int main(){
    int n;
    cin >> n;
    Tree t(n);

    REP(i, n-1){
        int a, b;
        cin >> a >> b;
        t.setlist(a-1, b-1);
        t.setlist(b-1, a-1);
    }

    t.dfs(0, -1, 0, 0);
    t.dfs(n-1, -1, 0, 1);

    cout << t.result() << endl;

    return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll N, A,B;
ll i,j,ans;
int main(){
    scanf("%lld%lld%lld", &N,&A,&B);
    printf("%lld", B < A * N ? B : A * N);

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer[] ary = new Integer[n];
        int ans = 0;
        int sum = 0;
        for(int i = 0;i<n;i++){
            ary[i]=sc.nextInt();
            sum += ary[i];
        }
        Arrays.sort(ary,Collections.reverseOrder());
        if(sum%(4*m)==0){
            sum = sum/(4*m);
        } else {
            sum = sum/(4*m)+1;
        }
        for(int i = 0;i<m;i++){
            if(ary[i]>=sum){
                ans ++;
            }
        }
        if (ans>=m){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
	}
}

Measured memory_bytes: 23764
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 100005
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct st{
	int to,nxt;
}e[MN<<1];
int head[MN],a[MN],st[MN],f[MN],ind[MN],fa[MN];
int cnt=0,num=0,top,n,x,y,rt,ans;
bool mk;
inline void ins(int x,int y){
	e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}
inline bool chk(int u,int x,int tp){
	int hd=1,tl=tp;
	if (u==hd) ++hd;if (u==tl) --tl;
	while (hd<tl){
		if (st[hd]+st[tl]>x) return 0;++hd;--tl;
		if (u==hd) ++hd;if (u==tl) --tl;
	}return 1;
}
inline void dfs(int u,int x){
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (v!=fa[u]) fa[v]=u,dfs(v,x);
	}top=0;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (v!=fa[u]) st[++top]=f[v];
	}if (!top) {f[u]=1;return;}
	if (!(top&1)) st[++top]=0;
	sort(st+1,st+top+1);int l=1,r=top,res=-1;
	while (l<=r){
		int mid=(l+r)>>1;
		if (chk(mid,x,top)) res=mid,r=mid-1;
		else l=mid+1;
	}if (res==-1&&!chk(r,x,top)) mk=0;f[u]=st[res]+1;	
}
inline bool check(int x){
	mk=1;fa[rt]=0;dfs(rt,x);
	return (mk&&(f[rt]<=x+1));	
}
int main()
{
	n=in();
	for (int i=1;i<n;++i){
		x=in();y=in();ins(x,y);ins(y,x);
		++ind[x];++ind[y];
	}
	for (int i=1;i<=n;++i) if (ind[i]&1) rt=i,++num;
	printf("%d ",num>>1);
	int l=1,r=n;while (l<=r){
		int mid=(l+r)>>1;
		if (check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}printf("%d",ans);return 0;
}

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

#define ull unsigned long long int
#define ll long long int
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define MOD (ull)(double)(1e9 + 7)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define pull pair<ull, ull>
#define m_p make_pair
#define debug(x) cout << #x << " " << x << endl

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int tt=1;
	//cin >> tt;
	
	while(tt--){
		ll x;
		cin >> x;
		
		ll sum=100;
		ll y=0;
		while(sum < x){
			sum += sum / 100;
			y++;
		}
		
		cout << y;
	}
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef vector<ld> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)


ll INF = 1e9;
ll NIL = -1;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------

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

    ll n;
    cin >> n;
    vll a(n);
    REP(i,n){
        cin >> a[i];
    }
    ll cnt = 0;
    REP(i,n){
        if(i%2==0 && a[i]%2==1){
            cnt++;
        }
    }
    cout << cnt <<endl;

    
    return 0;
}



Measured memory_bytes: 3652
import java.util.Scanner;

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

        if (str.equals("ABC")) {
            System.out.println("ARC");
        }
        else {
            System.out.println("ABC");
        }
    }
}


Measured memory_bytes: 35736
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    String x = "ACL";
    String y = "";
    
    for (int i = 0; i < K; i++){
      
      y += x;
      
      
    }
    System.out.print(y);  
  }
}

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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define mp make_pair
#define ll long long
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2097162
#define inf 1e9
#define MOD 1000000007

int main()
{

    ll n, l;
    cin >> n >> l;
    vector<ll> v;
    ll sum = 0;
    for(ll i = 1; i <= n; i++)
    {

        ll x = l+i-1;
        v.pb(x);
        sum+=x;
    }
    ll ans, diff = inf;
    for(ll i = 0; i < n; i++)
    {

        ll x = sum-v[i];
        if(abs(sum-x) < diff)
        {

            ans = x;
            diff = abs(sum-x);
        }
    }
    cout << ans;
}


Measured memory_bytes: 256
n,m=(int(i) for i in input().strip().split(" "))
ar=[int(i)%m for i in input().strip().split(" ")]
t=[0,ar[0]]
for i in range(1,n):
    t.append((t[i]+ar[i])%m)
from collections import Counter
c=Counter(t)
ans=0
for i in c.values():
    ans+=((i*(i-1))//2)
print(ans)


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

typedef long long ll;
#define ALL(a) a, a+sizeof(a)/sizeof(a[0])
#define all(a) a.begin(),a.end()
#define MOD 1000000007
using namespace std;
ll gcd(ll n, ll m) {
	if (m == 0) return n;
	return gcd(m, n % m);
}
ll lcm(ll n, ll m) {return m / gcd(n, m) * n;}

int code[127][2];

int main(void) {
	int h,w,ans=0;
	string s;
	while (1) {
		ans = 0;
		int before[2] = { 0,0 };
		cin >> h >> w;
		if (h == 0 && w == 0) break;
		vector<string> r(h);
		for (int i = 0; i < h; i++) cin >> r[i];
		cin >> s;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				code[r[i][j]][0] = i;
				code[r[i][j]][1] = j;
			}
		}
		for (int i = 0; i < s.length(); i++) {
			ans += abs(code[s[i]][0] - before[0]);
			ans += abs(code[s[i]][1] - before[1]) + 1;
			memcpy(before, code[s[i]], sizeof(before));
		}
		cout << ans << "\n";
	}
	return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/detail/standard_policies.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define ll long long
    #define int long long
    #define pb push_back
    #define For(i,n) for(ll  i=0;i<n;i++)
    #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) ;clock_t clk = clock();
    #define f(a,b,c) for(ll a=b;a<c;a++)
    #define ld long double
    #define read(t) ll t;cin>>t;
    #define all(x) x.begin(),x.end()
    #define fi first
    #define se second
    #define pii pair<ll,ll>
    #define endl "\n"
    #define sz(x) (int)(x).size()
    #define what_is(x) cerr << #x << " is " << x << endl;
    #define time cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / CLOCKS_PER_SEC << '\n';
    const double pi=3.14159265358979323846264;
    typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
/*.....................................................................................................................*/

    ll mod =(ll)1e9+7;
    ll add(ll x,ll y) {return (x+y)%mod;}
    ll mult(ll x, ll y){return ((x%mod )* (y%mod)) % mod;}
    long long binpow(long long x, long long p) 
    {
        if (p == 0) return 1;
    	if (p == 2 || (p & 1)) return mult(x, binpow(x, p - 1));
    	return binpow(binpow(x, p / 2), 2);
    }
    ll modinv(ll a) {return binpow(a,mod-2);}

    // bool check(ll y){}
    ll binsearch(ll l,ll r)
    {
        // while(r-l>1)
        // {
        //     ll mid=(l+r)/2;
        //     if(check(mid))l=mid;
        //     else r=mid;
        // }
        return l;
    }
    const ll man=(ll)1e3+5;
    vector<ll>adj[man];
    bool vis[man][man];
    ll d[man],depth[man],par[man];
    void addedge(ll u,ll v){adj[u].pb(v);adj[v].pb(u);}
    ll dx[4]={1,-1,0,0};ll dy[4]={0,0,1,-1};
/*........................................................................................................................*/

signed main()/*Check flow...question galat mat padhna */
{
    fast;
    ll a,b,k;
    cin>>a>>b>>k;
    priority_queue<ll>q;
    for(ll i=1;i<=100;i++)
    {
        if(a%i==b%i&&a%i==0)q.push(i);
    }
    For(i,k-1)q.pop();
    cout<<q.top()<<endl;
}


Measured memory_bytes: 3668
#include<iostream>

using namespace std;

int main()
{
	for(int n,m;cin>>n>>m,n;){
		int prz[100];
		char hit[100][9];
		for(int i=0;i<n;i++)	cin>>hit[i]>>prz[i];

		int total=0;
		for(int i=0;i<m;i++){
			char lot[9];	cin>>lot;
			for(int j=0;j<n;j++){
				bool ok=true;
				for(int k=0;k<8;k++)	if(hit[j][k]!='*' && hit[j][k]!=lot[k])	ok=false;
				if(ok)	total+=prz[j];
			}
		}

		cout<<total<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int m;
vector<int> bit;

void init_bit(){
    bit.assign(m+2,0);
}

void add(int a,int w){
    for(int i=a;i<=m+1;i+=i&-i) bit[i]+=w;
}

int sum(int a){
    int res=0;
    for(int i=a;i>0;i-=i&-i) res+=bit[i];
    return res;
}

int main(){
    int n; cin>>n>>m;
    init_bit();
    vector<vector<pp>> data(m+1);
    rep(i,n){
        int l,r; cin>>l>>r;
        data[r-l+1].push_back(mk(l,r));
    }
    int cnt=n;
    for(int i=1;i<=m;i++){
        for(auto p:data[i-1]){
            add(p.first,1);
            add(p.second+1,-1);
            cnt--;
        }
        int ans=cnt;
        for(int j=i;j<=m;j+=i) ans+=sum(j);
        printf("%d\n",ans);
    }
}


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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int getcount(char* a,int aend,char comparison){
	int numOfR=0;
	//cout << sizeof(a)/sizeof(a[0]) << endl;
	rep(i,aend){
		if(a[i]==comparison) numOfR++;
	}
	//-- Rの数を数える
	return numOfR;
}

int main() {
	int ans=0;

	int n;
	cin >> n;
	char a[n];
	rep(i,n) cin >> a[i];

	//敷居のため、Rの数を求める
	int devide = getcount(a,n,'R');

	//敷居より左側のWの数を求める
	ans = getcount(a,devide,'W');

	cout << ans << endl;
}


Measured memory_bytes: 3840
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;

const ll INF = 1ll<<60;

int main(){
    int n, m;
    ll c;
    scanf("%d %d %lld", &n, &m, &c);

    map<int, map<int,int>> v;
    int a, b, d;
    ll sum = 0;
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &a, &b, &d);
        a--, b--;
        v[a][b] = d;
        v[b][a] = d;
        sum += d;
    }

    // dijkstra
    vector<ll> dist(n, INF);
    priority_queue<pair<ll,int>> pq;
    pq.push({-0, 0});

    while(!pq.empty()){
        pair<ll,int> p = pq.top();  pq.pop();
        ll cost = -p.first;
        int pos = p.second;
        if(cost >= dist[pos])   continue;
        dist[pos] = cost;
        for(pair<int,int> edge : v[pos]){
            if(cost + edge.second < dist[edge.first]){
                pq.push({-(cost + edge.second), edge.first});
            }
        }
    }

    vector<pair<ll,int>> vp;
    for(int i = 1; i < n; i++){
        vp.push_back({dist[i], i});
    }
    sort(vp.begin(), vp.end());

    int len = vp.size();
    int cur = 0;
    set<int> used;
    used.insert(0);
    ll ans = sum;

    while(cur < len){
        ll x = vp[cur].first;
        vector<int> add;
        add.push_back(vp[cur].second);
        while(cur+1 < len && vp[cur+1].first == x){
            cur++;
            add.push_back(vp[cur].second);
        }
        for(int del : add){
            for(auto e : v[del]){
                int to = e.first, cost = e.second;
                if(used.count(to)){
                    sum -= cost;
                }
            }
            used.insert(del);
        }
        ans = min(ans, c*x + sum);
        cur++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 39524
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(int i=0; i<(n); i++)
#define REPj(n) for(int j=0; j<(n); j++)
#define REPinit(i,a,n) for(int i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(int j=(a); j<(n); j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/*
    add utility Algorithm
*/


int main(int argc, char const* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K;
    int A, B;

    cin >> K;
    cin >> A >> B;

    for (int i = A; i <= B; i++) {
        if (i % K == 0) {
            cout << "OK\n";
            return 0;
        }
    }

    cout << "NG\n";


    return 0;
}


Measured memory_bytes: 3648
//#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <string>
#include <stdbool.h>
#include<ctime>

#include <cstring>

#define pb push_back


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ll long long
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))

#define getI(a) scanf("%d",&a)
#define getII(a, b) scanf("%d%d",&a,&b)
#define getIII(a, b, c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a, b) scanf("%lld%lld",&a,&b)
#define getLLL(a, b, c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfb(a) printf("%.10lf\n",a);
#define pfi(a) printf("%d",a);
#define pfii(a, b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a, b) printf("%lld%lld",a,b);
#define pfd(a) printf("%.12lf ",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define endl "\n"

#define MOD  ( int)(1e9 + 7)
#define MAXN (ll) ((1e5+5))
#define K 25
#define  ALPHABET_SIZE  26
//#define N (int)(1e5+10)
#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define INF (ll )1e18
//#define int ll
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int, int>>> vvpi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<vi> graph;





int main() {
	ll n;
	cin >> n;
	cout << n * n * n + n*n + n;
	return 0;
}

Measured memory_bytes: 3596
N, M = map(int, input().split())
A = list(map(int, input().split()))

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
for a in sorted(A, reverse=True):
    c = Matches[a]
    for i in range(N - c + 1):
        if dp[i] == -1:
            continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + a)

print(dp[N])


Measured memory_bytes: 16500
N, A, B, C = map(int, input().split())
lst = [int(input()) for i in range(N)]
INF = 10**9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(A - a) + abs(B - b) + abs(C - c) -30 if min(a, b, c) > 0 else INF
    ret0 = dfs(cur + 1, a, b, c)
    ret1 = dfs(cur + 1, a + lst[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + lst[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + lst[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
    
print(dfs(0, 0, 0, 0))

Measured memory_bytes: 3064
import sys
import math

def resolve():
    stdin = sys.stdin
    mod = 10**9 + 7
    ns = lambda: stdin.readline().rstrip()
    ni = lambda: int(ns())
    na = lambda: list(map(int, stdin.readline().split()))
    sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

    n, a, b = na()

    if (b-a) % 2 == 0:
        print((b-a)//2)
    else:
        f = (a-1) + (b-a)//2+1
        b = (n-b) + (b-a)//2+1
        print(min(f, b))

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
n=int(input())
a=[[] for _ in range(n)]
for i in range(n):
    cnt=int(input())
    while cnt>0:
        x,y=map(int,input().split())
        x-=1
        a[i].append([x,y])
        cnt-=1
ans=0
for mask in range(1<<n):
    #0 means bad 1 means good
    #check if this choice leads to a valid solution
    honest=[]
    for j in range(n):
        if (mask>>j)&1:
            honest.append(j)
    choice=True
    for i in honest:
        for j in a[i]:
            if (j[0] in honest and j[1]==0) or (j[0] not in honest and j[1]==1):
                choice=False
                break
        if choice==False:
            break
    if choice:
        ans=max(ans,len(honest))
print(ans)





Measured memory_bytes: 3064
//
// Created by yamunaku on 2019/12/22.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int n;
    string s,t;
    cin >> n;
    cin >> s >> t;
    rep(i,n){
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (b>a) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, char const *argv[]) {
    int n, m, ans;
    cin >> n >> m;
    ans = n/m;
    if(n%m!=0) ans++;
    cout << ans << endl;
    return 0;
}




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

struct UnionFind{
    vector<int> data;

    UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);//親は負でサイズを保存
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  bool same(int x, int y){
      return find(x) == find(y);
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

int main(){
    ll N,M;
    cin >> N >> M;
    Edge edge;
    rep(i,M){
        int u,v;
        cin >> u >> v;
        u--;v--;
        edge.push_back(make_pair(u,v));
    }
    reverse(edge.begin(),edge.end());
    vector<ll> res;
    UnionFind uf(N);
    res.push_back(N*(N-1)/2);
    for(auto e : edge){
        int u = e.first,v = e.second;
        if(!uf.same(u,v)){
            ll su = uf.size(u);
            ll sv = uf.size(v);
            res.push_back(res.back()-su*sv);
            uf.unite(u,v);
        }else{
            res.push_back(res.back());
        }
    }
    reverse(res.begin(),res.end());
    rep(i,res.size()-1){
        cout << res[i+1] << endl;
    }
    return 0;
}

Measured memory_bytes: 5104
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>

using namespace std;

typedef pair<int,bool> Pair;

int main(){

  int N;
  int INPUT;
  int W[100];
  int S1,S2;
  int ans=1000;
  
  cin >> N;
  
  for(int i = 0; i < N; ++i){

    cin >> INPUT;
	W[i] = INPUT;
	
  }  
  
  for(int T = 0; T < N; ++T){
  
	S1 = S2 = 0;  
  
	for(int i = 0; i < N; ++i){
  
		if(i <= T) S1+=W[i];
		if(T < i) S2+=W[i];
  
    }
  
	if(abs(S1 - S2) < ans) ans = abs(S1 - S2);
		
  }
    
    cout << ans << endl;

  return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int N; cin >> N;
    vector<ll> a(N+1, 0);
    for(int i=0; i<N; ++i) cin >> a[i];
    ll ans = 0;
    for(int i=0; i<N; ++i){
        ans += a[i]/2;
        if(a[i+1] != 0) a[i+1] += a[i]%2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	private static final int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		char[][] map = new char[M][];
		for (int i = 0; i < map.length; i++) {
			map[i] = sc.next().toCharArray();
		}
		sc.close();

		int point = 0;
		while (true) {
			int begin = point;
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[i].length; j++) {
					if (map[i][j] != '.') {
						continue;
					}
					PriorityQueue<Tile> tiles = new PriorityQueue<Tile>();

					for (int k = 0; k < dir.length; k++) {
						int l = 1;
						int ti = i + dir[k][0] * l;
						int tj = j + dir[k][1] * l;
						while (ti >= 0 && ti < M && tj >= 0 && tj < N) {
							if (map[ti][tj] != '.') {
								char c = map[ti][tj];
								tiles.add(new Tile(ti, tj, c));
								break;
							}
							l++;
							ti = i + dir[k][0] * l;
							tj = j + dir[k][1] * l;
						}
					}

					while (tiles.size() > 1) {
						Tile t1 = tiles.poll();
						Tile t2 = tiles.poll();
						if (t1.color != t2.color) {
							tiles.add(t2);
							continue;
						}

						map[t1.i][t1.j] = '.';
						map[t2.i][t2.j] = '.';
						point++;
					}
				}
			}

			if (point == begin) {
				break;
			}
		}

		System.out.println(point * 2);

	}
}

class Tile implements Comparable<Tile> {
	int i, j;
	char color;

	public Tile(int i, int j, char color) {
		this.i = i;
		this.j = j;
		this.color = color;
	}

	public int compareTo(Tile o) {
		return this.color - o.color;
	}
}

Measured memory_bytes: 57380
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <set>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){

    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

bool IsPrime(ll num){
    if(num < 2) return false;
    else if(num == 2) return true;
    else if(num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for(ll i = 3; i <= sqrtNum; i += 2){
        if(num%i==0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

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

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int s,a,b;
  cin >> s >> a >> b;
  if(s==a&&a==b)cout << "Yes";
  else cout << "No";
  /*
  if(strlen(a)==3)cout << a[2] << a[1] << a[0];
  else cout << a;
  /*
  int n;
  cin >> n;
  int a[n],r[n],b[n],p=0,q=0;
  char s[n];
  for(int i=0;i<n;i++){
    r[i]=99999999;
    b[i]=99999999;
  }
  for(int i=0;i<n;i++){
    cin >> a[i] >> s[i];
    if(s[i]=='R'){
      r[p]=a[i];
      p++;
    }
    else{
      b[q]=a[i];
      q++;
    }
  }
  sort(r,r+n);
  sort(b,b+n);
  for(int i=0;i<n;i++){
    if(r[i]==99999999)break;
    cout << r[i] << endl;
  }
  for(int i=0;i<n;i++){
    if(b[i]==99999999)break;
    cout << b[i] << endl;
  }
  */
}


Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		HashMap<Integer, Integer>map = new HashMap<Integer, Integer>();

		for (int i=1; i<n; i++){
			int a = sc.nextInt();
			if (map.containsKey(a)){
				map.put(a, map.get(a)+1);
			} else {
				map.put(a, 1);
			}
		}

		for (int i=1; i<=n; i++){
			if (map.containsKey(i)){
				System.out.println(map.get(i));
			} else {
				System.out.println("0");
			}
		}
	}
}

Measured memory_bytes: 64244
import sys


def input(): return sys.stdin.readline().strip()


def resolve():
    s1, s2, t1, t2 = map(int, input().split())
    l = []
    yoko = t1 - s1
    tate = t2 - s2
    a,c,f,h='R','L','L','R'
    b,d,e,g='U','D','D','U'
    l.append(a*yoko+b*tate+c*yoko+d*tate)
    l.append(e+a*(yoko+1)+b*(tate+1)+f)
    l.append(g+c*(yoko+1)+d*(tate+1)+h)
    print(''.join(l))
resolve()

Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
 
		int humanNum = sc.nextInt();
		int count = 0;
 
		for(int num = 1; num <= humanNum; num++) {
			count += num;
		}
 
		System.out.println(count);
	}
}

Measured memory_bytes: 35604
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		Scanner sc = new Scanner(System.in);

		ArrayList<String> lines = new ArrayList<String>();
		int in = 0;

		while (true) {
			String string = new String();
			string = sc.nextLine();

			if (string.equals("0 0")) {
				break;
			}

			lines.add(string);
			in++;
		}

		for (int i = 0; i < in; i++) {
			int h = 0;
			int w = 0;
			int v = 0;
			String[] str = lines.get(i).split(" ");
			h = Integer.parseInt(str[0]);
			w = Integer.parseInt(str[1]);

			while (h > 0) {
				v = w;
				while (w > 0) {
					System.out.print("#");
					w--;
				}
				System.out.println("");
				h--;
				w = v;
			}
			System.out.println("");
		}
	}

}

Measured memory_bytes: 33184
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		String S = stdIn.next();
		long K = stdIn.nextInt();
		char[] s = S.toCharArray();
		int n = S.length();
		int count = 0;
		
		for(int i = 0; i < n;) {
			int temp = 1;
			while(i < n-1 && s[i] == s[i+1]) {
				temp++;
				i++;
			}
			if(temp > 1) count += temp/2;
			i++;
		}
		
		if(s[0] == s[n-1]) {
			int i = 0;
			int j = n-1;
			while(i < n-1 && s[i] == s[i+1]) {
				i++;
			}
			while(j > 0 && s[j] == s[j-1]) {
				j--;
			}
			i = i+1;
			j = n-1-j+1;
			if(i == n) {
				System.out.println(n*K/2);
			}else {
				count = count-i/2-j/2;
				
				System.out.println(count*K+((i+j)/2)*(K-1)+i/2+j/2);
			}
		}
		else {
			System.out.println(count*K);
		}

	}

}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll x, y; cin >> x >> y;

    if(x%y == 0) cout << -1 << endl;
    else cout << x << endl;
}

Measured memory_bytes: 256
L = int(input())

N = len(str(bin(L)))-2

bitL = [0] *20
splitL  = [0] * 20
sumL = [0] * 20

for i in range(19,-1,-1):
  if L % 2 == 1:
    bitL[i] = 1
  L = L // 2

for i in range(19,-1,-1):
  splitL[i] = int(bitL[i]) * 2**(19-i)

for i in range(20):

  if i == 0:
    sumL[i] = splitL[i]
  else:
    sumL[i] =splitL[i]+sumL[i-1]

#print(splitL)
#print(sumL)
#print(bitL)

edge = []
 
for i in range(N-1):
  edge.append([i+1,i+2,0])
  edge.append([i+1,i+2,2**i])


for i in range(21-N,20):
  if bitL[i] == 1:
    edge.append([20-i,N,sumL[i-1]])


print(N,len(edge))

for i in range(len(edge)):
  print(edge[i][0],edge[i][1],edge[i][2])

Measured memory_bytes: 3064
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int num = 0;
        for(int i=0;i<M;i++){
            num+=scan.nextInt();
        }
        System.out.println((N<=num)?"Yes":"No");
    }
}


Measured memory_bytes: 48016
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    private static int fact(int n) { int ans=1; for(int i=2;i<=n;i++) ans*=i; return ans; }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        int mx = 200010;
        int n = in.nextInt();
        int a[] = new int[n];
        long ind[] = new long[mx];
        long ans[] = new long[mx];
        for(int i=0;i<n;i++){
            a[i] = in.nextInt();
            ind[a[i]]++;
        }
        long sum=0L;
        for(int i=0;i<mx;i++){
            if(ind[i]>0){
                sum += ( ind[i] * (ind[i] - 1) ) / 2;
            }
        }
        for(int i=0;i<mx;i++){
            if(ind[i]>0){
                if(ind[i]==1) ans[i] = sum;
                else ans[i] = sum - ((ind[i]*(ind[i]-1))/2) + (((ind[i]-1)*(ind[i]-2))/2);
            }
        }
        for(int i=0;i<n;i++){
            out.println(ans[a[i]]);
        }
    }
    
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 54372
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	register int f=1,k=0;register char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
int main()
{
	int n=read(),ans=1e9;
	for (register int i=1;i<n;i++)
	{
		int a=i,b=n-i,tmp=0;
		while (a)tmp+=a%10,a/=10;
		while (b)tmp+=b%10,b/=10;
		if (tmp<ans)ans=tmp;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000;
const long long MOD = 1000000007;

std::vector<bool> IsPrime;

void sieve(size_t max)
{
  if (max + 1 > IsPrime.size())
  {                                // resizeで要素数が減らないように
    IsPrime.resize(max + 1, true); // IsPrimeに必要な要素数を確保
  }
  IsPrime[0] = false; // 0は素数ではない
  IsPrime[1] = false; // 1は素数ではない

  for (size_t i = 2; i * i <= max; ++i)     // 0からsqrt(max)まで調べる
    if (IsPrime[i])                         // iが素数ならば
      for (size_t j = 2; i * j <= max; ++j) // (max以下の)iの倍数は
        IsPrime[i * j] = false;             // 素数ではない
}

class Pointer{
public:
  long long p;
  long long w;
};

int main()
{
  int N;
  cin >> N;
  vector<int> pa(N + 1, -1);
  //-1は不可能その他は親が入ってる

  for (int i = 1; i <= N;i++){
    long long a;
    cin >> a;
    pa[i] = a;
  }
  int num = 1;
  vector<bool> ex(N + 1, false);
  int ans = 0;
  while (1)
  {
    int u = pa[num];
    //cout << u << endl;
    if (u == 2)
    {
      ans++;
      cout << ans << endl;
      return 0;
    }
    if(ex[u]==true || u==-1){
      cout << -1 << endl;
      return 0;
    }
    num = u;
    ex[u] = true;
    ans++;
    //cout << u << endl;
  }
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

const int DEF = -1000000000;
class Cell{
private:
	int val;
	Cell *left,*right;
public:
	Cell(){
		val = DEF;
		left = NULL;
		right = NULL;
	}
	void Left(Cell *l){
		left = l;
	}
	void Right(Cell *r){
		right = r;
	}
	void Update(int x){
		val = x;
	}
	int Value(){
		return val;
	}
	Cell* Next(){
		return right;
	}
	Cell* Before(){
		return left;
	}

};

class DLL{
private:
	Cell *first,*last;
public:
	DLL(){
		first = new Cell();
		last = new Cell();
		first->Right(last);
		last->Left(first);
	}
	void Insert(int x){
		Cell *nc = new Cell();
		first->Update(x);
		first->Left(nc);
		nc->Right(first);
		first = nc;
	}
	void DeleteFirst(){
		first = first->Next();
		first->Update(DEF);
		delete first->Before();
	}
	void DeleteLast(){
		last = last->Before();
		last->Update(DEF);
		delete last->Next();
	}
	void Delete(int x){
		Cell* itr = first->Next();
		while(itr != last){
			if(itr->Value() == x){
				Cell* f = itr->Before();
				Cell* l = itr->Next();
				f->Right(l);
				l->Left(f);
				delete itr;
				return;
			}
			itr = itr->Next();
		}
	}
	void List(){
		Cell* itr = first->Next();
		printf("%d",itr->Value());
		itr = itr->Next();
		while(itr != last){
			printf(" %d",itr->Value());
			itr = itr->Next();
		}
		printf("\n");
	}
};

int main(){
	int n;
	DLL dll;

	scanf("%d",&n);
	char cmd[64];
	int v;
	while(scanf("%s",cmd) != EOF){
		if(strcmp(cmd,"insert") == 0){
			scanf("%d",&v);
			dll.Insert(v);
		}
		else if(strcmp(cmd,"delete") == 0){
			scanf("%d",&v);
			dll.Delete(v);
		}
		else if(strcmp(cmd,"deleteFirst") == 0){
			dll.DeleteFirst();
		}
		else if(strcmp(cmd,"deleteLast") == 0){
			dll.DeleteLast();
		}
		else if(strcmp(cmd, "list") == 0){
			dll.List();
		}
	}
	dll.List();
	return 0;
}




Measured memory_bytes: 33944
N, M = map(int, input().split())

city = []
for i in range(M):
	p, y = map(int, input().split())
	city.append([p, y, i])
city.sort()

out = [0]*M
cnt = 1
for i in range(len(city)):
	out[city[i][2]] = '{0:06d}{1:06d}'.format(city[i][0], cnt)
	try:
		if city[i+1][0] == city[i][0]: cnt += 1
		else: cnt = 1
	except(IndexError):
		cnt += 1

for o in out:
	print(o)
	

Measured memory_bytes: 31300
k, n = map(int, input().split())
a = list(map(int, input().split()))

b = [0] * (n)
for i in range(n-1):
    b[i] = a[i+1] - a[i]
b[n-1] = k - a[n-1] + a[0]

b.sort()
print(sum(b[:-1]))

Measured memory_bytes: 78924
N = int(input())

# 再帰で全探索, sは文字列とすると便利
def dfs( s ):
    # 現在の数字が N を越えたら終わり
    if int( s ) > N: return 0
    # s 自体が七五三数なら +1, 他なら 0
    ret = 1 if all( s.count(c) > 0 for c in '753' ) else 0 
    # 最後尾に3,5,7を加えて新たな七五三数を作る
    for c in '753':
         ret += dfs(s + c)
    return ret

print( dfs('0') ) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため

Measured memory_bytes: 2940