akhauriyash/Code-Regression huggingface dataset:
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
black=0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      black+=1
s=[0,0,1]
g=[h-1,w-1]
queue=[s]
go=[[0,1],[0,-1],[1,0],[-1,0]]
ans=-1
check=[[True for i in range(w)] for j in range(h)]
while len(queue)>0:
  p=queue.pop(0)
  for i in range(4):
    x=p[0]+go[i][0]
    y=p[1]+go[i][1]
    count=p[2]+1
    if x>-1 and x<h and y>-1 and y<w and check[x][y] and maze[x][y]=='.':
      if x==g[0] and y==g[1]:
        ans=count
        break
      else:
        check[x][y]=False
        queue.append([x,y,count])
  if ans>0:
    break
if ans<0:
  print(ans)
else:
  print(h*w-black-ans)

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

ll L[87];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	L[0] = 2;
	L[1] = 1;
	for(int i = 2; i <= 86; ++i) {
		L[i] = L[i-1] + L[i-2];
	}
	int n;
	cin >> n;
	cout << L[n];
	return 0;
}
	



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

int main() {
  ll n,a,b;
  cin>>n>>a>>b;
  cout<<(n/(a+b))*a+(n-(n/(a+b)*(a+b))<=a ? n-(n/(a+b)*(a+b)) : a)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxx = 1e5 + 5;

int n, m;

int main(){
	while(scanf("%d %d", &n, &m) == 2){
		if(n % (2 * m + 1) == 0) cout << n / (2 * m + 1) << endl;
		else cout << n / (2 * m + 1) + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

map<LL ,LL> dp;
LL INF=1000000007;

LL func(LL N){
    if(dp.find(N)!=dp.end())return dp[N];
    if(N==0)return dp[0]=1;
    if(N==1)return dp[1]=2;

    return dp[N]=(func(N/2)+func((N-1)/2)+func((N-2)/2))%INF;
}

int main(){
    LL N;cin>>N;
    cout<<func(N)<<endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
//#define lowbit(n) n & (-n)
#define ls x<<1
#define rs x<<1|1
#define clc(a, b) memset(a, b, sizeof(a))
#define Buff ios::sync_with_stdio(false)
#define rush() int Case = 0; int T; scanf("%d", &T);  while(T--)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define per(i, a, b) for(int i = a; i >= b; i --)
#define reps(i, a, b) for(int i = a; b; i ++)
#define read(a) scanf("%d", &a)
#define readd(a) scanf("%lf", &a)
#define readl(a) scanf("%lld", &a)
#define readc(a) scanf("%c", &a)
#define reads(a) scanf("%s", a)
#define sqr(x) x*x
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>PII;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int N = 3e5+7;
int b[N];
struct BIT //binary index tree
{
    int t[N],n;
    int a[N];
    #define lowbit(x) (x&(-x))
    void init(int n_)
    {
        n=n_;
        for(int i=1;i<=n;i++)
            t[i] = a[i] = 0;
    }
    int query(int l,int r)
    {
        int res=a[r];
        while(r>l) //t[i]维护 [i-lowbit(i)+1,i]的最值
        {
            for(--r;r-lowbit(r)>=l;r-=lowbit(r))// r-lowbit(r)+1>=l return max t[r],query(l,r-low(r))
                res=max(res,t[r]);              // r-lowbit(r)+1<l return max a[r],query(l,r-1)
            res=max(res,a[r]);
        }
        return res;
    }
    void modify(int x,int v)
    {
        a[x]=v;
        while(x<=n)
        {
            t[x]=a[x];
            for(int i=1,j=lowbit(x);i<j;i<<=1)// y+( lowbit(y)=2^i) =x
                t[x]=max(t[x],t[x-i]);        // 对pos=x的修改需要考虑其维护的(x-lowbit(x),x]区间里的数对该区间最值贡献
            x+=lowbit(x); //转移至包含该区间的下一个位置
        }
    }
};
BIT tree;
int main()
{
    Buff;
    int n, k, maxv = 1, res = 0;
    cin >> n >> k;
    rep(i, 1, n)
    {
        cin >> b[i];    b[i] ++;
        maxv = max(maxv, b[i]);
    }
    tree.init(maxv);
    rep(i, 1, n)
    {
        int l = max(1, b[i]-k);
        int r = min(maxv, b[i]+k);
        int t = tree.query(l, r);
        res = max(res, t + 1);
        tree.modify(b[i], t+1);
    }
    cout << res <<endl;
    return 0;
}


Measured memory_bytes: 6704
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)x)<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define EREP(i,a,b) for(int i=a;i<=b;i++)
#define erep(i,n) EREP(i,0,n)
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

typedef pair<int,int> E;

vector<E> t[502];

int trans(string s,map<string,int> &name){
  if(name.find(s) != name.end()){
    return name[s];
  }

  int size = name.size();
  name[s] = size;
  return size;
}

int dik(int from,int to){
  priority_queue<E,vector<E>,greater<E> > open;
  bool closed[502];
  open.push(E(0,from));
  memset(closed,0,sizeof(closed));

  while(!open.empty()){
    E e = open.top(); open.pop();
    if(closed[e.second]) continue;
    closed[e.second] = true;

    if(e.second == to){
      return e.first;
    }

    rep(i,t[e.second].size()){
      E edge = t[e.second][i];
      open.push(E(e.first+edge.second,edge.first));
    }
  }

  return INT_MAX;
}

int main(void){
  int n,m;

  while(cin>>n>>m,n||m){
    rep(i,n) t[i].clear();

    map<string,int> name;
    int s,p,g;
    string S,P,G;
    cin>>S>>P>>G;

    s = trans(S,name);
    p = trans(P,name);
    g = trans(G,name);

    rep(i,m){
      int a,b;
      string A,B;
      int d,l;
      cin>>A>>B>>d>>l;
      a = trans(A,name);
      b = trans(B,name);
      t[a].push_back(E(b,d/40+l));
      t[b].push_back(E(a,d/40+l));
    }

    cout<<dik(s,p)+dik(p,g)<<endl;
  }
}

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

void print_A(int A[],int n){
	for (int i = 0 ;i<n;i++) {
		if (i!=n-1 )printf("%d ",A[i]);
		else printf("%d",A[i]);
	}
	printf("\n");
	return ;
}

void insertsort(int A[], int n){
	print_A(A,n);
	for(int i = 1;i<n;i++){
		int temp=A[i],j=i-1;
		while(j>=0&&A[j]>temp){
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=temp;	print_A(A,n);
	}

	return ;
}

int main (){
	int n,A[110];
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	insertsort(A,n);
	return 0;
}


Measured memory_bytes: 3136
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acosl(-1.0);

ll mod_pow(ll x, ll n, ll m = mod) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % m;
		x = x * x % m; n >>= 1;
	}
	return res;
}
struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n % mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 19;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}



