akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;

set<int> indices[26];

int idxToChar[200005];
int n;

const int BIT_SIZE = 200005;
int bit[BIT_SIZE];
void upd(int idx, int val) {
  idx += 2;
  while(idx < BIT_SIZE) {
    bit[idx] += val;
    idx += idx & -idx;
  }
}
int qry(int idx) {
  idx += 2;
  int ret = 0;
  while(idx) {
    ret += bit[idx];
    idx -= idx & -idx;
  }
  return ret;
}

void clean(set<int>& all, int idx) {
  assert(indices[idx].size());
  int val = *indices[idx].begin();
  upd(val, -1);
  indices[idx].erase(val);
  all.erase(val);
  if(indices[idx].size()) {
    val = *indices[idx].rbegin();
    upd(val, -1);
    indices[idx].erase(val);
    all.erase(val);
  }
}

void init() {
  string s;
  cin >> s;
  n = s.size();
  for(int i = 0; i < s.size(); i++) {
    indices[s[i] - 'a'].insert(i);
    idxToChar[i] = s[i] - 'a';
    upd(i, 1);
  }
  int odd = 0;
  for(int i = 0; i < 26; i++) {
    odd += indices[i].size()%2;
  }
  if(odd > 1) {
    cout << "-1\n";
    exit(0);
  }
}

