akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

set<int> si;

int n, m;
int a, b, cost;
int d[110];
bool used[110];

struct edge{
	int to, cost;
	edge(int _to, int _cost) :to(_to), cost(_cost){};
};

vector<edge> G[110];

void prim(int s){
	fill(d, d + 110, INF);
	REP(i, n)used[i] = false;
	d[s] = 0;
	priority_queue< P,vector<P>,greater<P> > que;
	que.push(P(0, s));

	while (!que.empty()){
		P p = que.top(); que.pop();
		int v = p.second;

		if (used[v])continue;

		used[v] = 1;

		for (int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if (used[e.to])continue;
			if (d[e.to] > e.cost){
				d[e.to] = e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main(){
	while (cin >> n >> m&&n + m){
		REP(i, m){
			cin >> a >> b >> cost;
			G[a].push_back(edge(b, cost));
			G[b].push_back(edge(a, cost));
		}
		prim(0);
		int ans = 0;
		REP(i, n){
			ans += d[i];
		}
		cout << ans << endl;
		REP(i, n)G[i].clear();
	}
}

Measured memory_bytes: 1208
N, x = map(int, input().split())
a_list = list(map(int,input().split()))

a_list.sort()

def func():
    cnt = 0
    global x
    for a in a_list:
        if x>=a:
            x -= a
            cnt += 1
        else:
            return cnt
    if x==0:
        return cnt
    else:
        return cnt-1

print(func())

Measured memory_bytes: 38384
#include<iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  int c=0;
  for(int i=1;i<n-1;i++)
  {
    if((a[i]>a[i+1] && a[i]<a[i-1]) || (a[i]<a[i+1] && a[i]>a[i-1]))
    {
      c++;
    }
  }
  cout<<c<<"\n";
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,0)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		parent[b]=a;
		return true;
	}
};
int n,t;
vector<int>G[1<<17];
bool mark[1<<17];
int parent[1<<17];
void dfs(int u,int p,int U,UF&uf)
{
	if(mark[u])U=u;
	else uf.unite(U,u);
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==p)continue;
		dfs(G[u][i],u,U,uf);
	}
}
main()
{
	while(cin>>n>>t,n)
	{
		for(int i=0;i<n;i++)mark[i]=0,G[i].clear();
		UF uf(n);
		int ap[1<<17]={};
		for(int i=1;i<n;i++)
		{
			int a;cin>>a;
			parent[i]=a-1;
			G[a-1].push_back(i);
		}
		vector<pair<bool,int> >q;
		for(int i=0;i<t;i++)
		{
			char c;int a;cin>>c>>a;
			if(c!='M'||!ap[a-1]++)q.push_back(make_pair(c=='M',a-1));
			if(c=='M')mark[a-1]=1;
		}
		mark[0]=1;
		dfs(0,-1,0,uf);
		long ans=0;
		for(int i=q.size();i--;)
		{
			if(q[i].first)
			{
				uf.unite(parent[q[i].second],q[i].second);
			}
			else
			{
				ans+=uf.find(q[i].second)+1;
			}
		}
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 28372
#!/usr/bin/env python3
import sys
from itertools import product

def solve(N: int):
    nine = [9**i for i in range(5,0,-1)]
    six = [6**i for i in range(6,0,-1,)]
    answer = 10**6

    for six_bit in product([0,1,2,3,4,5],repeat = 6):
        tmp = 0
        for i in range(6):
            tmp += six[i]*six_bit[i]

        if tmp > N:
            continue
        
        count = sum(six_bit)
        cur = N-tmp
        for i in range(5):
            syou = cur//nine[i]
            cur%=nine[i]
            count += syou
        else:
            answer = min(answer,count+cur)
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int count = 0;
		int max = 0;
		for(char c : s.toCharArray()) {
			if(c == 'I') {
				count++;
			} else {
				if(max < count) {
					max = count;
				}
				count--;
			}
		}
		if(max < count) {
			max = count;
		}
		System.out.println(max);
	}
}

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

int main(){
    int n, l;
    scanf("%d%d", &n, &l);
    int mn = 10000000, sm = 0, rem = 0;
    for(int i = 1; i <= n; i++){
        sm += (l + i - 1);
        if(mn > abs(l + i - 1)){
            rem = i;
            mn = abs(l + i - 1);
        }
    }
    printf("%d\n", sm - (l + rem - 1));
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <random>

using ll = long long;

//各種nil
template <class T>
constexpr T nil = static_cast<T>(-1);

constexpr int nil_i = nil<int>;
constexpr int nil_ll = nil<ll>;
constexpr double nil_d = nil<double>;

//vector
template <class T>
using vec = std::vector<T>;

void solve()
{
    using namespace std;

    constexpr int inf = 1 << 29;

    int n, m;   //n:払う金額, m:コインの種類
    cin >> n >> m;
    vec<int> c(m);
    for (auto& x : c) cin >> x;

    vec<int> dp(n + 1, inf);    //m円払うときの最小枚数

    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < m; ++j)
            if (i >= c[j])
                dp[i] = min(dp[i], dp[i - c[j]] + 1);

    cout << dp[n] << endl;

    ////dp[i + 1][j]i番目のコインまででj円払える場合の最小枚数
    //vec<vec<int>> dp(m + 1, vec<int>(n + 1, inf));

    ////初期値
    //for (int i = 0; i < m; ++i)
    //    dp[i][0] = 0;

    //for (int i = 0; i < m; ++i)
    //    for (int j = 0; j <= n; ++j)
    //    {
    //        dp[i + 1][j] = dp[i][j];
    //        if (c[i] <= j)
    //            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - c[i]] + 1);
    //    }

    //cout << dp[m][n] << endl;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 3172
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] B = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] C = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Array.Sort(A, (x, y) => y - x);
            Array.Sort(B, (x, y) => y - x);
            Array.Sort(C, (x, y) => y - x);
            long[] a = new long[N];
            long[] b = new long[N];
            for (int j = 0, k = 0; j < N; ++j)
            {
                while (k < N && B[j] < C[k]) { ++k; }
                b[j] = k;
            }
            long sum = 0;
            for (int i = 0, j = 0; i < N; ++i)
            {
                while (j < N && A[i] < B[j]) { sum += b[j++]; }
                a[i] = sum;
            }
            Console.WriteLine(a.Sum());
        }
    }
}