void solve() {
	modint ans = 0;
	int s; cin >> s;
	rep1(n, s/3) {
		int r = s - 3 * n;
		ans += comb(r + n - 1, n - 1);
	}
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(15);
	init_f();
	//init();
	//expr();
	//int t; cin >> t; rep(i, t)
	solve();
	return 0;
}


Measured memory_bytes: 11844
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] num_list = new int[n];
    for (int i = 0; i < n; i++){
      num_list[i] = sc.nextInt();
    }
    max_value(num_list, n);
  }

  public static void max_value(int[] lst, int n){
    int maxval = -2000000000;
    int minval = lst[0];
    for (int i = 0; i < n - 1; i++){
      maxval = Math.max(maxval, lst[i + 1] - minval);
      minval = Math.min(minval, lst[i + 1]);
    }
    System.out.println(maxval);
  }
}


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

int main() {
	int A, B;
	cin >> A >> B;
	int n = 0;
	while (true) {
		if (n * 8 / 100 == A && n * 10 / 100 == B) break;
		else if ((n * 8 / 100 - A) * (n * 10 / 100 - B) < 0) {
			n = -1;
			break;
		}
		else n++;
	}
	cout << n << endl;
}

Measured memory_bytes: 256
N,K=map(int,input().split())
H=[]
for i in range(N):
    h=int(input())
    H.append(h)
H.sort()
i=0
ans=max(H)-min(H)+1
while i+K-1<len(H):
    min_ans=H[i+K-1]-H[i]
    if ans>min_ans:
        ans=min_ans
    i=i+1
print(ans)


Measured memory_bytes: 7384
import sys
input = sys.stdin.readline
from operator import itemgetter

N = int(input())
LR = []
for _ in range(N):
    a, b = map(int, input().split())
    LR.append((a-b, a+b))

LR.sort(key=itemgetter(1))
now_max = -10**15
ans = N
for l,r in LR:
    if l < now_max:
        ans -= 1
    else:
        now_max = r

print(ans)

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

using namespace std;
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N, K;
    cin >> N >> K;
    vector<ll> cnt(K);
    for(int i = 1; i <= N; i++) cnt[i % K]++;

    ll ans = 0;
    for(int b = 0; b < K; b++) {
        int a = (K - b) % K;
        int c = (K - b) % K;
        if ((a + c) % K != 0) continue;
        ans += cnt[a] * cnt[b] * cnt[c];
    }
    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Measured memory_bytes: 1792
import math

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

n,d = list(map(int, input().split()))
x = []

for _ in range(n):
    tmp = list(map(int, input().split()))
    x.append(tmp)

counter = 0
distance = 0

for i in range(n-1):
    for j in range(i+1,n):
        distance = 0
        for k in range(d):
            distance += (x[i][k] - x[j][k])*(x[i][k] - x[j][k])
        #print(distance)
        distance = math.sqrt(distance)
        #print(x[i],x[j],distance)
        
        if is_integer_num(distance):
            #print("YES",distance)
            counter += 1

print(counter)

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

