akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
// const int MAXMEM = 200 * 1000 * 1024;
// char _memory[MAXMEM];
// size_t _ptr = 0;
// void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
// void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 100228;



int n;
int x[MAXN], l[MAXN];



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 // 	read(FILENAME);     
    cin >> n;
    vector<pair<int, int> > st;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> l[i];
        st.pb({x[i] + l[i], x[i] - l[i]});
    }
    sort(all(st));
    int b = -2000000001;
    int cnt = 0;
    for (auto x: st) {
        swap(x.first, x.second);
        if (x.first >= b) {
            b = x.second;
            cnt++;
        }
    }
    cout << cnt << '\n';
    return 0;
}            	


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

#define ull unsigned long long
#define ul unsigned long
#define ll long long
#define size_t long long
// sort(&a[0], &a[4], [](auto& x, auto& y){return x[0] < y[0];});
//accumulate(&arr2[n], &arr2[m-1], 0);
using namespace std;

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

  ll A,B,C,D; std::cin >> A >> B >> C >> D;
  ll x = ((A-1)/C*C);
  ll y = ((A-1)/D*D);
  ll CD = C*D/__gcd(C,D);
  ll xy = ((A-1)/CD*CD);
  // std::cout << x << " " << y << " " << CD << " " << xy << '\n';
  std::cout << B - A + 1 - ((B-x)/C + (B-y)/D - (B-xy)/CD) << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
    int n;
    cin>>n;
    ll b[n-1],ans;
    rep(i,n-1){
        cin>>b[i];
    }
    ans=b[0]+b[n-2];
    rep(i,n-2){
        ans+=min(b[i],b[i+1]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		int MAX = 200000;
		int[] R = new int[MAX];
		
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		for(int i = 0; i < n; i++){
			R[i] = scan.nextInt();
		}
		
		int maxv = -2000000000; //???????°??????????????????????????¨????
		int minv = R[0];
		
		for(int i = 1; i < n; i++){ //????????§??????R[i]?????????????????°???????????????
			maxv = R[i] - minv > maxv ? R[i] - minv : maxv; //?????§????????´??°
			minv = R[i] < minv ? R[i] : minv; //???????????§???????°?????????????????????????
		}
		System.out.println(maxv);
	}
}

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

int main() {
  string S, T;
  cin >> S >> T;
  int N = T.size();
  char c = T.at(N-1);
  if(S + c ==T){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;

vi pp(1e5 + 10);

inline int lowbit(int k)
{
    return k & -k;
}

void update(vi &v, int pos, int val)
{
    int len = v.size();
    while (pos < len)
    {
        //change behavior here
        v[pos] += val;
        pos += lowbit(pos);
    }
}

int getVal(vi &v, int pos)
{
    int res = 0;
    while (pos)
    {
        res += v[pos];
        pos -= lowbit(pos);
    }
    return res;
}

const int SIZE = 1e5 + 10;

bool notprime[SIZE] = {false};

void init()
{
    notprime[0] = notprime[1] = true;
    for (int i = 2; i < SIZE; i++)
        if (!notprime[i])
        {
            if (i > SIZE / i)
                continue;
            for (int j = i * i; j < SIZE; j += i)
                notprime[j] = true;
        }
    for (int i = 1; i < SIZE; i++)
        update(pp, i, !notprime[i] && !notprime[(i + 1) / 2] ? 1 : 0);
}

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

    init();

    int q, l, r;
    cin >> q;
    while (q--)
    {
        cin >> l >> r;
        cout << getVal(pp, r) - getVal(pp, l - 1) << endl;
    }

    return 0;
}

Measured memory_bytes: 1152
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String str1 = br.readLine();
            String str2 = br.readLine();
            String str3 = br.readLine();
            System.out.println("" + str1.charAt(0) + str2.charAt(1) + str3.charAt(2));

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}


Measured memory_bytes: 21204
#include<stdio.h>
int main(){
  int i, x, y, min[3000], max[3000], n;
  for(i=0;;i++){
    scanf("%d %d\n", &x, &y);
    if(x==0 && y==0){
      break;
    }
    if(x<=y){
      min[i] = x;
      max[i] = y;
    }else{
      min[i] = y;
      max[i] = x;
    }
  }
  n = i;
  for(i=0;i<n;i++){
    printf("%d %d\n", min[i], max[i]);
  }
  return 0;
}

Measured memory_bytes: 1724
while True:
    h,w = map(int, input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):
        for j in range(w):
            if (i == 0 or j == 0) or (i == h-1 or j == w-1) :
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()