void solve() {
  init();
  set<int> all;
  for(int i = 0; i < n; i++) all.insert(i);
  ll ret = 0;
  while(all.size()) {
    int lowest = *all.begin();
    int lowestCost = 0;
    {
      if(indices[idxToChar[lowest]].size() == 1) {
        lowestCost = all.size() / 2;
      }
      else {
        lowestCost = all.size() - qry(*indices[idxToChar[lowest]].rbegin());
      }
    }
    int highest = *all.rbegin();
    int highestCost = 0;
    {
      if(indices[idxToChar[highest]].size() == 1) {
        highestCost = all.size() / 2;
      }
      else {
        highestCost = qry(*indices[idxToChar[highest]].begin()) - 1;
      }
    }
    if(lowestCost < highestCost) {
      ret += lowestCost;
      int desired = idxToChar[lowest];
      clean(all, desired);
    }
    else {
      ret += highestCost;
      int desired = idxToChar[highest];
      clean(all, desired);
    }
  }
  cout << ret << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 20560
main = do
  (n:m:_) <- getLine >>= return . (map read) . words :: IO [Integer]
  print $ f n m

  where
    f n m
      | abs (n-m) >= 2 = 0
      | n == m = (2 * (g n) * (g m)) `mod` (10^9+7)
      | otherwise = ((g n) * (g m)) `mod` (10^9+7)

    g 0 = 1
    g n = (n * (g (n-1))) `mod` (10^9+7)


Measured memory_bytes: 7804
#include<iostream>
using namespace std;
int main(){
  int A,B,C;
  cin>>A>>B>>C;
  if( (A==5&&B==5&&C==7) || (A==5&&B==7&&C==5) || (A==7&&B==5&&C==5) ){
    cout<<"YES"<<endl;
  } else {
    cout <<"NO"<<endl;
  }
  return 0;
}


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

using namespace std;
#define int long long
const int N = 3001;
int n,a[3000],z,f[N][N];
bool cal[N][N];
int P[2];

int dp (int l, int r, int p)
{
    if (cal[l][r]) return f[l][r];
    if (l>r) return 0;
    if (p == 0)
    {
        f[l][r] = max(dp(l,r-1,1-p) + a[r], dp(l+1, r, 1-p) + a[l]);
    }
    else
    {
        f[l][r] = min(dp(l,r-1,1-p) - a[r], dp(l+1, r, 1-p) - a[l]);
    }
    cal[l][r] = true;
    return f[l][r];
}

signed main()
{
    cin >> n;
    for (int i=0; i<n; i++)
    {
        cin >> a[i];
    }
    cout << dp(0,n-1,0);
    return 0;
}


Measured memory_bytes: 78464
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> C(n);
    vector<vector<int>> A(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        cin >> C[i];
        for(int j = 0; j < m; j++) cin >> A[i][j];
    }

    int min = 100000000;
    for(int bit = 0; bit < (1 << n); bit++){
        int sum_c = 0;
        vector<int> sum_a(m);
        for(int i = 0; i < n; i++){
            if(bit & (1 << i)){
                sum_c += C[i];
                for(int j = 0; j < m; j++) sum_a[j] += A[i][j];
            }
        }
        bool f = true;
        for(int j = 0; j < m; j++){
            if(sum_a[j] < x) f = false;
        }
        if(f == true && sum_c < min) min = sum_c;
    }
    if(min == 100000000) cout << -1;
    else cout << min;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<class NumT>
NumT diffabs(NumT l, NumT r)
{
    if (l < r) return r-l;
    else return l-r;    
}

struct myinout_t {} io;

template<class T>
myinout_t &operator >>(myinout_t &my, T &i)
{
    cin >> i;
    return my;
}

myinout_t &operator >>(myinout_t &my, int &i)
{
    int r = scanf("%d", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

myinout_t &operator >>(myinout_t &my, ll &i)
{
    int r = scanf("%lld", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

template<class T>
myinout_t &operator <<(myinout_t &my, const T &i)
{
    cout << i;
    return my;
}

myinout_t &operator <<(myinout_t &my, int i)
{
    printf("%d", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, ll i)
{
    printf("%lld", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, double i)
{
    printf("%.20f", i);
    return my;
}

constexpr char BR = '\n';


///////////////////////////////////////////////////

bool l_ika_ni_dekiru(const vi &A, int N, int K, int L)
{
    int k = K;
    for (int i = 0; i < N; i++)
    {
        int ki = (A[i] - 1) / L;
        if (k >= ki)
            k -= ki;
        else
            return false;
    }
    return true;
}

int main()
{
    int N ,K;
    io >> N >> K;
    vi A(N);
    for (int i = 0; i < N; i++)
        io >> A[i];

    int l = 0, r = 1'000'000'001;
    while (l + 1 < r)
    {
        int mid = l + (r - l) / 2;
        if (l_ika_ni_dekiru(A, N, K, mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << BR;
}

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

int main() {
  string s;
  cin>>s;
  
  int a=0;
  for(int i=0;i<s.size();++i){
    if(s[i]=='A'){
      a=i;
      break;
    }
  }
  
  int z=0;
  for(int i=s.size()-1;i>=0;--i){
    if(s[i]=='Z'){
      z=i;
      break;
    }
  }
  cout<<z-a+1<<endl;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cmath>

constexpr double PI = acos(-1);

double rad(double ang)
{
    return ang * PI / 180;
}

double ang(double rad)
{
    return rad * 180 / PI;
}

int main()
{
    double th, x = 0, y = 0;
    for (int i = 0; i < 2; i++) {
        scanf("%lf", &th);
        x += cos(rad(th));
        y += sin(rad(th));
    }
    auto res = ang(atan2(y, x));    
    printf("%.15f\n", (res < 0 ? res + 360 : res));    
    return 0;
}

Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
int n;
double d,x,ans=0;
int main()
{
    cin>>n>>d>>x;
	for(n=n;n>0;--n)
    {
        ans+=d+(n-0.5)*x;
        d=((2*n+2)*d+5*x)/(2*n);
        x=(2*n+4)*x/(2*n);
    }
    printf("%.9f\n",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,k,q,p[100010];
	cin >> n >> k >> q;
	for(int i = 0;i < n;i++) p[i] = k - q;
	for(int i = 0;i < q;i++){
		int a;
		cin >> a;
		p[a - 1]++;
	}
	for(int i = 0;i < n;i++){
		if(p[i] > 0) Yes();
		else No();
	}
}


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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M;
  cin >> N >> M;
  vector<int> A(M);
  for (int i = 0; i < M; i++)
    cin >> A[i];
  int ans = N;
  for (auto a : A)
    ans -= a;
  if (ans < 0)
    cout << -1 << endl;
  else
    cout << ans << endl;
    
  return 0;
}


Measured memory_bytes: 3636
// next permutation を使って, {2,...,N} の順列を列挙し、辺が存在するパスを数える.

package main

import (
	"fmt"
	"sort"
)

// https://play.golang.org/p/ljft9xhOEn
func nextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

func main() {
	var N int
	var m int
	var g [8][8]bool

	fmt.Scan(&N, &m)
	var a, b int
	for i := 0; i < m; i++ {
		fmt.Scan(&a, &b)
		g[a-1][b-1] = true
		g[b-1][a-1] = true
	}
	v := make([]int, N)
	for i := 0; i < N; i++ {
		v[i] = i
	}

	ans := 0
	for {
		ok := true
		for i := 0; i < N-1; i++ {
			if !g[v[i]][v[i+1]] {
				ok = false
				break
			}
		}
		if ok {
			ans++
		}
		if !nextPermutation(sort.IntSlice(v[1:])) {
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main() {
  int n;
  cin >> n;
  vector<pair<ll,ll>> r(n);
  rep(i,n){int x,l; cin>>x>>l; r[i].F=x+l; r[i].S=x-l;}
  sort(r.begin(),r.end());
  
  int ans=0;
  int a=-inf;
  for(auto& p:r){
    if(a<=p.S){a=p.F; ans++;}
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split("");

		String s1[] = new String[str.length];
		String s2[] = new String[str.length];

		for (int i = 0; i < str.length; i++) {
			s1[i] = String.valueOf(i % 2);
			s2[i] = String.valueOf((i + 1) % 2);
		}

		int count1 = 0;
		int count2 = 0;

		for (int i = 0; i < str.length; i++) {
			if (!str[i].equals(s1[i])) {
				count1++;
			}
			if (!str[i].equals(s2[i])) {
				count2++;
			}
		}

		System.out.println(Math.min(count1, count2));
	}
}

Measured memory_bytes: 66152
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<complex>
#include<sstream>
#include<climits>
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N, L, Q;
int x[MAX_N];
int r[20][MAX_N];

int can_reach(int i, int d) {
  if (d == 0) return i;
  int k = 0;
  while (d >= (1<<k)) ++k;
  --k;
  return can_reach(r[k][i], d-(1<<k));
}

int main() {
  cin >> N;
  rep(i,N) cin >> x[i];
  cin >> L >> Q;

  for (int i = 0; i < N; ++i) {
    r[0][i] = upper_bound(x, x+N, x[i]+L) - x - 1;
  }

  int K = 0;
  while (N >= (1<<K)) ++K;
  for (int k = 1; k < K; ++k) {
    for (int i = 0; i < N; ++i) {
      r[k][i] = r[k-1][r[k-1][i]];
    }
  }


  while (Q--) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a; --b;
    if (a > b) swap(a,b);

    int lb = 0, ub = N, d = 0;
    while (ub-lb > 1) {
      d = (ub+lb)/2;
      if (can_reach(a, d) >= b) ub = d;
      else lb = d;
    }
    printf("%d\n", ub);
  }

  return 0;
}


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


typedef struct{
	char suit;
	int num;
	int pos;
} CARD_T;


int Partition(CARD_T *box, int l, int r)
{
	int pivot;
	CARD_T bk;
	int i, j;

	pivot = box[r].num;
	i = l - 1;
	j = r;

	while(1){
		while(box[++i].num < pivot);

		while(i < --j && pivot < box[j].num);

		if(j <= i)
			break;

		bk = box[i];
		box[i] = box[j];
		box[j] = bk;
	}

	bk = box[i];
	box[i] = box[r];
	box[r] = bk;

	return i;
}


int Partition2(CARD_T *box, int l, int r)
{
	int pivot;
	CARD_T bk;
	int i, j;

	pivot = box[r].num;
	j = l - 1;

	for(i = l; i < r; i++){
		if(box[i].num <= pivot){
			j++;
			if(i != j){
				bk = box[i];
				box[i] = box[j];
				box[j] = bk;
			}
		}
	}

	bk = box[r];
	box[r] = box[j + 1];
	box[j + 1] = bk;

	return j + 1;
}


void Quick_sort(CARD_T *box, int l, int r)
{
	int pivot;


	if(r <= l)
		return;

	pivot = Partition2(box, l, r);

	Quick_sort(box, l, pivot - 1);

	Quick_sort(box, pivot + 1, r);
}


int main()
{
	char in_str[20];
	int n;
	CARD_T *cards;
	int i;


	fgets(in_str, sizeof(in_str), stdin);
	sscanf(in_str, "%d", &n);

	cards = (CARD_T *)malloc(sizeof(CARD_T) * n);

	for(i = 0; i < n; i++){
		fgets(in_str, sizeof(in_str), stdin);
		sscanf(in_str, "%c %d", &cards[i].suit, &cards[i].num);
		cards[i].pos = i;
	}


	Quick_sort(cards, 0, n - 1);


	// 表示
	for(i = 0; i < n - 1; i++){
		if(cards[i].num == cards[i + 1].num && cards[i].pos > cards[i + 1].pos){
			printf("Not stable\n");
			break;
		}
	}
	if(i == n - 1)
		printf("Stable\n");

	// test
	for(i = 0; i < n; i++){
		printf("%c %d\n", cards[i].suit, cards[i].num);
	}

	return 0;
}


Measured memory_bytes: 2896
N = int(input())
S = input()
maxcount = 0

for i in range(N):
    count = 0
    alp = []
    for s in S[:i+1]:
        if s in S[i+1:] and s not in alp:
            count += 1
            alp.append(s)
    if maxcount < count:
        maxcount = count
print(maxcount)

Measured memory_bytes: 3060
// Duplex Printing

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int N;
    cin >> N;
    if (N % 2 == 0) {
        cout << N / 2 << endl;
    } else {
        cout << N / 2 + 1 << endl;
    }
    return 0;
}


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

using namespace std;

const int N = 1e5+100;

long long int dp[N][4], a[N], b[N], c[N];

int main () {
    memset(dp,0,sizeof(dp));
    long long int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++ ) cin >> a[i] >> b[i] >> c[i];
    for(int i = 1 ; i <= n ; i++ ) {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+c[i];
    }
    cout << max(max(dp[n][0],dp[n][1]),dp[n][2]);
}


Measured memory_bytes: 5760
#include <iostream>
#include <set>

using namespace std;

int main()
{
  int n, m, prev2 = 0, prev1 = 0, prev0 = 1;
  set<int> a;

  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a1;
    cin >> a1;
    a.insert(a1);
  }

  for (int i = 1; i <= n; i++) {
    //cout << prev0 << endl;
    prev2 = prev1; prev1 = prev0;
    if (a.find(i) != a.end()) {
      prev0 = 0;
    } else {
      prev0 = (prev1 + prev2)%1000000007;
    }
  }

  cout << prev0 << endl;

  return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

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

    int ans = 0;

    if(x == 1) {
        ans += 300000;
    } else if(x == 2) {
        ans += 200000;
    } else if(x == 3) {
        ans += 100000;
    }

    if(y == 1) {
        ans += 300000;
    } else if(y == 2) {
        ans += 200000;
    } else if(y == 3) {
        ans += 100000;
    }

    if(x == 1 && y == 1) {
        ans += 400000;
    }

    cout << ans << endl;

    return 0;


}

Measured memory_bytes: 256
n = int(input())
s = []
d = {}
for _ in range(n):
    s.append("".join(sorted(str(input()))))
for si in s:
    if si not in d.keys():
        d[si] = 1
    else: d[si] += 1
print(sum([int(v*(v-1)/2) for v in d.values()]))

Measured memory_bytes: 19400
#include<iostream>
#include<vector>
#include<map>
int main (){
    std::cin.tie(0); 
	std::ios::sync_with_stdio(false);
    long long N,Q;std::cin>>N;
    std::map<long long, long long>  A;
    long long a;
    long long S=0;
    for (int i=0;i<N;++i){
        std::cin>>a;
        S+=a;
        A[a]+=1;
    }
    std::cin>>Q;
    std::vector<long long> AS(Q);
    long long b,c,t;
    for(int i=0;i<Q;++i){
        std::cin>>b>>c;
        t=A[b];
        S += (c-b) * t;
        A[c]+=t;
        A[b]=0;
        AS[i]=S;
    }
    for (auto s : AS) {
        std::cout<<s<<std::endl;
    }


    return 0;
}

Measured memory_bytes: 9940
#include <iostream>
#include <cmath>
#include <cctype>
#include <string>

using namespace std;

bool IsSquare(int v) {
  auto r = static_cast<int>(sqrt(v));
  return (((r -1) * (r -1) == v) || (r * r == v) || ((r + 1) * (r + 1) == v));
}

int main() {

  string num1;
  string num2;

  cin >> num1 >> num2;
  num1.append(num2);

  int v = atoi(num1.c_str());

  if (IsSquare(v))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

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

using namespace std;

#define EPS 1e-9
#define For(i,N) FOR(i,N)
#define Forr(i,a,b) FORR(i,a,b)
#define Fotr(i,a,b,c) FOTR(i,a,b,c)
#define FOR(i,N) FORR(i, 0, N)
#define FORR(i,a,b) FOTR(i, a, b, 1)
#define FOTR(i,a,b,c) for(int i=(a);i<(b);i+=(c))
#define FOREACH(i,x) for(__typeof__((x).begin())i=(x).begin();i!=(x).end();i++)
#define MEM(a,x) memset(a,x,sizeof(a))
#define BCHK(a,x) (((a)>>(x))&1)
#define BSET(a,x) ((a)|(1<<(x)))
#define BCLR(a,x) ((a)&(~(1<<(x))))
#define BTGL(a,x) ((a)^(1<<(x)))
#define FMT(...) (sprintf(CRTBUFF, __VA_ARGS__)?CRTBUFF:0)
#define read() freopen("input.txt","r",stdin)
#define write() freopen("output.txt","w",stdout)
#define cpp_io() {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define BUFFSIZE 30000
#define INF 1000000000
#define MAX 300010
#define MOD 1000000007
#define pb push_back
#define mkpr make_pair
#define pii pair<int, int>
#define PI acos(-1)
#define ll long long
#define fi first
#define si second
#define all(x) x.begin(), x.end()
#define double long double

char CRTBUFF[BUFFSIZE];
#define dbg(args...) {cerr<<"-->";debugger::call(#args,args);cerr<<"\n";}
struct debugger {
    static void call(const char* it) {}
    template<typename T, typename ... aT>
    static void call(const char* it, T a, aT... rest) {
        string b;
        for (; *it&&*it != ','; ++it) if (*it != ' ')b += *it;
        cerr << b << "=" << a << " ";
        call(++it, rest...);
    }
};

int main(){
    cpp_io();
    #ifdef LOCAL
        read();
        //write();
    #endif
    
    int n;
    cin>>n;
    if(n<3){
        cout<<0<<endl;
        return 0;
    }
    cout<<n/3<<endl;
    return 0;
    

}





















Measured memory_bytes: 896
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

int main() {
	ll a, b; cin >> a >> b;

	cout << (b - a)*(b - a + 1) / 2 - b << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using ull = unsigned long long;
using ll = long long;
using namespace std;

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

    if (n < 4) {
        cout << 0 << endl;
        return 0;
    }

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

    sort(a.begin(), a.end(), greater<int>());

    // int edge[2] = {0,0};
    // int edge_i = 0;
    vector<ll> edge;

    for (int i = 0; i < a.size() - 1 && edge.size() < 2; ++i) {
        if (a[i] == a[i+1]) {

            // cand
            // edge[edge_i] = a[i];
            edge.push_back(a[i]);
            // edge_i++;
            i++;

            // cout << "edge:" << edge.back() << endl;
        } else {
            // cout << a[i] << " is skipped." << endl;

        }
    }

    if (edge.size() < 2) {
        cout << 0 << endl;
    } else {
        cout << edge[0] * edge[1] << endl;
    }

    return 0;
}

Measured memory_bytes: 640
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b/c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 * c1 + buy2 * c2 > b or buy1 + buy2 <q1:
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
		if buy1 == 0:
			break
	if buy1 > 0:
		print buy1, buy2
	else:
		print "NA"

Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
 pair<pair<int,int>,int> p[100001];
signed main() {
 int n;
 cin>>n;
 int a[n],b[n];
 pair<int,int> p[n];
 for(int i=0;i<n;i++)cin>>a[i];
 for(int i=0;i<n;i++)cin>>b[i];
 for(int i=0;i<n;i++)p[i]=make_pair(b[i],a[i]);
 sort(p,p+n);
 for(int i=0;i<n;i++){
   p[i]=make_pair(p[i].second,i);
 }
 sort(p,p+n);sort(b,b+n);
 for(int i=0;i<n;i++){
   if(p[i].first>b[i]){
     cout<<"No";
     return 0;
   }

 }
 int k=0;
 for(int i=0;i<n-1;i++){
   k=p[k].second;
   if(k==0){
     cout<<"Yes";
     return 0;
   }
 }
 for(int i=0;i<n-1;i++){
   if(p[i+1].first<=b[i]){
     cout<<"Yes";
     return 0;
   }

 }
 cout<<"No";

 




return 0;
}


Measured memory_bytes: 3328
n,m = map(int,input().split())
a = n-m
ans = 0
if abs(a) > 1:
    ans = 0
elif abs(a) == 1:
    x = 1
    if a < 0:
        s = n
    else:
        s = m
    for i in range(1,s+1):
        x *= i 
        x %= (10**9+7)
    ans = x * x *(i+1) %(10**9+7)
else:
    x = 1
    for i in range(1,n+1):
        x *= i 
        x %= (10**9+7)
    ans = 2* x**2  %(10**9+7)
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using static System.Console;
using static System.Math;
class Simple
{
    int N;
    void Solve() {
        //input
        N = io.Int;
        //cal
        var ans = 0L;
        if (N == 0) {
            ans = 2;
        }else if(N== 1) {
            ans = 1;
        } else {
            var pre2 = 2L;
            var pre1 = 1L;
            for(int i = 2; i <= N; ++i) {
                ans = pre1 + pre2;
                pre2 = pre1;
                pre1 = ans;
            }
        }
        //ret
        WriteLine(ans);
    }

    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) => new Simple().Stream();
    private void Stream() {
        //var exStdIn = new System.IO.StreamReader("stdin.txt");
        //SetIn(exStdIn);
        Solve();
        io.Flush();
    }
}
class SimpleIO
{
    string[] _nextBuffer;
    int _bufferCnt;
    char[] cs = new char[] { ' ', '"', ',' };
    StreamWriter sw = new StreamWriter(OpenStandardOutput()) {
        AutoFlush = false
    };
    public SimpleIO() {
        _nextBuffer = new string[0];
        _bufferCnt = 0;
        SetOut(sw);
    }
    string Next() {
        if (_bufferCnt < _nextBuffer.Length)
            return _nextBuffer[_bufferCnt++];
        var st = ReadLine();
        while (st == "")
            st = ReadLine();
        if (st != null)
            _nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        else
            st = "";
        _bufferCnt = 0;
        return _nextBuffer[_bufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void Flush() => Out.Flush();
}


Measured memory_bytes: 11092
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()

int h, w;
int a[200000];
int b[200000];


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

	cin >> h >> w;
	rep(i, h) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}

	multiset<int> ms;
	map<int, int> mp;

	rep(i, w) {
		mp[i] = 0;
		ms.insert(0);
	}

	for (int i = 1; i <= h; i++) {
		auto it1 = mp.lower_bound(a[i - 1]);
		auto it2 = mp.upper_bound(b[i - 1]);
		for (auto it = it1; it != it2; it = mp.erase(it)) {
			ms.erase(ms.find(it->second));
		}

		if (b[i] + 1 < w) {
			auto it3 = mp.upper_bound(b[i] + 1);
			if (it3 != mp.begin()) {
				--it3;
				int mv = it3->second + (b[i] + 1 - it3->first);

				auto it4 = mp.find(b[i] + 1);
				if (it4 == mp.end()) {
					mp[b[i] + 1] = mv;
					ms.insert(mv);
				}
				else if (mv < it4->second) {
					ms.erase(ms.find(it4->second));
					mp[b[i] + 1] = mv;
					ms.insert(mv);
				}
			}
		}

		if (ms.empty())cout << -1 << endl;
		else cout << *ms.begin() + i << endl;
	}



	return 0;
}


Measured memory_bytes: 23928
package main

import (
	"fmt"
)

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func checkGrid(g [][]int, a, b []int) bool {
	for i, ai := range a {
		for j, bi := range b {
			if g[i][j] != ai+bi {
				return false
			}
		}
	}
	return true
}

func main() {
	c := make([][]int, 3)
	for i := 0; i < 3; i++ {
		r := make([]int, 3)
		fmt.Scanf("%d %d %d", &r[0], &r[1], &r[2])
		c[i] = r
	}

	for a1 := 0; a1 <= 100; a1++ {
		for a2 := 0; a2 <= 100; a2++ {
			for a3 := 0; a3 <= 100; a3++ {
				b1 := abs(a1 - c[0][0])
				b2 := abs(a2 - c[1][1])
				b3 := abs(a3 - c[2][2])
				a := []int{a1, a2, a3}
				b := []int{b1, b2, b3}
				if checkGrid(c, a, b) {
					fmt.Println("Yes")
					return
				}
			}
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 512
N = int(input())
alist = list(map(int, input().split()))
flag = 0
for i in range(0,N):
    if alist[i]%2 == 1:
        continue
    else:
        if alist[i]%3 == 0 or alist[i]%5 == 0:
            continue
        else:
            print("DENIED")
            flag = 1
            break
if flag == 0:
    print("APPROVED")

Measured memory_bytes: 61836
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <cmath>
#include <string.h>
#include <queue>
#include <functional>

#define NMAX 100010
#define MOD 1000000007
#define INF 2000000000
#define PI 3.1415926535
#define EPS 1.e10-6

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) > 0 ? (a) : (-a))

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

int n, k;
int r, s, p;
char t[NMAX];
int maxWin[3][NMAX];
int taken[NMAX];

int GetWin(char computer, int player)
{
	// rock = 0, paper = 1, scissors = 2
	switch (computer)
	{
	case 'r':
		if (player == 1)
			return p;
		break;
	case 'p':
		if (player == 2)
			return s;
		break;
	case 's':
		if (player == 0)
			return r;
		break;
	default:
		break;
	}
	return 0;
}

int main()
{
	cin >> n >> k;
	cin >> r >> s >> p;
	cin.get();
	cin.getline(t, n + 1);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (i < k)
				maxWin[j][i] = GetWin(t[i], j);
			else
				maxWin[j][i] = MAX(maxWin[(j + 1) % 3][i - k] + GetWin(t[i], j), maxWin[(j + 2) % 3][i - k] + GetWin(t[i], j));
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int val = 0;
		if (i < k)
			val = MAX(MAX(maxWin[0][i], maxWin[1][i]), maxWin[2][i]);
		else
			val = MAX(MAX(maxWin[0][i], maxWin[1][i]), maxWin[2][i]) - MAX(MAX(maxWin[0][i - k], maxWin[1][i - k]), maxWin[2][i - k]);
		taken[i] = val;
	}

	for (int i = 0; i < n; i++)
		ans += taken[i];
	cout << ans << '\n';
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    rep(i, n) {
        int a;
        cin >> a;
        a--;
        x[a]++;
    }
    sort(x.begin(), x.end());
    int sum = 0;
    for(int i = n - 1; i >= 0; i--) {
        sum += x[i];
        if(n - i >= k) break;
    }
    cout << n - sum << endl;
    return 0;
}

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

#define gOdSpEeD ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0)
#define Int long long
#define all(x) x.begin(), x.end()
#define el '\n'
#define ints unsigned
#define cy cout << "YES" << end 
#define cn cout <<"NO" << end
#define elif else if
#define test int t; cin>>t; while(t--)

using namespace std;


int main () {
    gOdSpEeD;
    int n; cin >> n;
    char s; cin >> s;
    int k; cin >> k;
    if(s == '+') cout << n+k << endl;
    elif(s == '-') cout << n-k << endl;
    return 0;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  int c = 1;
  while (n >= k) {
    n /= k;
    c++;
  }
  cout << c << endl;   
}

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

using namespace std;

const int MAX_N = 5e5 + 1, MAX_Q = 5e5 + 1, MAX_AI = 5e5 + 1, OFFSET = 10;

int N, Q, BLOCK_SIZE, current_ans, arr[MAX_N + OFFSET], ans[MAX_Q + OFFSET], frec[MAX_AI + OFFSET];

struct Query {
  int left, right, idx;
  Query() {};
  Query(int left_, int right_, int idx_): left(left_), right(right_), idx(idx_) {}
  bool operator < (const Query& other) const {
    int this_block = this -> left / BLOCK_SIZE;
    int other_block = other.left / BLOCK_SIZE;
    if (this_block != other_block) return this_block < other_block;
      return this -> right < other.right;
    }
} query[MAX_Q + OFFSET];

void print() {
  for (int i = 0; i < Q; i++) printf("%d\n", ans[i]);
}

void add(const int& num) {
  if (0 == frec[num]) current_ans++;
  frec[num]++;
}

void remove(const int& num) {
  frec[num]--;
  if (0 == frec[num]) current_ans--;
}

void MoAlgorithm() {
  BLOCK_SIZE = sqrt(N);
  sort(query, query + Q);
  int mo_left = 0, mo_right = -1;
  for (int i = 0; i < Q; i++) {
    while (mo_right < query[i].right) add(arr[++mo_right]);
    while (mo_right > query[i].right) remove(arr[mo_right--]);
    while (mo_left < query[i].left) remove(arr[mo_left++]);
    while (mo_left > query[i].left) add(arr[--mo_left]);
    ans[query[i].idx] = current_ans;
  }
}

void readInput() {
  scanf("%d %d", &N, &Q);
  for (int i = 0; i < N; i++) scanf("%d", arr + i);
  for (int i = 0, left_, right_; i < Q; i++) {
    scanf("%d %d", &left_, &right_);
    query[i] = Query(--left_, --right_, i);
  }
}

int main() {
  readInput();
  MoAlgorithm();
  print();
  return (0);
}


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

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

    vector<int> a(n);
    rep(i, n) cin >> a.at(i);

    map<int, int> counter;
    int ans = 0;
    rep(i, n)
    {
        if (counter[a.at(i)] > 0)
        {
            counter[a.at(i)] = 0;
            ans--;
        }
        else
        {
            counter[a.at(i)]++;
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8304
n=gets.to_i
input = gets.chomp.split(" ").map(&:to_i)
answer=[]
n.times do |count|
  if count==0
    answer<<input[count]
  elsif count==n-1
    answer<<input[count-1]
  else  
    answer<<[input[count],input[count-1]].min
  end  
end  
puts answer.inject(:+)

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

int main(){
  int N;
  string color;
  cin >> N;
  
  for(int i=0; i<N; i++){
    cin >> color;
    if(color == "Y"){
      cout << "Four" << endl;
      break;
    }
    else if (i == N-1) cout << "Three" << endl;
  }
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
#include <numeric>
#include <iomanip>

using namespace std;

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

    string search;
    int ans = 0;

    for (int i = 0; i < 1000; i++)
    {
        if (i < 10)
        {
            search = "00" + to_string(i);
        }
        else if (i < 100)
        {
            search = "0" + to_string(i);
        }
        else
        {
            search = to_string(i);
        }

        int point = 0;
        int flag = 0;
        for (int j = 0; j < 3; j++)
        {
            for (int k = point; k < N; k++)
            {
                if (search.at(j) == S.at(k))
                {
                    point = k+1;
                    flag++;
                    break;
                }
                
            }
            
        }
        if (flag == 3)
        {
            //cout << search << endl;
            ans++;
        }
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
    int a[101],length,i,j,count=0,temp;
    scanf("%d",&length);
    for (i=0; i<length; i++) scanf("%d",&a[i]);
    for (i=0; i<length; i++) {
        for (j=length-1; j>i; j--) {
            if (a[j]<a[j-1]) {
                temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
                count++;
            }
        }
    }
    for (i=0; i<length; i++) {
        if (i) printf(" ");
        printf("%d",a[i]);
    }
    printf("\n%d\n",count);
    return 0;
}

Measured memory_bytes: 604
#初期入力
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
#あえて構造を辞書
connection ={i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    connection[i] =A[i-1]
#テレポート先は1か所、N << K だからループする。戻ってくる場所を探す。
passed =[1]
passed_set =set(passed)
intersection =0
next =connection[1]
#count_intersection =[]
#count_loop =0
for i in range(1,N+1): #スタートは１
    if next not in passed_set:
        passed.append(next)
        passed_set.add(next)
        next =connection[next]
    else:
        intersection =next
        break
#1ループの移動回数
loop_s  =passed.index(intersection)
loop_f  =len(passed) 
loop_num =loop_f -loop_s

#ループ開始前後で場合分け
ans =0
if K < loop_f:
    ans =passed[K]
else:
    K2      =K -loop_s
    q,mod   =divmod(K2,loop_num)
    ans     =passed[loop_s +mod]
print(ans)

Measured memory_bytes: 49268
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
 
using namespace std;

int main()
{
    int n, p;
    while(1){
        cin >> n >> p;
        if(n == 0 && p == 0) break;
        int candidate[50] = {0};
        int start = 0;
        int bowlin = p;
        while(1){
            for(int i = 0; i < n; i++){
                candidate[i] += bowlin / n;
                if(i < bowlin % n) candidate[(start + i) % n]++;
            }
            int end = (start + bowlin % n) % n;
            while(candidate[end] == 0) end = (end + 1) % n;
            bowlin = candidate[end];
            candidate[end] = 0;
            start = (end + 1) % n;
            if(candidate[start] == p - 1){
                cout << start << endl;
                break;
            }
        }
    }
   return 0;
}

Measured memory_bytes: 1160
H,W=map(int, input().split())

S=[list(input()) for i in range(H)]

A=[-1,-1,-1,0,0,1,1,1]
B=[-1,0,1,-1,1,-1,0,1]
Ts=""
T=[]
t=0
for i in range(H):
    for j in range(W):

        if S[i][j]=="#":
            Ts+="#"
            continue

        for a,b in zip(A,B):
            ni=i+a
            nj=j+b

            if ni<0 or ni>=H or nj <0 or nj>=W: continue
            if S[ni][nj]=="#": t+=1
        Ts+=str(t)
        t=0

    T.append(Ts)
    Ts=""

for i in range(H):
    print(T[i])


Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>



int main()
{
    
    int n = 0;
    
    scanf("%d",&n);
    
    if(n<4)
    {
        printf("No\n");
        return 0;
    }
    if(n%4 == 0)
    {
        printf("Yes\n");
        return 0;
    }
    
    
    for(int i = 0;n>0;i++){
        
    
        if(n%7 == 0)
        {
            printf("Yes\n");
            return 0;
        }
        if(n%7 != 0)
        {
            
            n-=4;
            continue;
        }
  
    }
    
    printf("No\n");
    
    return 0;
    
}

Measured memory_bytes: 128
index = Hash.new{|index,key| index[key] = []}
while line = gets do
  word,page=line.split
  page=page.to_i
  index[word]<<page
end
 
index.each{|key,value|
  value.sort!
}
 
words=index.keys.sort!
words.each{|key|
  puts key
  puts index[key].join(" ")
}

Measured memory_bytes: 2360
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

struct R
{
	double x1,x2,y1,y2;
	R(double x1,double x2,double y1,double y2):x1(x1),x2(x2),y1(y1),y2(y2){}
};
bool F(const R &a,const R &b)
{
	return(a.x1<b.x2&&b.x1<a.x2&&a.y1<b.y2&&b.y1<a.y2);
}
int main()
{
	int n,i,j,k,T=0;
	double x,y,p,res;
	while(scanf("%d",&n),n)
	{
		vector<R>v;
		vector<double>vx,vy;
		while(n--)
		{
			scanf("%lf%lf%lf",&x,&y,&p);
			v.push_back(R(x-p,x+p,y-p,y+p));
			vx.push_back(x-p);
			vx.push_back(x+p);
			vy.push_back(y-p);
			vy.push_back(y+p);
		}
		int f;
		res=0;
		sort(vx.begin(),vx.end());
		sort(vy.begin(),vy.end());

		for(i=0;i+1<vx.size();++i)
			for(j=0;j+1<vy.size();++j)
				for(f=k=0;k<v.size();++k)
					if(F(v[k],R(vx[i],vx[i+1],vy[j],vy[j+1])))
						if(f++==0)
							res+=(vx[i+1]-vx[i])*(vy[j+1]-vy[j]);
		printf("%d %.2f\n",++T,res);
	}
	return 0;
}

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

int dp[100000+1000][2][200];
const int pri=1000000007;

signed main(){
	string S; int D; cin>>S>>D;
	dp[0][0][0]=1;
	int N=S.size();
	for(int i=0;i<N;i++){
		for(int smaller=0;smaller<2;smaller++){
			for(int j=0;j<=D;j++){
				for(int x=0;x<=(smaller ? 9 : S[i]-'0');x++){
					dp[i+1][smaller or x<(S[i]-'0')][(j+x)%D]+=dp[i][smaller][j];
					dp[i+1][smaller or x<(S[i]-'0')][(j+x)%D]%=pri;
				}
			}
		}
	}
	cout<< (dp[N][0][0]+dp[N][1][0]-1 + pri)%pri<<endl;
}


Measured memory_bytes: 33024
#include <cstdio>
#include <set>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
 
namespace IO
{
    inline char gc()
    {
        static char s[1<<20|1]={0},*p1=s,*p2=s;
        return (p1==p2)&&(p2=(p1=s)+fread(s,1,1<<20,stdin),p1==p2)?EOF:*(p1++);
    }
//	inline char gc() { return getchar(); }
	inline long long read()
	{
		long long ret=0;bool flag=0;char c=gc();
		while ((c<'0')|(c>'9')) flag ^= !(c^'-'),c=gc();
		while ((c>='0')&(c<='9')) ret=(ret<<1)+(ret<<3)+(c^'0'),c=gc();
		return flag?-ret:ret;
 	}
 	char OutputAns[1<<20|1],*OutputCur = OutputAns;
 	inline void output()
 	{
 		OutputCur -= fwrite(OutputAns,1,OutputCur - OutputAns,stdout);
	}
	inline void print(long long ans)
	{
		char s[20]={0};
		if (OutputCur - OutputAns + sprintf(s,"%lld",ans) >> 20) output();
		OutputCur += sprintf(OutputCur,"%lld",ans);
	}
	inline void printc(char c)
	{
		if (OutputCur - OutputAns + 1 >> 20) output();
		*(OutputCur++) = c;
	}
}
 
using IO::read;
using IO::print;
using IO::output;
using IO::printc;

typedef long long int64;

const int M = 3e5 + 11;

struct Node { int l, r; bool operator < (const Node& x) const { return (l == x.l ? r < x.r : l < x.l); } } E[M];

struct Tree { int ls, rs, sum; } T[M * 25];

int Rt[M], S[M], End[M];

int n, m, ans, tot;

inline void Insert(int pre, int now, int p, int o = 1, int l = 1, int r = n)
{
	if (l == r) { T[now].sum = T[pre].sum + 1; return ; } int mid = l + r >> 1;
	if (p <= mid) { T[now].ls = ++tot, T[now].rs = T[pre].rs; Insert(T[pre].ls, T[now].ls, p, o<<1, l, mid); }
	else T[now].ls = T[pre].ls, T[now].rs = ++tot, Insert(T[pre].rs, T[now].rs, p, o<<1|1, mid + 1, r);
	T[now].sum = T[T[now].ls].sum + T[T[now].rs].sum;
}

inline int Qu(int pre, int now, int x, int y = n, int o = 1, int l = 1, int r = n)
{
	if (l >= x && r <= y) return T[now].sum - T[pre].sum; int mid = l + r >> 1, res = 0;
	if (x <= mid) res = Qu(T[pre].ls, T[now].ls, x, y, o<<1, l, mid);
	if (y > mid) res += Qu(T[pre].rs, T[now].rs, x, y, o<<1|1, mid + 1, r); return res;
}

inline void Input()
{
	m = read(), n = read(); int cur = 0;
	for (int i = 1;i <= m; ++i) E[i].l = read(), E[i].r = read(); std::sort(E + 1, E + 1 + m);
	for (int i = 1;i <= n; ++i) { S[i] = cur; while (E[cur + 1].l == i) ++cur; End[i] = cur; }
	for (int i = 1;i <= m; ++i) Rt[i] = ++tot, Insert(Rt[i - 1], Rt[i], E[i].r);
}

inline void Solve()
{
	for (int i = 1;i <= n; ++i)
	{
		ans = 0;
		for (int j = i;j <= n; j += i)
			ans += Qu(Rt[S[j - i + 1]], Rt[End[j]], j);
		printf("%d\n", ans);
	}
}

int main(void)
{
	Input();
	Solve();
}

Measured memory_bytes: 72320
n=int(raw_input())
a=map(int, raw_input().split())

b=[0]*n
m=[]
for i in range(n,0,-1):
    v=0
    for j in range(i,n+1,i):
        v+=b[j-1]
    #b[i-1]=1 if v%2!=a[i-1] else 0
    if v%2!=a[i-1]:
        b[i-1]=1
        m.append(i)

print len(m)
print " ".join(map(str, m))


Measured memory_bytes: 24060
from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad,ne):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == b or nxt == ne:
				continue
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad,-1))
	else:
		for c1,c2 in pairs:
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
	print ans
solve()

Measured memory_bytes: 98844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()
#define out(s) cout << (s) << endl
#define ll long long

bool is_prime(int n) {
  if(n==1) return false;
  if (n == 2) return true;
  if (n%2 == 0) return false;
  for(int d = 3; d*d <= n; d += 2) {
    if( n % d == 0 ) return false;
  }
  return true;
}

void solve(){
  int n;
  cin>>n;
  ll ans = 0;
  vector<int> a(n);
  rep(i,0,n){
    cin>>a[i];
    if(is_prime(a[i])) ans++;
  }
  out(ans);
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}



Measured memory_bytes: 3096
#include <iostream>

using namespace std;

int gcd(int x, int y) {
  return y ? gcd(y, x % y) : x;
}

int main() {
  int N, X;
  cin >> N >> X;
  int D[100100];
  cout << endl;
  for (int i = 0; i < N; i++) {
    int num;
    cin >> num;
    D[i] = abs(X-num);
  }
  int ans = D[0];
  for (int i = 1; i < N; i++) {
    ans = gcd(ans, D[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC return 0;
using namespace std;
int a, b, k;
int main() {
    DAU
    cin >> k >> a >> b;
    for (int i = a; i <= b; ++i)
        if (i % k == 0) {
            cout << "OK";
            PLEC
        }
    cout << "NG";
    PLEC
}


Measured memory_bytes: 3612
# Solution using a lazy segment tree

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        for i in range(self.n-1):
            self.query(i, i+1)
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


n, q = map(int, input().split())

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

People = []
for _ in range(q):
    People.append(int(input()))

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for x in ST.values():
    print(x)


Measured memory_bytes: 158896
import java.util.*;
import java.lang.*;


public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int N = sc.nextInt();

        int ans = H+W;
        for(int h=0; h<=H; h++) for(int w=0; w<=W; w++) if(H*W-(H-h)*(W-w)>=N) ans = Math.min(ans, h+w);
        System.out.println(ans);
    }


}


Measured memory_bytes: 23124