int sumofdigits(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += x % 10;
        x /= 10;
    }

    return sum;
}

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

    int ans = 10000;

    for (int i = 1; i < N; i++)
    {
        int sum = sumofdigits(i) + sumofdigits(N - i);
        ans = min(sum, ans);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		for (int i = S.length() - 1; i > 0; i--) {
			String f = S.substring(0, i / 2);
			String s = S.substring(i / 2, i);
			if (f.equals(s)) {
				System.out.println(i);
				break;
			}
		}
		sc.close();
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::map;
using std::set;
using std::bitset;
using std::vector;
using std::string;
using std::multimap;
using std::multiset;
using std::deque;
using std::queue;
using std::stack;
using std::pair;
using std::iterator;

using std::sort;
using std::stable_sort;
using std::reverse;
using std::max_element;
using std::min_element;
using std::unique;
using std::ios_base;
using std::swap;
using std::fill;

using std::setprecision;
using std::fixed;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef string S;

ll min(ll a, ll b) {return a < b ? a : b;}
ll min(int a, ll b) {return a < b ? a : b;}
ll min(ll a, int b) {return a < b ? a : b;}
ll min(int a, int b) {return a < b ? a : b;}

ll max(ll a, ll b) {return a > b ? a : b;}
ll max(int a, ll b) {return a > b ? a : b;}
ll max(ll a, int b) {return a > b ? a : b;}
ll max(int a, int b) {return a > b ? a : b;}

namespace MySpace{

};

#define F(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define fi first
#define se second
#define re return
#define all(x) (x).begin(), (x).end()
#define int long long

const int N = 333333;
const int MOD = 998244353;

int n, m;
vector<int> a[500];
vector<int> st[500];

long long inq(long long x, long long y)
{
    if (y == 0) return 1;
    long long l = inq(x, y / 2);
    if (y % 2) return l * l % MOD * x % MOD;
    return l * l % MOD;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }
    int sz = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] && st[j].size() == 0)
            {
                t = j;
                break;
            }
            else
            {
                if (a[i][j])
                {
                    for (int k = 0; k < m; k++)
                    {
                        a[i][k] = a[i][k] ^ st[j][k];
                    }
                }
            }
        }
        if (t > -1)
        {
            st[t] = a[i];
            sz++;
        }
    }
    //cout << sz << "\n";
    cout << inq(2, m - 1) * (inq(2, n) - inq(2, n - sz) + MOD) % MOD;
}