Measured memory_bytes: 7004
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
import collections 
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
NMAX=10**6
class Sieve:
    def __init__(self,n):
        self.n=n
        self.f=[0]*(n+1)
        self.prime=[]
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1):
            if(self.f[i]):
                continue
            else:
                self.prime.append(i)
                self.f[i]=i
                for j in range(i*i,n+1,i):
                    if(~self.f[j]):
                        self.f[j]=i
    def isProme(self,x):
        return (self.f[x]==x)
    def factorList(self,x):
        res=[]
        while(x!=1):
            res.append(self.f[x])
            x//=self.f[x]
        return res
    def factor(self,x):
        fl=self.factorList(x)
        return collections.Counter(fl)
        


                
                
            
        
        
def get_sieve_of_eratosthenes(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]



sieve=Sieve(10**6)
mp=defaultdict(int)
for i in range(N):
    f=sieve.factor(A[i])
    for key,val in f.items():
        mp[key]=max(val,mp[key])


lcm=1
for key,val in mp.items():
    lcm*=(key**val)


ans=0
for i in range(N):
    ans+=lcm//A[i]

print(ans%mod)

Measured memory_bytes: 82792
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); bool s=false; if(c=='-'){s=true;c=getchar_unlocked();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); int s=0; if(c=='-'){s=1;c=getchar_unlocked();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar_unlocked(); while(c==' '||c=='\n') c=getchar_unlocked(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar_unlocked(); } *s='\0'; return len; }

char **m;
int **d;

int s[1000000][2];
int main(void){
	int h=nextint();
	int w=nextint();
	int k=nextint();
	int x1=nextint()-1;
	int y1=nextint()-1;
	int x2=nextint()-1;
	int y2=nextint()-1;
	m = malloc(h*sizeof(char*));
	d = malloc(h*sizeof(int*));
	for(int i=0; i<h; i++){
		m[i] = malloc(w+1);
		d[i] = calloc(w, sizeof(int));
		nextstr(m[i]);
	}
	int sl=0, sr=0;
	d[x1][y1]=1;
	s[sr][0]=x1; s[sr][1]=y1; sr++;
	while(sl<sr){
		int x=s[sl][0], y=s[sl][1]; sl++;
		int D=d[x][y]+1;
		{
			int X=x-1, Y=y;
			for(int i=0; i<k && X>=0 && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]>=D); i++){ if(d[X][Y]!=D){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} X--; }
		}
		{
			int X=x+1, Y=y;
			for(int i=0; i<k && X<h  && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]>=D); i++){ if(d[X][Y]!=D){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} X++; }
		}
		{
			int X=x, Y=y-1;
			for(int i=0; i<k && Y>=0 && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]>=D); i++){ if(d[X][Y]!=D){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} Y--; }
		}
		{
			int X=x, Y=y+1;
			for(int i=0; i<k && Y<w  && m[X][Y]=='.' && (d[X][Y]==0||d[X][Y]>=D); i++){ if(d[X][Y]!=D){d[X][Y]=D; s[sr][0]=X; s[sr][1]=Y; sr++;} Y++; }
		}
		//printf("%d %d %d ", x+1, y+1, D-1);
	}
	printf("%d\n", d[x2][y2]==0?-1:d[x2][y2]-1);
}


Measured memory_bytes: 12268
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long

using namespace std;

int main(){

  int N, a;
  cin >> N;
  int ans = 0;
  vector<int> vec(N);

  for (int i = 0; i < N; i++){
    cin >> a;
    vec.at(i) = a;
  }

  bool flag = false;
  for (int i = 0; i < N; i++) {
    if(vec.at(i)%2 == 0){
      if(((vec.at(i)%3 == 0) || (vec.at(i)%5 == 0))){
        flag = true;
      } else {
        cout << "DENIED" << endl;
        return 0;
      }
    }
  }

  // if(flag == true){
    cout << "APPROVED" << endl;
  // } else {
  //   cout << "DENIED" << endl;
  // }

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	long long int n,i,a,min,max;
	cin>>n;
	cin>>a;
	min=a;
	max=a;
	for(i=1;i<n;i++)
	{
		cin>>a;
		if(a<min)
		min=a;
		if(a>max)
		max=a;
	}
	cout<<abs(max-min);
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Runtime.Remoting.Contexts;
using System.Security.Cryptography.X509Certificates;

namespace Contest
{
    class Scanner
    {
        private string[] line = new string[0];
        private int index = 0;
        public string Next()
        {
            if (line.Length <= index)
            {
                line = Console.ReadLine().Split(' ');
                index = 0;
            }
            var res = line[index];
            index++;
            return res;
        }
        public int NextInt()
        {
            return int.Parse(Next());
        }
        public long NextLong()
        {
            return long.Parse(Next());
        }
        public string[] Array()
        {
            line = Console.ReadLine().Split(' ');
            index = line.Length;
            return line;
        }
        public int[] IntArray()
        {
            var array = Array();
            var result = new int[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = int.Parse(array[i]);
            }

            return result;
        }
        public long[] LongArray()
        {
            var array = Array();
            var result = new long[array.Length];
            for (int i = 0; i < array.Length; i++)
            {
                result[i] = long.Parse(array[i]);
            }

            return result;
        }
    }

    class Program
    {
        private int N, D, X;
        private int[] A;

        private void Scan()
        {
            var sc = new Scanner();
            N = sc.NextInt();
            D = sc.NextInt();
            X = sc.NextInt();
            A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = sc.NextInt();
            }
        }

        public void Solve()
        {
            Scan();
            Console.WriteLine(A.Sum(Q) + X);
        }

        private int Q(int n)
        {
            return (D + n - 1) / n;
        }

        static void Main(string[] args)
        {
            new Program().Solve();
        }
    }
}