Measured memory_bytes: 40612
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main(void){
    // Here your code !
    long long int a,b,c;
    scanf("%lld %lld %lld",&a,&b,&c);
    if(a%2==1 && b%2==1 && c%2==1){
        int buf = max({a,b,c});
        long long int buf2;
        if(buf == a){
            buf2 = b*c;
        }else if(buf==b){
            buf2 = c*a;
        }else{
            buf2 = a*b;
        }
        printf("%lld",buf2);
    }else{
        printf("0");
    }
    
}


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

using namespace std;

int main(){
    long long A,B;
    long long V,W;
    long long T;

    cin >> A >> V >> B >> W >> T;
    long long dist = abs(B-A);
    long long diffSpeed = V-W;

    if(diffSpeed <= 0)cout << "NO" << endl;
    else{
        int turn;
        if(dist % diffSpeed == 0)turn = dist/diffSpeed;
        else turn = dist/diffSpeed + 1;

        if(turn <= T)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#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 1e9
#define ALL(v) v.begin(), v.end()

using namespace std;
typedef long long ll;

int main(){
    // read in integer 
    ll a, b, c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N, flag=0;
  cin >> N;
  for(int i=0; i<3; i++){
    if(N%10 == 7) flag = 1;
    N/=10;
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3636
K = input()
N = len(K)

KK = int(input())
dp = [[[0]*(5) for _ in range(2)] for _ in range(N+1)]
dp[0][0][0] = 1

for i, s in enumerate(K):
    a = ord(s)-48
    for j in range(4):
        for k in range(10):
            p = j+1 if k else j
            dp[i+1][1][p] += dp[i][1][j]
            if k<a:
                dp[i+1][1][p] += dp[i][0][j]

    for j in range(4):
        p = j+1 if a else j
        dp[i+1][0][p] += dp[i][0][j]

print(dp[N][0][KK]+dp[N][1][KK])

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

     public static void main(String []args){
        Scanner scan = new Scanner(System.in);
        ArrayList<Integer> a = new ArrayList<>();
        a.add(scan.nextInt());
        a.add(scan.nextInt());
        a.add(scan.nextInt());
        int n =scan.nextInt();
        int x = Collections.max(a) ;
        for(int i = 0 ; i<n ;i++){
        	x = x*2 ;
        }
       
        
        a.remove(Collections.max(a));
        a.add(x);
        int sum = 0;
        for(Integer u : a){
            sum+=u;
        }
        System.out.println(sum);
        
        
        
      
     }
}

Measured memory_bytes: 22868
N = int(input())
A = []
B = []

for _ in range(N):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)

A.sort()
B.sort()

if N%2==0:
  mA = (A[N//2-1]+A[N//2])/2
  mB = (B[N//2-1]+B[N//2])/2
  print(int((mB - mA)*2 + 1))
else:
  mA = A[N//2]
  mB = B[N//2]
  print(mB-mA+1)

Measured memory_bytes: 104544
#include <iostream>
#include <vector>
#include <cstring>

int test[1000];
std::vector<int> product[300];
bool isOK[300];

inline int popCount(int bits) {
	int ret = 0;
	while (bits != 0) {
		++ret;
		bits &= bits - 1;
	}
	return ret;
}

int main() {
	int a, b, c, n;
	while (std::cin >> a >> b >> c, a + b + c != 0) {
		std::cin >> n;

		for (int i = 0; i < n; ++i) {
			int x, y, z, res;
			std::cin >> x >> y >> z >> res;

			if (res) {
				isOK[x - 1] = isOK[y - 1] = isOK[z - 1] = true;
				continue;
			}

			test[i] = 7;
			product[x - 1].push_back(i);
			product[y - 1].push_back(i);
			product[z - 1].push_back(i);
		}

		for (int i = 0; i < a + b + c; ++i) {
			if (isOK[i]) {
				int which = (i < a ? 0 : i < a + b ? 1 : 2);
				for (int idx : product[i])
					test[idx] &= ~(1 << which);
			}
		}

		for (int i = 0; i < a + b + c; ++i) {
			if (isOK[i]) {
				std::cout << 1 << std::endl;
				continue;
			}

			bool isInvalid = false;
			for (int idx : product[i]) {
				if (popCount(test[idx]) == 1) {
					isInvalid = true;
					break;
				}
			}

			std::cout << (isInvalid ? 0 : 2) << std::endl;
		}

		for (auto&& p : product)
			p.clear();

		std::memset(isOK, 0, sizeof(isOK));
	}
}

Measured memory_bytes: 3084
(function() {
	var
		S = parseInt(require('fs').readFileSync('/dev/stdin').toString()),
		date = new Date(S * 1000),
		str = "";
	str = str + String(date.getUTCHours());
	str = str + ":";
	str = str + String(date.getUTCMinutes());
	str = str + ":";
	str = str + String(date.getUTCSeconds());
	console.log(str);
}) ();

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

int main() {
	int N, a, maxi = -1, mini = 1001;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		maxi = max(a, maxi);
		mini = min(mini, a);
	}
	cout << maxi - mini;
}


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



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

    int ans = 0;
  for(int i = 1;i <= N;i++) {
      int num = 0;
      int cpy = i;
      while(cpy > 0) {
          cpy /= 10;
          num++;
      }

      if(num % 2 != 0) ans++;
  }

  cout << ans << endl;


}


Measured memory_bytes: 256
use std::io;


/// https://beta.atcoder.jp/contests/abc101/tasks/abc101_b
/// https://beta.atcoder.jp/contests/abc080/tasks/abc080_b と同じ
fn main() {
    let n = read_one::<usize>();
    let mut x = n;
    let mut sum = 0;
    while x > 0 {
        sum += x % 10;
        x = x / 10;
    }
    if n % sum == 0 { println!("Yes"); }
    else { println!("No"); }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
N = int(input())
ans = 0
l = [N,0]
a = 1

while l[0] != 0:
    if l[1] == 0:
        a += 1
        l = [N//a, N%a]
    elif l[0] == l[1]:
        ans += a
        a += 2 
        l = [N//a, N%a]
    else:
        if l[1] % l[0] == 0:
            a += l[1] // l[0] - 1
            ans += a
            a += 2
            l = [N//a, N%a]
        else:
            a += l[1] // l[0] + 1
            l = [N//a, N%a]

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
using namespace std;
int vis[100];
ll sum[200010];
const ll mod=1e9+7;
int main()
{

    for(int i=1;i<=200005;i++)
    {
        sum[i]=(sum[i-1]+i);
    }

    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll ans=0;
    for(ll i=k-1;i<=n;i++)
    {
        ans=(ans+sum[n]-sum[n-i-1]-sum[i]+1)%mod;
//        if(i==1||i==n)ans=(ans+n+1)%mod;
//        else if(i==n+1)ans=(ans+1)%mod;
//        else
//        {
//            int x=min(i,n+1-i);
//            ans=(ans+(C[i]-sum[n+x-4]+mod)%mod)%mod;
//        }

        //printf("%lld\n",ans);

    }
    printf("%lld\n",ans);
//    int T;
//    scanf("%d",&T);
//    while(T--)
//    {
//        int n;
//        scanf("%d",&n);
//        for(int i=1;i<=n;i++)
//        {
//            scanf("%d",&a[i]);
//        }
//    }
}


Measured memory_bytes: 5376
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int A,B,K;
	scanf("%d %d %d",&A,&B,&K);
	for(int i=A;i<=min(A+K-1,B);i++)
		printf("%d\n",i);
	for(int i=max(A+K,B-K+1);i<=B;i++)
		printf("%d\n",i);
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include <random>
//std::random_device seed_gen;
//std::mt19937 engine(seed_gen());

unsigned long xor128() {
  static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned long t=(x^(x<<11));
  x=y; y=z; z=w;
  return (w=(w^(w>>19))^(t^(t>>8)));
}

int const INF = 1e9;
int const M = 3e5;

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int D; std::cin >> D;
  int c[26];
  for(int& ci: c) std::cin >> ci;
  std::vector<std::array<int,26>> s(D);
  for(int d = 0; d < D; ++d) {
    for(int& si: s[d]) std::cin >> si;
  }
  
  // greedy
  std::vector<int> t(D);
  int ans = 0;
  int last[26];
  std::fill_n(last, 26, -1);
  for(int d = 0; d < D; ++d) {
    int ma = -INF;
    t[d] = 0;
    for(int T = 1; T <= 26; ++T) {
      int cur = s[d][T-1];
      int sv = last[T-1];
      last[T-1] = d;
      for(int cx = 0; cx < 26; ++cx) {
        cur -= (d-last[cx])*c[cx];
      }
      last[T-1] = sv;
      if(cur > ma) { ma = cur; t[d] = T; }
    }
    ans += ma;
    last[t[d]-1] = d;
  }
  
  auto score = [&]()->int {
    int ans = 0;
    int last[26];
    std::fill_n(last, 26, -1);
    for(int d = 0; d < D; ++d) {
      ans += s[d][t[d]-1];
      last[t[d]-1] = d;
      for(int cx = 0; cx < 26; ++cx) {
        ans -= (d-last[cx])*c[cx];
      }
    }
    return ans;
  };
  
  // modify
  for(int m = 0; m < M; ++m) {
    //int d = dD(engine), T = dT(engine);
    int d = xor128()%365, T = xor128()%26; ++T;
    int sv = t[d];
    t[d] = T;
    int new_ans = score();
    if(new_ans > ans) ans = new_ans;
    else t[d] = sv;
  }
  for(int ti: t) std::cout << ti << "\n";
  
  return 0;
}


Measured memory_bytes: 3688
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i

count = 0
(a + 1).times do |i|
  (b + 1).times do |j|
    (c + 1).times do |k|
      count += 1 if x == (i*500 + j*100 + k*50)
    end
  end
end

print count

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

int main ()
{
	typedef long long ll;
	ll a,b; cin>>a>>b;
	
	if(a%2!=b%2){
		cout<<"IMPOSSIBLE"<<endl;
	}
	
	else 
	cout<<(a+b)/2<<endl;
	


}



Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;
typedef long long lint;

int dp[1111][1111];

void chmin(int& x, const int y) {
    x = min(x, y);
}

int main() {
    string X, Y;
    cin >> X >> Y;
    const int N = X.size(), M = Y.size();
    const int INF = 1e9+7;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            // i-1 番目は削除
            if (i > 0) chmin(dp[i][j], dp[i-1][j] + 1);
            // j-1 番目は挿入で対応
            if (j > 0) chmin(dp[i][j], dp[i][j-1] + 1);
            if (i > 0 && j > 0) {
                // 同じなのでスルー
                if (X[i-1] == Y[j-1]) chmin(dp[i][j], dp[i-1][j-1]);
                // 置換
                else chmin(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
    }
    cout << dp[N][M] << endl;
    return 0;
}


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

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


int main(){
    
    int n,k;
    int a[100];
    cin >> n >> k;
    rep(i,n) cin >> a[i];

    sort(a,a + n, greater<int>());

    int sum = 0;
    for(int i=0;i<k;i++){
        sum += a[i];
    }    

    cout << sum << endl;

    return 0;
};



Measured memory_bytes: 256
import bisect
n = int(input())
s = input()
R = []
G = []
B = []
for i in range(n):
  if s[i] == 'R':
    R.append(i)
  elif s[i] == 'G':
    G.append(i)
  else:
    B.append(i)
res = 0
for i in range(n):
  if s[i] == 'R':
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(B, G[j])
      res += len(B) - y
      sss.add(2*G[j]-i)
    res -= len(sss & set(B))
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(G, B[j])
      res += len(G) - y
      sss.add(2*B[j]-i)
    res -= len(sss & set(G))
  elif s[i] == 'G':
    x = bisect.bisect_left(B, i)
    sss = set()
    for j in range(x, len(B)):
      y = bisect.bisect_left(R, B[j])
      res += len(R) - y
      sss.add(2*B[j]-i)
    res -= len(sss & set(R))
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(B, R[j])
      res += len(B) - y
      sss.add(2*R[j]-i)
    res -= len(sss & set(B))
  else:
    x = bisect.bisect_left(G, i)
    sss = set()
    for j in range(x, len(G)):
      y = bisect.bisect_left(R, G[j])
      res += len(R) - y
      sss.add(2*G[j]-i)
    res -= len(sss & set(R))
    x = bisect.bisect_left(R, i)
    sss = set()
    for j in range(x, len(R)):
      y = bisect.bisect_left(G, R[j])
      res += len(G) - y
      sss.add(2*R[j] - i)
    res -= len(sss & set(G))
print(res)


Measured memory_bytes: 95756
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAXN = (int) 1e5 + 10;
const int INF = (int) 0x3f3f3f3f;
typedef long long LL;

int n,k;
int a[MAXN];

bool is_judge(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]==x) return true;
        if(a[mid]<x) l=mid+1;
        else r=mid-1;
    }
    return false;
}

void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int q; scanf("%d",&q);
    int ans=0;
    for(int i=1;i<=q;i++){
        int x; scanf("%d",&x);
        if(is_judge(x)) ans++;
    }
    printf("%d\n",ans);
}

int main(){
    work();
    return 0;
}





Measured memory_bytes: 3128
#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
};

#endif // ___CLASS_MODINT

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
using modulo = modint<1000000007>;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<int> X(N), Y(M);
	for (int i = 0; i < N; ++i) cin >> X[i];
	for (int i = 0; i < M; ++i) cin >> Y[i];
	vector<int> L, R;
	int ptr = 0;
	for (int i = 0; i < N; ++i) {
		while (ptr != M && Y[ptr] < X[i]) ++ptr;
		if (1 <= ptr && ptr < M) {
			L.push_back(X[i] - Y[ptr - 1]);
			R.push_back(Y[ptr] - X[i]);
		}
	}
	vector<int> CL(L), CR(R);
	sort(CL.begin(), CL.end());
	CL.erase(unique(CL.begin(), CL.end()), CL.end());
	sort(CR.begin(), CR.end());
	CR.erase(unique(CR.begin(), CR.end()), CR.end());
	int S = L.size(), SL = CL.size(), SR = CR.size();
	vector<pair<int, int> > seg;
	for (int i = 0; i < S; ++i) {
		int posl = lower_bound(CL.begin(), CL.end(), L[i]) - CL.begin();
		int posr = lower_bound(CR.begin(), CR.end(), R[i]) - CR.begin();
		seg.push_back(make_pair(posr, -posl));
	}
	sort(seg.begin(), seg.end());
	seg.erase(unique(seg.begin(), seg.end()), seg.end());
	S = seg.size();
	vector<modulo> bit(SL + 2);
	function<void(int, modulo)> add = [&](int pos, modulo val) {
		for (int i = pos + 1; i <= SL + 1; i += i & (-i)) {
			bit[i] += val;
		}
	};
	function<modulo(int)> sum = [&](int pos) {
		modulo ans = 0;
		for (int i = pos; i >= 1; i -= i & (-i)) {
			ans += bit[i];
		}
		return ans;
	};
	add(0, 1);
	for (int i = 0; i < S; ++i) {
		modulo res = sum(-seg[i].second + 1);
		add(-seg[i].second + 1, res);
	}
	modulo ans = sum(SL + 1);
	cout << ans.get() << endl;
	return 0;
}

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

typedef long long ll;
#define pb push_back

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,x,t;
    cin>>n>>x>>t;
    if(n%x!=0)
    cout<<(n/x + 1)*t;
    else
    cout<<(n/x)*t;
    return 0;
}


Measured memory_bytes: 3644
import java.lang.*;
import java.io.*;
import java.util.*;


public class Main {
	
	public static void main(String[] args) throws java.lang.Exception {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(in, out);
		out.close();
	}
}

class TaskA {
	
	public void solve(InputReader in, PrintWriter out) {
		int n = in.nextInt(), m = 0;
		int[] a = new int[n+1];
		int[] b = new int[n];
		
		for (int i=1; i<=n; ++i)
			a[i] = in.nextInt();
		
		if (n%2 == 1) {
			for (int i=n; i>0; i-=2) {
				b[m++] = a[i];
			}
			for (int i=2; i<=n; i+=2) {
				b[m++] = a[i];
			}
		} else {
			for (int i=n; i>0; i-=2) {
				b[m++] = a[i];
			}
			for (int i=1; i<=n; i+=2) {
				b[m++] = a[i];
			}
		}
		
		for (int i=0; i<n; ++i) {
			if (i == n-1)
				out.println(b[i]);
			else
				out.print(b[i] + " ");
		}
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;
	
	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}
	
	public String next() {
		while (tokenizer==null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	
	public int nextInt() {
		return Integer.parseInt(next());
	}
	
	public long nextLong() {
		return Long.parseLong(next());
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


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

int main(){
  int n; cin >> n;
  vector<int> a(n); for(int i = 0; i < n; i++) cin >> a.at(i);
  sort(a.begin(), a.end());
  cout << a.at(n-1) - a.at(0) << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf = 1e9+7;

int a, b, c, N, K, M;
string s;
vector<int> vt;
map<int,int> m;
int sum;
int main() {
    cin>>N>>K;
    REP(i,0,N){
        int A;
        cin>>A;
        m[A]++;
    }
    for(auto d:m){
        vt.push_back(d.second);
    }
    sort(vt.begin(),vt.end());
    reverse(vt.begin(),vt.end());
    if(vt.size()<=K) p(0);
    else {
        REP(i, 0, K) {
            sum += vt[i];
        }
        p(N - sum);
    }
    return 0;
}

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

using namespace std;

int main()
{
  int N;
  scanf("%d", &N);
  
  set<int> s;
  vector< pair<int, int> > v;
  
  for (int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    v.push_back(make_pair(x, i));
  }
  
  sort(v.begin(), v.end());
  
  s.insert(-1);
  s.insert(N);
  
  long long ans = 0;
  for (int i = 0; i < N; i++) {
    auto it = s.lower_bound(v[i].second);
    int r = *it;
    int l = *(--it);
    ans += (long long)(i + 1) * (v[i].second - l) * (r - v[i].second);
    s.insert(v[i].second);
  }
  
  printf("%lld\n", ans);
  
  return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	string s;
	vector<int> alp(3,0);

	cin >> s;
	for(auto x: s)
		alp[x-'a']++;
	sort(BE(alp));
	int mini = alp[0];
	alp[0] -= mini;
	alp[1] -= mini;
	alp[2] -= mini;

	if(alp[2] >= 2)
		cout << "NO" << endl;
	else
		cout << "YES" << endl;

	return 0;
}

Measured memory_bytes: 512
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        mut n: i64,
    }
    let mut res = 0;
    for i in 2.. {
        if i * i > n {
            break;
        }
        if n % i == 0 {
            let mut r = 0;
            while n % i == 0 {
                r += 1;
                n /= i;
            }
            for j in 1.. {
                if r >= j {
                    r -= j;
                    res += 1;
                } else {
                    break;
                }
            }
        }
    }
    if n != 1 {
        res += 1;
    }
    println!("{}", res);
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
#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()
using namespace std;
typedef long long int ll;
int main()
{
  int n;
  scanf("%d",&n);
  int h[n];
  REP(i,n) scanf("%d",&h[i]);
  int dp[n+1];
  dp[0] = 0;
  dp[1] = abs(h[1]-h[0]);
  FOR(i,2,n){
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout << dp[n-1] << endl;
  
}

Measured memory_bytes: 1024
/**
*   author:  akifpathan
*   created: Saturday 19.09.2020 06:03:05 PM
**/

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

#ifdef LOCAL
#include "debug.h"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(x...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using ordered_set= tree<T, null_type, 
		less<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> 		
using ordered_mset= tree<T, null_type, 
		less_equal<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
		
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

void solve()
{
	string x;
	cin>>x;
	
	if(x.back()=='s') x+="es";
	else x+="s";
	
	cout<<x;
}		

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int testcase=1;
	//cin>>testcase;
	
	for(int i=1;i<=testcase;i++)
	{
		//cout<<"Case "<<i<<": ";
		solve();
	}
	
	#ifdef LOCAL
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	#endif
	
	
	return 0;
}



Measured memory_bytes: 3656
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

const R: u64 = 1000000007;

fn main() {
    let n: usize = read();

    let mut dp: Vec<Vec<Vec<Vec<u64>>>> = vec![vec![vec![vec![1; 4]; 4]; 4]; 101];
    dp[3][0][2][1] = 0;
    dp[3][2][0][1] = 0;
    dp[3][0][1][2] = 0;

    for i in 4..(n + 1) {
        for q in 0..4 {
            for r in 0..4 {
                for s in 0..4 {
                    if q == 0 && r == 2 && s == 1 {
                        dp[i][q][r][s] = 0;
                    } else if q == 2 && r == 0 && s == 1 {
                        dp[i][q][r][s] = 0;
                    } else if q == 0 && r == 1 && s == 2 {
                        dp[i][q][r][s] = 0;
                    } else if r == 2 && s == 1 || q == 2 && s == 1 {
                        dp[i][q][r][s] =
                            (dp[i - 1][1][q][r] + dp[i - 1][2][q][r] + dp[i - 1][3][q][r]) % R;
                    } else {
                        dp[i][q][r][s] = (dp[i - 1][0][q][r]
                            + dp[i - 1][1][q][r]
                            + dp[i - 1][2][q][r]
                            + dp[i - 1][3][q][r])
                            % R;
                    }
                }
            }
        }
    }

    let mut ans: u64 = 0;
    for q in 0..4 {
        for r in 0..4 {
            for s in 0..4 {
                ans = (ans + dp[n][q][r][s]) % R;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> r(n);
  for(ll i = 0; i<n; i++)cin >> r[i];
  sort(r.begin(),r.end());
  ll num = 0;
  for(ll i = n-1-k; i>=0; i--){
  	num+=r[i];
  }
  cout << num << endl;
}


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

int main() {
    int h, w;
    cin >> h >> w;

    string s[h];
    for (int i = 0; i < h; i++) cin >> s[i];

    for (int i = 0; i < h; i++) {
        cout << s[i] << endl;
        cout << s[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import core.bitop, std.bitmanip;
import core.checkedint;
import std.algorithm, std.functional, std.meta;
import std.array, std.container;
import std.bigint;
import std.conv;
import std.math, std.numeric;
import std.range, std.range.interfaces;
import std.stdio, std.string;
import std.ascii, std.typecons;

void main()
{
    int n;
    readf("%s", &n);
    readln;

    auto arr = readln.chomp.split.map!(to!int).array;
    
    long ans = arr.sum(0L);
    
    int[int] cnt;
    foreach (e; arr) { cnt[e] += 1; }
    
    int q;
    readf("%s", &q);
    readln;
    
    while (q--) {
        int b, c;
        readf("%s %s", &b, &c);
        readln;
        
        int diff = c - b;
        int elems = cnt.get(b, 0);
        
        long change = diff.to!long * elems;
        
        cnt[b] = 0;
        cnt[c] += elems;
        
        ans += change;
        
        ans.writeln;
    }
}

Measured memory_bytes: 11452
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  int n;
  cin >> n;
  cout << (100000-n)%1000 << endl;
}


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

int main()
{
    int d, t, s;
    std::cin >> d >> t >> s;
    if (1.0 * d / t <= s)
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define maxn 110
using namespace std;
typedef double ldb;
const ldb eps=1e-7;
const ldb pi=acos(-1.0);
ldb nx[maxn],ny[maxn];
int n;
int dcmp(ldb d){
	return fabs(d)<eps?0:(d<0?-1:1);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%lf%lf",&nx[i],&ny[i]);
	for(int i=1;i<=n;++i){
		ldb mn=0,mx=pi;
		int id=(i==1?2:1);
		ldb ang=atan2(ny[id]-ny[i],nx[id]-nx[i]);
		for(int j=1;j<=n;++j)if(i!=j&&j!=id){
			ldb ang1=atan2(ny[j]-ny[i],nx[j]-nx[i]);
			ldb a=ang-ang1;
			if(dcmp(a-pi)==0||dcmp(a+pi)==0)mn=1e20;
			if(dcmp(a-pi)>0)a-=2*pi;
			else if(dcmp(-pi-a)>0)a+=2*pi;
			if(dcmp(a)<0)mn=max(mn,-a);
			else mx=min(mx,pi-a);
		}
//		printf("[%.3lf,%.3lf]",mn,mx);
		if(dcmp(mn-mx)>=0)puts("0.0");
		else printf("%.10lf\n",(mx-mn)/(2*pi));
	} 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
ll N, M;
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;

	ll ans = 0;
	ans = min(N, M / 2);

	N -= ans;
	M -= ans * 2;

	ans += M / 4;

	cout << ans << endl;
}

Measured memory_bytes: 764
n,m = map(int,input().split())
student = [[0]*2 for _ in range(n)]
check = [[0]*2 for _ in range(m)]
for i in range(n):
    student[i][0],student[i][1] = map(int,input().split())
for i in range(m):
    check[i][0],check[i][1] = map(int, input().split())

INF = 10**9
for i in range(n):
    zantei = INF
    ans = 1
    for j in range(m):
        dum = abs(student[i][0] - check[j][0]) + abs(student[i][1] - check[j][1])
        if dum < zantei:
            ans = j+1
            zantei = dum
    print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
 
int n, A[100000];

int judge(int i, int m) {
	if (m == 0) {
		return 1;
	}
	if (i >= n) {
		return 0;
	}

	int res = judge(i + 1, m) || judge(i + 1, m - A[i]);

	return res;
}

int main(void)
{
	int q, m[100000];
	int i, j, k, l = 0;
	int min, max, mid;
	int count = 0;

	scanf("%d", &n);

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

	scanf("%d", &q);

	for (i = 0;i < q;i++) {
		scanf("%d", &m[i]);
	}

	for (i = 0;i < q;i++) {
		if (judge(0, m[i])) {
			printf("yes\n");
		}
		else
		{
			printf("no\n");
		}

	}
	return 0;
}
 



Measured memory_bytes: 1992
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
  int N;
  cin>>N;
  vector<int> l(N, INT_MAX);
  for (int i=0;i<N;++i) {
    int a;
    cin>>a;
    int pos = distance(l.begin(),lower_bound(l.begin(),l.end(),a));
    l[pos] = a;
  }

  int idx = l.size();
  while(l[--idx] == INT_MAX);
  cout<<idx+1<<endl;

  return 0;
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,a[N],b[N],c[N],ma[N*4],mi[N*4];
vector<int>g;
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void build(int nod,int l,int r)
{
	if(l==r)
	{
		ma[nod]=mi[nod]=a[l]=read();
		return;
	}
	int mid=(l+r)/2;
	build(nod*2,l,mid);
	build(nod*2+1,mid+1,r);
	ma[nod]=max(ma[nod*2],ma[nod*2+1]);
	mi[nod]=min(mi[nod*2],mi[nod*2+1]);
}
int find1(int nod,int l,int r,int L,int R)
{
	if(l==L&&r==R)return ma[nod];
	int mid=(l+r)/2;
	if(R<=mid)return find1(nod*2,l,mid,L,R);
	else if(L>mid)return find1(nod*2+1,mid+1,r,L,R);
	else return max(find1(nod*2,l,mid,L,mid),find1(nod*2+1,mid+1,r,mid+1,R));
}
int find2(int nod,int l,int r,int L,int R)
{
	if(l==L&&r==R)return mi[nod];
	int mid=(l+r)/2;
	if(R<=mid)return find2(nod*2,l,mid,L,R);
	else if(L>mid)return find2(nod*2+1,mid+1,r,L,R);
	else return min(find2(nod*2,l,mid,L,mid),find2(nod*2+1,mid+1,r,mid+1,R));
}
//int find(int nod,int l,int r,int L,int R)
//{
//	if(l==L&&r==R)return ma[nod];
//	int mid=(l+r)/2;
//	if(R<=mid)return find(nod*2,l,mid,L,R);
//	else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
//	else return max(find(nod*2,l,mid,L,mid),find(nod*2+1,mid+1,r,mid+1,R));
//}
signed main()
{
	n=read();m=read();
	build(1,1,n);
	int ans=1;
	c[1]=1;
	for(int i=2;i<=n-m+1;i++)
	{
		ans++;
		int x=find1(1,1,n,i,i+m-2),y=find2(1,1,n,i,i+m-2);
		if(a[i+m-1]>=x&&a[i-1]<=y)ans--;
		else c[i]=1;
//		cout<<ans<<endl;
	}
//	cout<<ans<<endl;
	for(int i=1,j;i<=n;i=j+1)
	{
		j=i;
		while(j+1<=n&&a[j+1]>=a[j])j++;
		if(j-i+2-m>0)
		{
			for(int p=i;p+m-1<=j;p++)
				b[p]=1;
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(b[i]&&c[i])
		{
			ans-=sum;
			sum=0;
		}
		if(i>=m&&b[i-m+1]&&c[i-m+1])sum++;
	}
//	k=k/2;
	cout<<ans;
}
/*
6 2
0 3 1 4 2 5
*/

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

int fun(int x){
    int ans = 0;
    for(int i = 1;;i++){
        ans += i;
        if(ans == x) return i;
        else if(x < ans) return i-1;
    }
}

int main() {
    ll n; cin >> n;
    ll half = sqrt(n);
    int ans = 0;
    if(n == 1){
        cout << 0 << endl; return 0;
    }
    for(int i = 2; i < half; i++){
        int a = 0;
        while(n%i==0){
            a++;
            n /= i;
        }
        ans += fun(a);
    }
    if(n > 1) cout << ans+1 << endl;
    else cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3648
import scala.io.StdIn.readLine
import scala.io.StdIn.readInt
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  val N = sc.nextInt
  val K = sc.nextInt
  var l = new Array[Int](N)
  for {i <- 1 to K}{
    val d = sc.nextInt
    for(j <- 1 to d){
      val t = sc.nextInt
      l(t-1) = 1
    }
  }
  println(l.count(a=>a==0))

}

Measured memory_bytes: 57192
// D - Lazy Faith

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

const ll INF = 1e11;
ll s[100002];
ll t[100002];

int A, B, Q;

ll calc(ll x) {
	int l, r;
	r = lower_bound(s, s+A+2, x) - s;
	l = r - 1;
	ll s_l = s[l];
	ll s_r = s[r];

	r = lower_bound(t, t+B+2, x) - t;
	l = r - 1;
	ll t_l = t[l];
	ll t_r = t[r];

	ll result = INF;

	result = min(result, abs(x - s_l) + abs(s_l - t_l));
	result = min(result, abs(x - t_l) + abs(t_l - s_l));
	result = min(result, abs(x - s_r) + abs(s_r - t_r));
	result = min(result, abs(x - t_r) + abs(t_r - s_r));
	result = min(result, abs(x - s_l) + abs(s_l - t_r));
	result = min(result, abs(x - t_l) + abs(t_l - s_r));
	result = min(result, abs(x - s_r) + abs(s_r - t_l));
	result = min(result, abs(x - t_r) + abs(t_r - s_l));

	return result;
}

int main() {

	cin >> A >> B >> Q;

	s[0] = -INF;
	s[A+1] = INF;
	for (int i=1; i<=A; i++) {
		cin >> s[i];
	}

	t[0] = -INF;
	t[B+1] = INF;
	for (int i=1; i<=B; i++) {
		cin >> t[i];
	}

	vector<ll> ans_list;

	for (int i=0; i<Q; i++) {
		ll x;
		cin >> x;

		ans_list.push_back(calc(x));
	}

	for (ll ans : ans_list) {
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 5880
import java.util.*;

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

        int N = sc.nextInt();
        String S = sc.next();

        String[] strArray = S.split("");

        int ans = 0;

        for (int i = 0; i < strArray.length - 2; i++) {
            if (strArray[i].equals("A")) {
                if (strArray[i + 1].equals("B")) {
                    if (strArray[i + 2].equals("C")) {
                        ans += 1;
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 24020
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	ll s= 0;
	s += min(k, a);
	k -= min(k, a);
	k -= min(k, b);
	s -= min(k, c);
	cout << s;





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
string s;
int cnt;
int main() {
	cin >> s;
	if (s[0] == 'A') cnt++;
	if (s[1] == 'A') cnt++;
	if (s[2] == 'A') cnt++;
	if (cnt == 0 || cnt == 3) {
		puts("No");
	} else {
		puts("Yes");
	}
	return 0;
} 

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
X = [A[0]]
for i in range(1, N):
  if A[i] != A[i-1]:
    X.append(A[i])
S = []
n = len(X)
if n==1:
  print(1000)
else:
  status = 0
  result = 1000
  now_m = 1000
  k = 0
  if X[0]<X[1]:
    S.append(0)
  for i in range(1, n-1):
    if (X[i-1]<X[i] and X[i]>X[i+1]) or (X[i-1]>X[i] and X[i]<X[i+1]):
      S.append(i)
  if X[n-2]<X[n-1]:
    S.append(n-1)
  for s in S:
    if status==0:
        k = now_m//X[s]
        result = max(result, now_m)
        now_m -= k*X[s]
        status = 1
    else:
        now_m += k*X[s]
        result = max(result, now_m)
        k = 0
        status = 0
  print(result)

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

int main(){
    ll x;
    int r,d;
    cin >> r >> d >> x;

    rep(i,10){
        x=r*x-d;
        cout << x << endl;
    }



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <string>
#include <map>
#include <list>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define LargeNum 1000000007

int main(){
    string S;
    cin >> S;
    if (S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}


Measured memory_bytes: 3596
N=int(input())
S=input()
a=S[1:].count('E')
ans=a
t=1
while t<=N-1:
    if S[t-1]=='W':
        a+=1
    if S[t]=='E':
        a-=1
    ans=min(ans,a)
    t+=1
print(ans)

Measured memory_bytes: 3700
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll m;
    cin >> m;
    ll d[200003], c[200003];
    ll k = 0, s = 0;
    for(int i = 0; i < m; i++){
        cin >> d[i] >> c[i];
        k += c[i];
        s += d[i] * c[i];
    }
    cout << k - 1 + (s - 1) / 9 << endl;
}

Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
	char s[1000];

	while(gets(s) != NULL){

		int len = strlen(s);

		for(int i = 0;i < len;i++){
			if(s[i] >= 'a' && s[i] <= 'z'){
				s[i] -= 32;
			}
		}
	cout << s << endl;
	}
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define INF 1000000
using ll = long long;

void chmin(int &a, int b){ if(a>b) a = b;}//aを短い方にする。

int N,A,B,C;
vector<int> L;

//再起
int rec(int i, int a, int b, int c){
  if(i == N){
    if(!a || !b || !c)return INF;
    return abs(a - A) + abs(b - B) + abs(c - C);
  }

  //今ある竹を採用しない。
  int res = rec(i+1,a,b,c);
  //A,B,Cそれぞれに採用
  chmin(res,rec(i+1,a+L.at(i),b,c)+(a?10:0));
  chmin(res,rec(i+1,a,b+L.at(i),c)+(b?10:0));
  chmin(res,rec(i+1,a,b,c+L.at(i))+(c?10:0));

  return res;
}

int main(){
  cin >> N >> A >> B >> C;
  L.resize(N);
  rep(i,N)cin >> L.at(i);

  cout<<rec(0,0,0,0)<<endl;
  return 0;
}

Measured memory_bytes: 256
def main42():
    data = input()
    nagasa = len(data)
    result = 10000
    for i in range(0,nagasa-2,1):
        kari = data[i:i+3]
        num = int(kari)
        if result > abs(num - 753):
            result = abs(num - 753)
    print(result)

if __name__ == "__main__":
    main42()

Measured memory_bytes: 3060