Measured memory_bytes: 2176
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
const int INF = 1001001001;
const ll LINF = 1e18;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const P p1, const P p2){ return p1.first < p2.first;};
bool p_comp_fg(const P p1, const P p2){ return p1.first > p2.first;};
bool p_comp_ss(const P p1, const P p2){ return p1.second < p2.second;};
bool p_comp_sg(const P p1, const P p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

const ll mod = 1e9 + 7;

int main(){
    string S; cin >> S;
    vvl dp(S.size()+1, vl(4,0)); FOR(i, 0, S.size()+1) dp[i][0] = 1;
    FOR(i,0,S.size()){
        if(S[i] == 'A'){
            dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod;
            for(auto j : {0,2,3}) dp[i+1][j] = dp[i][j];
        }
        else if(S[i] == 'B'){
            dp[i+1][2] = (dp[i][1] + dp[i][2]) % mod;
            for(auto j : {0,1,3}) dp[i+1][j] = dp[i][j];
        }
        else if(S[i] == 'C'){
            dp[i+1][3] = (dp[i][2] + dp[i][3]) % mod;
            for(auto j : {0,1,2}) dp[i+1][j] = dp[i][j];
        }
        else if(S[i] == '?'){
            REP(j, 4){
                dp[i+1][j] = (3 * dp[i][j] + (j >= 1 ? dp[i][j-1] : 0)) % mod;
            }
        }
    }
    cout << dp[S.size()][3] << endstr;
    return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
struct fastio{fastio(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}}_fast_io_;
template<class T> bool chmin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

#include <vector>
#include <functional>

template<class T>
struct segment_tree {
	using value_type = T;
	using size_type = std::size_t;
	using F = std::function<T(T, T)>;
private : 
	size_type n;
	const F f;
	const value_type ie;
	std::vector<value_type> node;

public : 
	segment_tree (const F &f, const value_type &ie) noexcept : f(f), ie(ie) { }

	void assign (size_type _n) noexcept {
		n = _n;
		node.assign(n << 1, ie);
	}

	void assign (size_type _n, const value_type &x) noexcept {
		assign(_n);
		std::fill(node.begin() + n, node.end(), x);
		for (int i = n; i--> 0;) {
			node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
		}
	}

	template<class Iterator>
	void build (Iterator first, Iterator last) {
		assign(last - first);
		for (size_type i = n; first != last; i++, first++) node[i] = (*first);
		for (int i = n; i --> 0;) {
			node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
		}
	}

	void set_val (size_type i, const value_type &x) {
		i += n;
		node[i] = x;
		for (i >>= 1; i > 0; i >>= 1) {
			node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
		}
	}

	value_type fold (size_type l, size_type r) {
		value_type vl = ie, vr = ie;
		for (l += n, r += n; l ^ r; l >>= 1, r >>= 1) {
			if (l & 1) vl = f(vl, node[l++]);
			if (r & 1) vr = f(node[--r], vr);
		}
		return f(vl, vr);
	};

	constexpr const value_type& fold_all() const noexcept {
		return (node[1]);
	}

	const value_type& operator[] (size_type i) const noexcept {
		return node[i + n];
	}

	const value_type& at (size_type i) const noexcept {
		return node.at(i + n);
	}

};

constexpr int MAX = 500500;

int main() {
	int n, q;
	std::cin >> n >> q;
	std::vector<int> c(n);
	std::vector<std::tuple<int, int, int>> query;
	for (int &e : c) std::cin >> e;
	for (int i = 0; i < q; i++) {
		int l, r;
		std::cin >> l >> r;
		query.emplace_back(r, --l, i);
	}
	
	std::sort(query.begin(), query.end());
	
	std::vector<int> last(MAX, -1), ans(q);
	auto f = [](int a, int b) { return a + b; };
	segment_tree<int> seg(f, 0);
	seg.assign(n);
	
	int r = 0;
	for (auto [ir, il, idx] : query) {
		for (; r < ir; r++) {
			if (last[c[r]] != -1) seg.set_val(last[c[r]], 0);
			last[c[r]] = r;
			seg.set_val(r, 1);
		}
		ans[idx] = seg.fold(il, ir);
	}
	
	for (int a : ans) std::cout << a << '\n';
	
	return 0;
}

Measured memory_bytes: 19428
#include<bits/stdc++.h>
using namespace std;
template <typename T> using vec = vector<T>;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int s = 0;
    for (int i = 0; i < n; i++)
    {
        s ^= a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cout << (s ^ a[i]) << " ";
    }
    cout << endl;
}

Measured memory_bytes: 4320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define int long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int mod = 1e9+7;
const int N = 1e7+5;
int cnt[N], g[N];

void preproces(){
	for(int i = 1; i < N; i++){
		for(int j = i; j < N; j+=i)
			cnt[j]++;
	}

	for(int i = 2; i < N; i++)
		cnt[i] += cnt[i-1];

	g[1] = 1;

	for(int i = 2; i < N; i++){
		g[i] = g[i-1] + i*(cnt[i] -cnt[i-1]);
	}
}
int32_t main(){
	// #ifndef ONLINE_JUDGE
	// 	freopen("in.txt", "r", stdin);
	// 	freopen("out.txt", "w", stdout);
	// #endif

	// for(int i = 1; i <= 10; i++)
	// 	cout<<g[i]<<" ";
	// cout<<"\n";
	preproces();
	int n;
	cin>>n;
	cout<<g[n]<<"\n";
	return 0;
}

Measured memory_bytes: 159872
#include <iostream>
#include <bits/stdc++.h>
#define NMAX 1005
using namespace std;
int n;
map<string,int> m;
int main()
{
    cin>>n;
    int nr=0;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        if(m.find(s)==m.end())
        {
            nr++;
            m[s]=1;
        }


    }
    cout<<nr;
}


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