Measured memory_bytes: 11220
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
struct MaxFlow{
    struct edge{
        int to, rev;
        T cap;
        edge(int t, int r, T c):to(t),rev(r),cap(c){}
        edge(){}
    };
    vector<vector<edge>> graph;
    T zero;
    T inf;
    
    MaxFlow(int n, T zero, T inf):zero(zero),inf(inf){
        graph.resize(n);
    }
    void add_edge(int from, int to, T cap){
        graph[from].emplace_back(to, graph[to].size(), cap);
        graph[to].emplace_back(from, (int)graph[from].size()-1, 0);
    }
    T dfs(int v, int g, T flow, vector<bool>& used){
        if(used[v]) return -1;
        used[v] = true;
        if(v == g) return flow;
    
        for(auto &e: graph[v]){
            if(zero < e.cap){
                T ret = dfs(e.to, g, min(flow, e.cap), used);
                if(zero < ret){
                    e.cap = e.cap - ret;
                    graph[e.to][e.rev].cap = graph[e.to][e.rev].cap + ret;
                    return ret;
                }
            }
        }
        return zero;
    }
    T exec(int s, int g){
        T res = zero;
        while(1){
            vector<bool> used(graph.size(), false);
            T ret = dfs(s, g, inf, used);
            if(ret == zero) break;
            res = res + ret;
        }
        return res;
    }
};

int main(){
    int n,m;
    cin >> n >> m;
    MaxFlow<int> mf(n, 0, 1e9);
    for(int i=0; i<m; i++){
        int u,v,c;
        cin >> u >> v >> c;
        mf.add_edge(u, v, c);
    }
    cout << mf.exec(0, n-1) << endl;
    return 0;
}



Measured memory_bytes: 3140
import sys, collections
file = sys.stdin
n = int(file.readline())
C = list(map(int, file.readline().split()))

def square(P):
    G = []
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        G.append((len(P) - a[0]) * a[1])
    return max(G)

print(square(C))

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


void solve(long long N, std::vector<long long> a){
  sort(a.begin(), a.end(), greater<long long>());

  long long acc = 0;
  for(long long i = 0; i < N; i++){
    acc += a[(i*2)+1];
  }

  cout << acc << endl;
}

// 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)
int main(){
    long long N;
  scanf("%lld",&N);
  std::vector<long long> a(3*N);
  for(int i = 0 ; i < 3*N ; i++){
    scanf("%lld",&a[i]);
  }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 2560
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] ab = new int[m * 2];
        int[] out = new int[n];
        for(int i = 0; i < m * 2; i++){
            ab[i] = scan.nextInt();
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m * 2; j++){
                if(i + 1 == ab[j]){
                    out[i]++;
                }
            }
            System.out.println(out[i]);
        }
    }
}

Measured memory_bytes: 22996
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip> 
#include <complex> 
#include <string>
#include <vector> 
#include <list>
#include <deque> 
#include <stack> 
#include <queue> 
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm> 
#include <numeric> 
#include <typeinfo> 
#include <cstdio>
#include <cstdlib> 
#include <cstring>
#include <cmath>
#include <climits> 
#include <ctime>

using namespace std;

int main(void){
	const int INF=-100001;
	int n;
	int a,b;
	int num[5001];
	int ans=INF,ans2=0;
	while(1){
		ans=INF,ans2=0;
		cin >> n;
		if(n==0)break;
		for(a=0;a<n;a++)cin >>num[a];
		for(b=0;b<n;b++){
			ans2=0;
			for(a=b;a<n;a++){
				ans2+=num[a];
				ans=max(ans,ans2);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll dep(ll a,ll b){
	if(b==0){
		return a;
	}
	return dep(b,a%b);
}
int main() {
	ll n;
	cin>>n;
	ll ans;
	cin>>ans;
	for(int i=0;i<n-1;i++){
		ll x;
		cin>>x;
		ll gcd=dep(max(x,ans),min(x,ans));
		ans=ans/gcd*x;
	}
	cout << ans;
	// your code goes here
	return 0;
}

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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) REP(i, 0, n)
#define ALL(r) (r).begin(), (r).end()

void Main();

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main() {
    int64_t a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
using namespace std;
using uint = unsigned int;
using ll = long long;
int N;
double p[3000];
double dp[3000][3000];

void input() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> p[i];
    }
}
double solve() {
    if(N == 1) {
        return p[0];
    }
    if(N == 2) {
        return p[0] * p[1];
    }
    for(int i = 0; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            dp[i][j] = 1;
        }
    }
    for(int j = 1; j <= N; j++) {
        dp[0][j] *= dp[0][j-1] * (1-p[j-1]);
    }
    for(int i = 0; i < N; i++) {
        for(int j = i; j < N; j++) {
            dp[i+1][j+1] = dp[i][j]*p[j]+dp[i+1][j]*(1-p[j]);
        }
    }
    double ans = 0;
    for(int i = N/2+1; i <= N; i++) {
        ans += dp[i][N];
    }
    return ans;
}
int main() {
    input();
    printf("%.10lf\n", solve());
}

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

using namespace std;
using ll = long long int;
using P = pair<int, int>;

#define loop(i, n) for(int i = 0;i < n;i++)

int main(void){

    string str;
    cin >> str;

    string s = "";
    reverse(str.begin(), str.end());
    int ans = 0;

    loop(bit, 1 << str.size()-1){
        loop(i, str.size()-1){
            s += str[i];
            if(bit & (1 << i)) {
                ans += str[i]-'0';
                s += '+';
            }else{
                ans -= str[i]-'0';
                s += '-';
            }
        }
        // cout << "ans:" << ans << endl;
        // cout << bit <<  " s:" << s << endl;

        ans += str[3]-'0';
        s += str[3];

        if(ans == 7){
            reverse(s.begin(), s.end());
            cout << s << "=7" << endl;
            return 0;
        }

        s = "";
        ans = 0;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int N, i, count=0;
    char S[100001];
    
    scanf("%d",&N);
    scanf("%s",S);
    
    for(i=0; i<N-1; i++){
        //printf("S[%d] = %d\n",i,S[i]);
        if(S[i] != S[i+1]){
            //printf("i=%d, S[%d]=%d\n",i,i,S[i]);
            count++;
        }
    }
    
    printf("%d\n",count+1);
    
    
    return 0;
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	long long num[10000010] = {};
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			num[j]++;
		}
	}

	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += i * num[i];
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 81800
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
 
int main(){
  	string s, t, u;
    int a, b;
cin >> s >> t;
cin >> a >> b;
cin >> u;
    if (s == u){
        cout << (a-1) << " " << b << endl;
    } else {
        cout << a << " " << (b-1) << endl;
    }
    return 0;
}

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

typedef long long int LL;
#define REP(n) for(LL i = 0; i < (n); i++)
#define COUT(val) cout << (val) << endl
#define CIN(val) cin >> (val)
#define SORT(vec) sort(vec.begin(), vec.end())
#define SORT_GRE(vec) sort(vec.begin(), vec.end(), greater<LL>())

int main(){
    int n;
    cin >> n;
    if(n <= 999){
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
const int maxn = 10001;

int main()
{
	long long s;
	cin >> s;
	long long x1 = 0, y1 = 0, x2 = 0, y2 = 0;
	if (s <= 1000000000)
	{
		printf("0 0 0 1 %lld 0\n", s);
	}
	else
	{
		int x = sqrt(s) + 1;
		if (x > 1000000000)--x;
		x1 = y2 = x;
		x2 = 1;
		while (x1 * y2 - s > 1000000000)
		{
			--x1;
		}
		y1 = x1 * y2 - s;
		printf("0 0 %lld %lld %lld %lld\n", x1, y1, x2, y2);
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <cassert>
#include <random>


int main() {
	int x, y, a, b, c; std::cin >> x >> y >> a >> b >> c;
	std::vector<std::pair<int, int>> p(a + b + c);
	for (int i = 0; i < a; i++) std::cin >> p[i].first, p[i].second = 0;
	for (int i = a; i < a + b; i++) std::cin >> p[i].first, p[i].second = 1;
	for (int i = a + b; i < a + b + c; i++) std::cin >> p[i].first, p[i].second = 2;
	std::sort(p.rbegin(), p.rend());
	int cnta = 0, cntb = 0, cntc = 0;
	long long ans = 0;
	for (int i = 0; i < a + b + c; i++) {
		if (cnta + cntb + cntc == x + y) break;
		if (p[i].second == 0) {
			if (cnta == x) continue;
			cnta++;
			ans += p[i].first;
		}
		else if (p[i].second == 1) {
			if (cntb == y) continue;
			cntb++;
			ans += p[i].first;
		}
		else {
			cntc++;
			ans += p[i].first;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		boolean flag = false;
		for (int i = a; i <= b; i++) {
			if (i % k == 0) {
				flag = true;
				break;
			}
		}
		if (flag) {
			System.out.println("OK");
		} else {
			System.out.println("NG");
		}
	}
}


Measured memory_bytes: 35808
#include <iostream>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;

string To_string(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

int GetDigit(int num) {
    return To_string(num).length();
}


int Q;

int main() {
    cin >> Q;
    for(int i=0; i<Q; ++i) {
        int n;
        cin >> n;
        int digit = GetDigit(n); 
        int count = 0; 
        while(1) {
            int max = 0;
            if(n >= 0 && n <= 9) {
                cout << count << endl;
                break;
            } else {
                for(int j=1; j<=digit-1; ++j) {
                    int op1 = n / int(pow(10,j));
                    int op2 = n % int(pow(10,j));
                    //cout << "op1: " << op1 << ", op2: " << op2 << endl;
                    if(op1*op2 > max) { max = op1*op2; }
                    //cout << "max at loop" << j << ": " << max << endl;
                }
                ++count;
                //cout << "max: " << max << ", count: " << count << endl;
                
                if(max >= 0 && max <= 9) {
                    cout << count << endl;
                    break;
                } else if(count > 100) {
                    cout << "-1" << endl;
                    break;
                } else {
                    n = max;
                }
            }
        }
    }
    return 0;
}



Measured memory_bytes: 3392
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, X, M = map(int, readline().split())

    P = N.bit_length()
    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;

int main(){
	ll t;
    t=1;
  	while(t--){
      ll n,count=0;
      cin>>n;
      ll a[n];
      for(int i=0;i<n;i++){
        cin>>a[i];
      }
      ll min=n+1;
      for(int i=0;i<n;i++){
        if(a[i]<min){
          count++;
        }
        if(a[i]<min){
          min=a[i];
        }
      }
      cout<<count<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

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

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


ll calc(int N) {
    ll MOD = 1e9 + 7;
    if (N==1) return 2;
    if (N==0) return 1;

    if ( N % 2 == 0 ) {
        return ((calc(N / 2) % MOD) * (calc(N / 2) % MOD)) % MOD;
    } else {
        return ((2 * calc(N / 2) % MOD) * (calc(N / 2) % MOD)) % MOD;
    }
}

int main() {

    CIN(int, N);

    vector<int> A(N*2, 0);

    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        A[temp]++;
    }

    ll count = 1;

    if ( N % 2 == 0 ) {
        for (int i = 0; i < N/2; i++) {
            if ( A[ 2 * i + 1 ] != 2 ) {
                count = 0;
                break;
            }
        }
    } else {
        for (int i = 0; i < (N-1)/2; i++) {
            if ( A[ 2 * i + 2 ] != 2 ) {
                count = 0;
                break;
            }
        }
    }


    if ( count > 0 ) {
        count = calc(N/2);
    }

    cout << count << "\n";
    return 0;
}

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

mod_num = 10 ** 9 + 7
a = [0] * N

for i in range(M):
    a[i] = int(input())

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % mod_num
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)
 
print(ans)

Measured memory_bytes: 6900
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    V<ll> a(n);
    map<ll,ll> mp;
    set<ll> st;
    rep(i,n){
        cin>>a[i];
        mp[a[i]]=i+1;
        st.insert(i+1);
    }
    st.insert(0);
    st.insert(n+1);
    ll ans=0;
    for(ll i=n;i>=0;i--){
        auto it=st.find(mp[i]);
        auto it1=st.find(mp[i]);
        auto it2=st.find(mp[i]);
        it1++;
        it2--;
        ans+=(*it-*it2)*(*it1-*it)*i;
        it=st.erase(it);
    }
    cout<<ans<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
(全探索できるなら全探索しろ)
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'\n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え(=でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
*/

Measured memory_bytes: 23680
n = int(input())
a = input().split(" ")

sum = 1
for i in a:
  sum = sum * int(i)
  if sum > 1000000000000000000:
    break

if "0" in a:
  print(0)
elif sum > 1000000000000000000:
  print(-1)
else:
  print(sum)

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

int main() {
  int N, A;
  string op;
  cin >> N >> A;
    if (N % 500 <= A){
    cout << "Yes" << endl;
    }
    else {
    cout << "No" << endl;
    }
  
  // ここにプログラムを追記
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.close();
		//100~999
		int ans=n;
		for(int i=n;i<1000;i++) {
			String s = String.valueOf(i);
			if(s.charAt(0)==s.charAt(1) && s.charAt(0)==s.charAt(2)) {
				ans=i;
				break;
			}
		}
		System.out.println(ans);
	}
}

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

using namespace std;

int main(void){
  int dice[7];
  for(int i = 1;i < 7;++i){
    scanf("%d", dice + i); // To use like the 1-origin style.
  }

  string commands;
  cin >> commands;
  int tmp;
  for(int i = 0;i < commands.length();++i){
    char command = commands[i];
    switch(command){
      case 'N':
        tmp = dice[1];
        dice[1] = dice[2];
        dice[2] = dice[6];
        dice[6] = dice[5];
        dice[5] = tmp;
        break;
      case 'E':
        tmp = dice[3];
        dice[3] = dice[1];
        dice[1] = dice[4];
        dice[4] = dice[6];
        dice[6] = tmp;
        break;
      case 'W':
        tmp = dice[4];
        dice[4] = dice[1];
        dice[1] = dice[3];
        dice[3] = dice[6];
        dice[6] = tmp;
        break;
      case 'S':
        tmp = dice[6];
        dice[6] = dice[2];
        dice[2] = dice[1];
        dice[1] = dice[5];
        dice[5] = tmp;
        break;
      default:
        printf("Undefined input.");
        break;
    }
  }

  printf("%d\n", dice[1]);

  return 0;
}



Measured memory_bytes: 3296
#include <iostream>
#include <array>
#include <string>

int main() {
	std::array<bool, 1000000> is_prime_table = { false, false, true };
	for( int i=3; i<=is_prime_table.size(); i+=2 )
		is_prime_table[i] = [&i]() -> bool
		{
			for( int j=3; j*j<=i; j+=2 )
			if ( i % j == 0 )
				return false;
			return true;
		}();

	int num = 0;
	while( std::cin >> num ) {
		int result = num > 1 ? 1 : 0;	// 2

		for( int i=3; i<=num; i+=2 )
			if ( is_prime_table[i] )
				++result;
		std::cout << result << std::endl;
	}
}

Measured memory_bytes: 2140
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

template <class T = int>
int in() {
  T x;
  cin >> x;
  return x;
}
int bpm(int x, int y) {
  if (x == 0)
    return 0;
  else if (y == 0) {
    return 1;
  }
  int ans = 1;
  x %= MOD;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) {
      ans *= x;
      ans %= MOD;
    }
    x = x * x;
    x %= MOD;
  }
  return ans;
}

class DDiceInLine {
public:
  static void solve(std::istream &cin, std::ostream &cout) {
    int N, K;
    cin >> N >> K;
    vector<double> cum_sum(N + 1, 0);
    rep(i, N) {
      double temp;
      cin >> temp;
      cum_sum[i + 1] = (temp + 1) / 2;
      cum_sum[i + 1] += cum_sum[i];
    }
    double sum = 0;
    rep(i, N - K + 1) {
      sum = max(sum, cum_sum[i + K] - cum_sum[i]);
    }
    cout << fixed << sum << setprecision(15) << endl;
  }
};


signed main() {
  DDiceInLine solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>

int main(void){
  int W,H,i,v;

  while(1){
    scanf("%d %d",&W,&H);

    if(W==0 && H==0){
      break;
    }else{
      for(i=1;i<=W;i++){
	for(v=1;v<=H;v++){
	  printf("#");
	}
	printf("\n");
      }
      printf("\n");
    }
  }
}



Measured memory_bytes: 2032
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Gput(a, b) G[a].push_back(b)
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));

int main()
{
    cout << fixed << setprecision(30);
    ll n;
    cin >> n;
    vec a(n), b(n), c(n);
    loop(i, n) cin >> a[i];
    loop(i, n) cin >> b[i];
    loop(i, n) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    ll ans = 0;
    loop(i, n)
    {
        ll now = b[i];
        ans += idx_lower(a, now) * idx_upper2(c, now);
    }
    putout(ans);
    return 0;
}


Measured memory_bytes: 2560
s = input()
t = input()
len_t = len(t)
ans = 10 ** 9
for i in range(len(s) - len_t + 1):
    tgt = s[i:i+len_t]
    cnt = 0
    for j in range(len_t):
        if t[j] != tgt[j]:
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int main(){
  string s;cin>>s;
  rep(i,s.size())cout<<'x';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define mod 1000000007
#define mem(a,val) memset(a,val,sizeof(a))
#define ps(x,noOfDecimal) fixed<<setprecision(noOfDecimal)<<x
	
using namespace std;
int main()
{
	
	
		int n;
		cin>>n;
		bool ok=false;
		while(n>0){
			int rem= n%10;
			n/=10;
			if(rem==7)ok = true;
		}
	
		if(ok)cout<<"Yes"<<endl;
		else cout<<"No";
	return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 1000000000
#define eps 1e-7
#define mod 1000000007
#define int ll
using namespace std;

signed main(void) {
    int N, H, W;
    cin >> N >> H >> W;
    cout << (N-H+1) * (N-W+1) << endl;
    return 0;
}

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

const int MOD=1000000000+7;

int main(){
  int n;
  cin >> n;
  vector<string> s(2);
  for(int i=0;i<2;++i) cin >> s[i];

  vector<int> ss;
  for(int i=0;i<n;++i){
    if(s[0][i]==s[1][i]){
      ss.push_back(1);
    }else{
      ss.push_back(2);
      i++;
    }
  }
  int k=ss.size();
  ll ans;
  if(ss[0]==1) ans=3;
  else ans=6;
  //for(int i=0;i<k;++i) cout << ss[i] << endl;
  for(int i=1;i<k;++i){
    if(ss[i-1]==1 && ss[i]==1) ans=(ans*2)%MOD;
    else if(ss[i-1]==2 && ss[i]==1) ans=ans%MOD;
    else if(ss[i-1]==1 && ss[i]==2) ans=(ans*2)%MOD;
    else if(ss[i-1]==2 && ss[i]==2) ans=(ans*3)%MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
//make_tuple emplace_back next_permutation push_back make_pair second first

#if MYDEBUG
#define DBG(...) {string dst__=#__VA_ARGS__;dbgsplit(dst__);stringstream dss__; dss__<<dst__; debug(dss__,__VA_ARGS__);}
#else
#define DBG(...)
#endif
void debug(stringstream& ds){cerr<<endl;return;}
template<typename F, typename... R>void debug(stringstream& ds,const F& f, const R&... r){string n; ds>>n; cerr<< n <<'='<<f<<' '; debug(ds,r...);}
void dbgsplit(string &s){int l=s.length(),n=0;for(int i=0; i<l; ++i){if(s[i]=='(')++n;if(s[i]==')')--n;if(s[i]==','&&!n)s[i]=' ';}}
using LL = long long;
constexpr long long LINF=334ll<<53; constexpr int INF=15<<26; constexpr long long MOD=1E9+7;
template<typename T, typename S>
struct LazySegmentTree{
    static constexpr T id_val=0;
    static constexpr S id_delay=0;
    inline void composite_delay(S &a, S &b){
        a+=b;
    }
    inline void propagate(int k,int a,int b){
        data[k].val+=data[k].delay*(b-a);
        if(k<n){
            composite_delay(data[2*k].delay, data[k].delay);
            composite_delay(data[2*k+1].delay, data[k].delay);
        }
        data[k].delay=id_delay;
    }
    inline T calc(T a,T b){
        return a+b;
    }

    struct Node{
        T val; S delay;
        Node(){val=id_val;delay=id_delay;}
    };
    int n;
    vector<Node> data;
    explicit LazySegmentTree(int size){
        n=1;
        while(n<size)n*=2;
        data=vector<Node>(2*n,Node());
    }
    inline void update(int l,int r,S v){update(l,r,v,1,0,n);}
    void update(int l, int r, S v, int k, int a, int b){
        if(l<=a && b<=r){
            composite_delay(data[k].delay,v);
            propagate(k,a,b);
            return ;
        }
        propagate(k,a,b);
        if(b<=l || r<=a){return ;}//
        update(l,r,v,2*k,a,(a+b)/2);
        update(l,r,v,2*k+1,(a+b)/2,b);
        data[k].val=calc(data[2*k].val,data[2*k+1].val);
    }
    inline T get(int l,int r){return get(l,r,1,0,n);}
    T get(int l, int r, int k, int a, int b){
        if(b<=l || r<=a){return id_val;}//
        propagate(k,a,b);
        if(l<=a && b<=r){
            return data[k].val;
        }
        T vall=get(l,r,2*k,a,(a+b)/2);
        T valr=get(l,r,2*k+1,(a+b)/2,b);
        return calc(vall,valr);
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<tuple<int,int,int>> s(n);
    for(int i=0; i<n; ++i){
        int l,r;
        cin >> l >> r;
        s[i]=make_tuple(r-l+1,l,r);
    }
    sort(s.begin(),s.end());

    auto it=s.begin();
    LazySegmentTree<LL,LL> seg(m+1);
    for(int i=1; i<=m; ++i){
        int ans=0;
        while(get<0>(*it)<i && it<s.end()){
            seg.update(get<1>(*it),get<2>(*it)+1,1);
            it++;
        }
        ans=s.end()-it;
        for(int j=i; j<=m; j+=i){
            ans+=seg.get(j,j+1);
        }
        cout << ans <<endl;
    }

    return 0;
}



Measured memory_bytes: 8576
from collections import deque
from itertools import accumulate

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

N, K, *P = map(int, open(0).read().split())

mi = slide_min(P, K)
ma = slide_min([-p for p in P], K)

B = [mi != i or ma != i + K for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)

Measured memory_bytes: 40772
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  while (n--) {
    int y, m, d;
    cin >> y >> m >> d;
    int big = (y % 3 == 0 || m % 2);
    int cnt = 0;
    while (!(y == 1000 && m == 1 && d == 1)) {
      d++;
      cnt++;
      if (y % 3 == 0)
        big = 1;
      if (big) {
        if (d == 21)
          d = 1, m++, big = !big;
        if (m == 11)
          m = 1, y++, big = 1;
      } else if (!big) {
        if (d == 20)
          d = 1, m++, big = !big;
        if (m == 11)
          m = 1, y++, big = 1;
      }
    }
    cout << cnt << endl;
  }
}


Measured memory_bytes: 3080
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long m = sc.nextLong();
    long[] a = new long[n];
    long lc = 1;
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextLong();
      a[i] /= 2;
      long g = gcd(lc, a[i]);
      lc = g * (lc / g) * (a[i] / g);
    }
    int p = 0;
    for(int i = 0; i < n; i++) {
      long s = (lc / a[i]);
      if((s % 2) == 0) p++;
    }
    long ans = 0;
    if(p > 0) {

    } else {
      long k = (m / lc);
      ans = (k + 1) / 2;
    }
    System.out.println(ans);
  }

  public static long gcd(long x, long y) {
    if(y == 0) return x;
    return gcd(y, (x % y));
  }
}

Measured memory_bytes: 49700
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,K,di,A;
  cin >> N >> K;
  map<int,int> count;
  for(int i=0;i<K;i++){
    cin>>di;
    for(int j=0;j<di;j++){
      cin >> A;
      count[A]++;
    }
  }
  cout << N-count.size() << endl;
}

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

int main()
{
    int n,x=0;
    cin>>n;
    int arr[n];
    int mx=-1,mn=100000;
    for(int i=0; i<n; i++)
    {
        cin>>x;
        arr[i]=x;

        if(x<mn)
            mn=x;
        if(x>mx)
            mx=x;
    }

    int minStamina=1000000000;
    for(int i=mn; i<=mx; i++)
    {
        int total=0;
        for(int j=0; j<n; j++)
        {
            total+=((arr[j]-i)*(arr[j]-i));
        }
        if (total<minStamina)minStamina=total;
    }

    cout<<minStamina<<endl;

}


Measured memory_bytes: 256
#include<array>
#include<iostream>
#include<utility>
#include<vector>
int main(){
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int>> g(n);
  while(m--){
    int a, b;
    std::cin >> a >> b;
    --a;
    --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  struct node{
    int time, color;
    node(int x, int y) : time(x), color(y) {}
    void set(const node& x){if(x.time < time) *this = x;}
  };
  std::array<std::vector<std::pair<int, node>>, 11> qs;
  int q;
  std::cin >> q;
  std::vector<node> dp(n, node(q, 0)), prev = dp;
  while(q--){
    int v, d, c;
    std::cin >> v >> d >> c;
    qs[d].emplace_back(v - 1, node(q, c));
  }
  for(int d = 11; d--;){
    std::swap(dp, prev);
    for(int v = 0; v != n; ++v){
      dp[v] = prev[v];
      for(const int e : g[v]) dp[v].set(prev[e]);
    }
    for(const auto &e : qs[d]) dp[e.first].set(e.second);
  }
  for(const auto &e : dp) std::cout << e.color << std::endl;
  return 0;
}


Measured memory_bytes: 9976
A = input()
B = input()
C = input()
abc = [0,0,0]
now = 0
ABC = [A,B,C]
ans = 'ABC'
while True:
    if abc[now] == len(ABC[now]):
        print(ans[now])
        break
    if ABC[now][abc[now]] == 'a':
        abc[now] += 1
        now = 0
    elif ABC[now][abc[now]] == 'b':
        abc[now] += 1
        now = 1
    else:
        abc[now] += 1
        now = 2
 

Measured memory_bytes: 3064
#include <stdio.h>

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	
	a = ((a * a) / 2) - (a / 2);
	b = ((b * b) / 2) - (b / 2);
	
	printf("%d", a + b);
	
	return 0;
}

Measured memory_bytes: 1716