int n;
int r[18], b[18];
struct info {
  int val, pos, color;
};
int BLUE = 1;
int RED = 0;
int f(int choice) {
  int sorted[n];
  info orig[n];
  for (int i=0; i<n; i++) {
    if ((choice>>i) & 1) {
      orig[i] = {b[i], i, BLUE};
      sorted[i] = b[i];
    } else {
      orig[i] = {r[i], i, RED};
      sorted[i] = r[i];
    }
  }
  sort(sorted, sorted + n);
  int cnt = 0;
  for (int i=0; i<n; i++) {
    bool found = false;
    for (int j=i; j<n; j++) {
      if (sorted[i] != orig[j].val) {
        continue;
      }
      int color = orig[j].color;
      int pos = orig[j].pos;
      if (color == RED && abs(pos - i) % 2 != 0) {
        continue;
      }
      if (color == BLUE && abs(pos - i) % 2 != 1) {
        continue;
      }
      found = true;
      cnt += j - i;
      for (int k=j; k>i; k--) {
        orig[k] = orig[k-1];
      }
      break;
    }
    if (!found) {
      return -1;
    }
  }
  return cnt;
}
int main() {
  cin>>n;
  for (int i=0; i<n; i++) cin>>r[i];
  for (int i=0; i<n; i++) cin>>b[i];
  int ans = 1e9;
  for (int choice=0; choice<(1ll<<n); choice++) {
    int cnt = f(choice);
    if (cnt > -1) {
      ans = min(cnt, ans);
    }
  }
  if (ans == 1e9) {
    cout<<-1<<endl;
  } else {
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 256
n,m = map(int, input().split())

A = [[0 for i in range(m+1)] for j in range(n+1)]

for i in range(n):
  data = input().split()

  for j in range(m):
    A[i][j] = int(data[j])

for i in range(n):
  for j in range(m):
    A[i][m] += A[i][j]

for j in range(m+1):
  for i in range(n):
    A[n][j] += A[i][j]

for i in range(n+1):
    print(*A[i])


Measured memory_bytes: 6208
import java.util.Scanner;

public class Main {
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        //int x = sc.nextInt();
        int n = sc.nextInt();
        int[] id = new int[n-1];
        int[] times = new int[n+1];
        //int[] d = new int[102];
        
        for(int i = 0; i<n-1;i++) {
        	id[i] = sc.nextInt();
        	times[id[i]]++;
        }
        
        for(int i = 1; i<=n; i++) {
        	System.out.println(times[i]);
        }
        
        
        
        
        
        
        
        //System.out.print(ans);
        
	}
}

Measured memory_bytes: 63508
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s; cin >> s;
    int cnt = 0;
    for(int i = 0, j = s.size()-1; i < j; i++, j--){
        if(s[i] != s[j]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 350
using namespace std;
typedef unsigned long long ll;
int n;
char s[MAXN];
map<pair<ll,ll> ,ll> used[MAXN][MAXN];
ll ans;
void dfs1(int x,ll sum1,ll sum2,int len1,int len2){
	if(x==n){
		used[len1][len2][make_pair(sum1,sum2)]++;
		return ;
	}
	dfs1(x+1,sum1*131+(ll)(s[x]-'a'+1),sum2,len1+1,len2);
	dfs1(x+1,sum1,sum2*131+(ll)(s[x]-'a'+1),len1,len2+1);
}
void dfs2(int x,ll sum1,ll sum2,int len1,int len2){
	if(x==n-1){
		ans+=used[len1][len2][make_pair(sum1,sum2)];
		return ;
	}
	dfs2(x-1,sum1*131+(ll)(s[x]-'a'+1),sum2,len1+1,len2);
	dfs2(x-1,sum1,sum2*131+(ll)(s[x]-'a'+1),len1,len2+1);
}
int main(){
	SF("%d",&n); 
	SF("%s",s);
	dfs1(0,0,0,0,0); 
	dfs2(2*n-1,0,0,0,0);
	PF("%llu",ans);
} 

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

bool is_palindrome(string s)
{
    string t(s.rbegin(),s.rend());
    return s == t;
}

int main()
{ 
    int a,b,c,d,e,f,g,h,i,j;
    string s;
    cin>>s;
    int n=s.size(),k,tc,ans=0;
    if(is_palindrome(s) && is_palindrome(s.substr(0,(n-1)/2)) && is_palindrome(s.substr((n+1)/2)))
    {
        cout<<"Yes"<<endl;
    }
    else
        {cout<<"No"<<endl;}
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	cards := make([]int,n)
	for i := 0; i < n; i++ {
		var num int
		fmt.Scan(&num)
		cards[i] = num
	}
	sort.Sort(sort.Reverse(sort.IntSlice(cards)))

	alice := 0
	bob := 0
	for k,card := range cards {
		if k % 2 == 0 {
			alice += card
		} else {
			bob += card
		}
	}

	fmt.Println(alice - bob)
}

Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (in i = 0; i < (in)(n); i++)
#define REP(i,a,b) for(in i=(in)(a);i<(in)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const in inf=1e9+7;
using P=pair<in,in>;
vector<in> dx={0,1,-1,0};
vector<in> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    in n;
    cin>>n;
    vector<in> a(n);
        rep(i,n) cin>>a.at(i);
    in q,b,c;
    cin>>q;

    in sum=0ll;
    rep(i,n) sum +=a[i];
    vector<in> cnt(100001,0ll);
    rep(i,n){
        cnt[a[i]] ++;
    }

    rep(nfiwfbi,q){
        cin>>b>>c;
        in cntb=cnt[b];
        cnt[b]=0ll;
        sum -= cntb*b;
        cnt[c] +=cntb;
        sum += cntb*c;
        //cout<<endl<<"ans=";
        cout<<sum<<endl;
    }
}/*
./problem.exe
*/

Measured memory_bytes: 4776
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n)             for(int i = 0; i < n; i ++)
#define forn1(i, n)            for(int i = 1; i <= n; i ++)
#define pb push_back
#define ll long long int
#define fi first
#define se second
#define ii  pair<long long int, long long int>
#define vi  vector <long long int>
#define vii vector <pair <long long int, long long int > >
#define all(cont)  cont.begin(), cont.end()
#define EPS 1e-9
#define MOD 1000000007
#define range 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
ll dp[60][2][2][2];
bool cached[60][2][2][2];
int len;
vi lower, upper;

ii merges[3] = {{1, 1}, {1, 0}, {0, 0}};

ll solve(int pos, int l_set, int r_set, int prefix){
	// cerr << pos <<" " << r_set << " " << l_set << endl;
	if(pos == len){
		return 1;
	}
	
	if(cached[pos][l_set][r_set][prefix] == true) return dp[pos][l_set][r_set][prefix];
	cached[pos][l_set][r_set][prefix] = true;

	ll & ans = dp[pos][l_set][r_set][prefix];

	int mn = 0, mx = 1;
	if(r_set == 1) mx = upper[pos];
	if(l_set == 1) mn = lower[pos];

	// cout << mx << " " << mn << endl;
	forn(i, 3) {
		if(merges[i].fi > mx) continue;
		if(merges[i].se < mn) continue;

		if(prefix == 0 && i == 1) continue;
		int nprefix = (i == 0) || (prefix == 1);

		int nlset = (l_set == 1)&&(merges[i].se == mn);
		int nrset = (r_set == 1)&&(merges[i].fi == mx);

		ans += solve(pos + 1, nlset, nrset, nprefix);
		if(ans >= MOD) ans -= MOD;
	}
	return ans;

}

int main(){

  //  freopen("input.txt","r",stdin);
    IOS;
    clock_t clk = clock();

    ll l, r;
    cin >> l >> r;

    for(; l; l = l / 2) lower.pb(l%2);
    for(; r; r = r / 2) upper.pb(r%2);
    while(lower.size() < upper.size()) lower.pb(0);
	reverse(all(lower));
	reverse(all(upper));
	len = upper.size();

	// forn(i, upper.size()) cout<< upper[i] <<" "; cout<<endl;
	// forn(i, lower.size()) cout<< lower[i] <<" "; cout<<endl;

    cout<<solve(0, 1, 1, 0);    



    cerr << endl << setprecision(10) << fixed << (double)(clock() - clk) / CLOCKS_PER_SEC;
    return 0;
}


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

using namespace std;

string S;
int main(void){
    cin >> S;

    if(S.length() >= 4 && S[0] == 'Y' && S[1] == 'A' && S[2] == 'K' && S[3] == 'I'){
        cout << "Yes" << endl;;
    } else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
# coding:utf-8
n = int(input())
a = list(map(int,input().split(' ')))
b = list(map(int,input().split(' ')))
d = [ a - b for a,b in zip(a,b)]
m = [ di for di in d if di < 0]
p = [ di for di in d if di > 0]

sum_m = sum(m)
if sum_m == 0:
  print(0)
  exit()

p.sort(reverse=True)
for i,pi in enumerate(p):
  sum_m += pi
  if sum_m >= 0:
    print(len(m) + i + 1)
    exit()

print(-1)


Measured memory_bytes: 18836
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <climits>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
using ll = long long;
int cnt = 0;
int N;
int main(){
    cin >> N;
    int A[N], B[N], C[N];
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    rep(i, N) cin >> C[i];
    sort(A, A + N);
    sort(C, C + N);
    ll ans = 0;
    for(int b = 0; b < N; b++){
        ll a = lower_bound(A, A + N, B[b]) - A;
        ll c = N - (upper_bound(C, C + N, B[b]) - C);
        ans += a * c;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
import java.math.BigInteger;
import java.util.*;


public class Main {
	
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			long a = sc.nextLong();
			long b = sc.nextLong();
			long c = sc.nextLong();
			long k = sc.nextLong();
			
			if(k%2==1){
				System.out.println(b-a);
			}
			else{
				System.out.println(a-b);
			}
			
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

}


Measured memory_bytes: 24916
/**
*    author:  yuya1234
*    created: 10.07.2020 16:33:27
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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

  ll l,r;
  cin>>l>>r;

  ll ans=2019;
  FOR(i,l,r-1)
  {
    FOR(j,i+1,r)
    {
      ans=min(ans,(i*j)%2019);
      if(ans==0)
      {
        i=r;
        j=r;
      }
    }
  }

  cout<<ans<<endl;

  return 0;
}

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

namespace AtCoder
{
	class Program
	{
		public static void Main()
		{
			var intArray = IO.ReadIntArray();
			var pointNum = intArray[0];
			var distanceNums = new int[pointNum + 1];
			var x = intArray[1];
			var y = intArray[2];
			for(var iIndex0 = 1 ; iIndex0 <= pointNum ; ++ iIndex0)
			{
				for(var iIndex1 = iIndex0 + 1 ; iIndex1 <= pointNum ; ++ iIndex1)
				{
					var simpleDistance = iIndex1 - iIndex0;
					var bridgeDistance = Math.Abs(x - iIndex0) + 1 + Math.Abs(iIndex1 - y);
					++ distanceNums[Math.Min(simpleDistance , bridgeDistance)];
				}
			}
			IO.Write(distanceNums.Skip(1).Take(pointNum - 1) , "\n");
		}
	}

	public static class IO
	{
		public static string   Read()							   { return Console.ReadLine(); }
		public static string[] ReadArray(char iSplitter = ' ')	   { return Read().Split(iSplitter); }
		public static int	   ReadInt()						   { return int.Parse(Read()); }
		public static int[]	   ReadIntArray(char iSplitter = ' ')  { return ReadArray().Select(iText => int.Parse(iText)).ToArray(); }
		public static long	   ReadLong()						   { return int.Parse(Read()); }
		public static long[]   ReadLongArray(char iSplitter = ' ') { return ReadArray().Select(iText => long.Parse(iText)).ToArray(); }
		public static char[]   ReadCharArray()					   { return Read().ToCharArray(); }

		public static void Write(string iValue)									   { Console.WriteLine(iValue); }
		public static void Write(int iValue)									   { Console.WriteLine(iValue); }
		public static void Write(IEnumerable<int> iValue , string iJoinWord = " ") { Console.WriteLine(string.Join(iJoinWord , iValue)); }
		public static void Write(long iValue)									   { Console.WriteLine(iValue); }
		public static void Write(decimal iValue)								   { Console.WriteLine(iValue); }
		public static void Write(bool iValue)									   { Console.WriteLine(iValue ? "Yes" : "No"); }
	}

	public static class Util
	{
		public static long Gcd(long i0 , long i1) { return (i0 > i1) ? _Gcd(i0 , i1) : _Gcd(i1 , i0); }
		public static long Lcm(long i0 , long i1) { return (i0 * i1) / Gcd(i0 , i1); }
		public static long ModPow(long iBaseNumber , long iPow , long iModNumber)
		{
			var num = 1L;
			while(iPow != 0)
			{
				if((iPow & 0x1) != 0)
				{
					num = (num * iBaseNumber) % iModNumber;
				}
				iBaseNumber = (iBaseNumber * iBaseNumber) % iModNumber;
				iPow >>= 1;
			}
			return num;
		}

		private static long _Gcd(long i0 , long i1)	{ return (i1 == 0) ? i0 : _Gcd(i1 , i0 % i1); }
	}
}


Measured memory_bytes: 13472
N, K = map(int, input().split())
A = list(map(int, input().split()))

kb = format(K, 'b')[::-1]
v = len(kb)

dp = [0]*v
for e in A:
    i = 0
    while e > 0 and i < v:
        if e % 2 == 1:
            dp[i] += 1
        e //= 2
        i += 1

bi = ""
for i in range(v):
    if dp[i] > N // 2:
        bi += "0"
    else:
        bi += "1"

bi = bi

def hoge(binary):
    res = 0
    n = int(binary[::-1], 2)
    for e in A:
        res += n ^ e
    return res


def calc(i):
    tmp = bi[:i] + "0" + bi[i+1:]
    return hoge(tmp)

ans = 0
for i in reversed(range(v)):
    if bi[i] == "1" and kb[i] == "1":
        ans = max(ans, calc(i))
    elif bi[i] == "1" and kb[i] == "0":
        bi = bi[:i] + "0" + bi[i+1:]
    elif bi[i] == "0" and kb[i] == "1":
        break

ans = max(ans, hoge(bi))

print(ans)


Measured memory_bytes: 70900
#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int u,v,w;
};
vector<edge> ans;
int l,n,p,m,s,i;
int main()
{
	cin>>l;
	--l;
	n=1;
	p=1;
	while (p+s<=l)
	{
		ans.push_back((edge){n,n+1,0});
		ans.push_back((edge){n,n+1,p});
		s+=p;
		p*=2;
		++n;
	}
	i=n-1;
	p/=2;
	m=s-p;
	while(s<l)
	{
		if(s+m+1<=l)
		{
			ans.push_back((edge){i,n,s+1});
			s+=m+1;
		}
		p/=2;
		m-=p;
		i--;
	}
	cout<<n<<' '<<ans.size()<<'\n';
	for(unsigned i=0;i<ans.size();++i)
		cout<<ans[i].u<<' '<<ans[i].v<<' '<<ans[i].w<<'\n';
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	long long int n, a[200000], i, j, p = 0;
	scanf("%lld", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	for (i = 0; i < n - 1; i++)
	{
		//for (j = i + 1; j < n; j++)

		if (a[i] > a[i + 1])
		{
			p = p + (a[i] - a[i + 1]);
			a[i + 1] = a[i];
		}
	}

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

Measured memory_bytes: 3288
import java.io.BufferedReader;
//import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		//System.setIn(new FileInputStream("./input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		boolean[] dict = new boolean[(int) Math.pow(5, 12)];
		char[] c;
		for(int i = 0; i < n; ++i) {
			c = br.readLine().toCharArray();
			if(c[0] == 'i'){
				// insert
				dict[hash(Arrays.copyOfRange(c, 7, c.length))] = true;
			}else{
				// find
				if(dict[hash(Arrays.copyOfRange(c, 5, c.length))] == true){
					System.out.println("yes");
				}else{
					System.out.println("no");
				}
			}
					
		}
	}
	public static int hash(char[] c){
		int a;
		int n = c.length;
		int hash = 0;
		for(int i = 0; i < n; ++i) {
			switch(c[n - i - 1]){
			case 'A':
				a = 1;
				break;
			case 'C':
				a = 2;
				break;
			case 'G':
				a = 3;
				break;
			default:
				a = 4;
				break;				
			}
			hash = hash*5 + a;
		}
		
		return hash;
		
	}
}

Measured memory_bytes: 301372
#include <stdio.h>

#define MAX_N 246912

int isPrime[ MAX_N + 1 ], pNum[ MAX_N + 1 ] = { 0, 0 };

int main( void ) {
	int i, j, n;

	isPrime[ 1 ] = 0;
	for ( i = 2; i <= MAX_N; i++ )
		isPrime[ i ] = 1;

	for ( i = 2; i <= MAX_N; i++ ) {
		pNum[ i ] = pNum[ i - 1 ] + isPrime[ i ];

		if ( isPrime[ i ] )
			for ( j = i * 2; j <= MAX_N; j += i )
				isPrime[ j ] = 0;
	}

	for ( ; scanf( "%d", &n ), n; printf( "%d\n", pNum[ n * 2 ] - pNum[ n ] ) ) ;

	return 0;
}

Measured memory_bytes: 2528
li = list(map(int,input().split()))
n,m=li[0],li[1]
_list=[int(input()) for i in range(m)]
is_safe = [True] * (n+1)
for a in _list:
  is_safe[a] = False
DP=[1, 1] if is_safe[1] == True else [1, 0]
for i in range(n-1):
  if is_safe[i+2] == False:
    DP+= [0]
  else:
    DP += [DP[i] + DP[i+1]]
print(DP[n] % 1000000007 if DP[n] != 0 else 0)

Measured memory_bytes: 460788
//submitted by HimJ
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  int t=1;
  //cin>>t;
    while(t--){
            ll n,i,x;
    cin>>n;
    ll arr[n];
    ll neg=0ll,pos=0ll;
    fr(i,0,n)
    {
        cin>>arr[i];
    }
    fr(i,0,n)
    {
        cin>>x;
        if(x-arr[i]>1)
            pos+=(x-arr[i])/2;
        else if(arr[i]>x)
            neg+=(arr[i]-x);
    }
   // cout<<pos<<" "<<neg;
    if(pos-neg>=0)
        cout<<"Yes";
    else
        cout<<"No";

  }
  return 0;
  }



Measured memory_bytes: 384
#include <stdio.h>
#include <algorithm>
#include <functional>
typedef long long ll;

int main(void) {
  ll i, j, k, h, ans = 1ll << 40;
  scanf("%lld", &h);
  while(!(ans & h)) ans >>= 1; 
  printf("%lld", (ans << 1) - 1);
  return 0;
}

Measured memory_bytes: 128
def main():
    data = []
    n = input().split()
    a = int(n[0])
    b = int(n[1])

    divans = a / b
    intdiv = int(divans)
    divr = a % b

    print("{0} {1} %.5f".format(intdiv,divr) % divans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
 
// debug templates 
#define debug(x)       cerr<< #x <<" : "<< x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
 
multiset<ll> low,high;
ll low_sum, high_sum;

void balance(){
	while(1){
		int ls = low.size();
		int hs = high.size();
		if(ls == hs || ls == hs+1) break;
		if(ls < hs){
			auto v = high.begin();
			low.insert(*v);
			low_sum += *v;
			high_sum -= *v;
			high.erase(v);
		} else{
			auto v = low.end();
			--v;
			high.insert(*v);
			high_sum += *v;
			low_sum -= *v;
			low.erase(v);
		}
	}
}

// optimal x is median of a's
void solve(){
	ll q; cin >> q;
	ll b_sum = 0;
	FOR(q){
		int n; cin >> n;
		// b value doesnt matter, we want to minimize |x-ai| for all valid i
		if(n==1){
			ll a,b; cin >> a >> b;
			b_sum += b;
			
			if(!low.size()){
				low.insert(a);
				low_sum += a;
			} else{
				auto itr = low.end();
				--itr;
				if(*itr >= a){
					low.insert(a);
					low_sum += a;
				} else{
					high.insert(a);
					high_sum += a;
				}
			}			
			balance();
		} else{
			//debugs(low);
			//debugs(high);
			auto itr = low.end();
			--itr;
			ll median = *itr;
			ll ans = b_sum + median*low.size() - low_sum + high_sum - median*high.size();
			cout << median << " " << ans << '\n';
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	solve();
	return 0;
}
 


Measured memory_bytes: 12964
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
    is>>p.first>>p.second; return is; }
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;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct segtree {
    vector<int> data;
    int size;
    segtree(int n) {
        size=1;
        while(size<n) size<<=1;
        data=vector<int>(size<<1,0);
    }
    void add(int i,int x) {
        i+=size-1;
        data[i]+=x;
        while(i>0) {
            i=(i-1)/2;
            data[i]+=x;
        }
    }
    int getsum(int l,int r) {
        int res=0;
        for(l+=size-1,r+=size-1; l<r; l=(l-1)/2,r=(r-1)/2) {
            if(!(l&1)) res+=data[l++];
            if(!(r&1)) res+=data[--r];
        }
        return res;
    }
};
signed main() {
    int n,q;
    cin>>n>>q;
    segtree seg(n);
    while(q--) {
        int com,x,y;
        cin>>com>>x>>y;
        if(com) {
            cout<<seg.getsum(x-1,y)<<endl;
        } else {
            seg.add(x-1,y);
        }
    }
    return 0;
}

Measured memory_bytes: 4924
#include <stdio.h>

int main()
{
	int input;
	
	scanf("%d",&input);
	
	while(input != 0)
	{
		if(input % 10 == 9)
		{
			printf("Yes");
			return 0;
		}
		
		input = (int)(input/10);
	}
	printf("No");
	return 0;
}


Measured memory_bytes: 128