akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

n = max(A).bit_length()

cnt = [0]*n

for x in A:
	for i, y in enumerate("{:b}".format(x).zfill(n)[::-1]):
		if y == "1":
			cnt[i] += 1

ans = 0

for i, c in enumerate(cnt):
	bit_sum = (c*(N-c)%mod) * pow(2, i, mod) % mod
	ans = (ans+bit_sum)%mod

print(ans)


Measured memory_bytes: 131716
// include
#include <array>
#include <algorithm>
#include <set>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <string>
#include <unordered_map>


// pow(10, 15) 10の15乗

//  多倍長整数
#include <boost/multiprecision/cpp_int.hpp>
using big_int = boost::multiprecision::cpp_int;


// ============================================
int main() {
  std::string S;
  std::string T;
  
  
  std::cin >> S;
  std::cin >> T;
  int cnt = 0;
  auto strSize = S.size();
  for (int i = 0; i < strSize; ++i) {
    if (S[i] != T[i]) {
      cnt++;
    }
  }
  std::cout << cnt << std::endl;
}



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

typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
const double pi = 3.141592653589793238;

ll gcd(ll a, ll b) { return __gcd(a,b); } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

void printV(vector<int> &v);
void printVV(vector<vector<int>> &vv);

void printPQ(priority_queue<int> pq);

int main() {
  int X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;

  vector<int> QA(A);
  vector<int> QB(B);
  vector<int> QC;

  for(int i = 0; i < A; i++) cin >> QA.at(i);
  for(int i = 0; i < B; i++) cin >> QB.at(i);
  for(int i = 0; i < C; i++) {
    int q;
    cin >> q;
    QC.push_back(q);
  };

  sort(QA.begin(), QA.end(), greater<int>());
  sort(QB.begin(), QB.end(), greater<int>());
  // sort(QC.begin(), QC.end(), greater<int>());

  for(int i = 0; i < X; i++) {
    QC.push_back(QA.at(i));
  }
  for(int i = 0; i < Y; i++) {
    QC.push_back(QB.at(i));
  }

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

  int64_t sum = 0;
  for (int i = 0; i < X+Y; i++) {
    sum += QC.at(i);
  }

  cout << sum << endl;
}


// ベクターの中身を全部出力
void printV(vector<int> &v) {
  cout << "  [ ";
  for(int i = 0; i < (int)v.size(); i++) {
    cout << v.at(i) << " ";
  }
  cout << "]" << endl;
}

void printVV(vector<vector<int>> &vv) {
  cout << "{" << endl;
  for(int i = 0; i < (int)vv.size(); i++) {
    cout << "  [ ";
    for(int j = 0; j < (int)vv.at(i).size(); j++) {
      cout << vv.at(i).at(j) << " ";
    }
    cout << "]," << endl;
  }
  cout << "}" << endl;
}

void printPQ(priority_queue<int> pq) {
  cout << "----------  QA  ----------" << endl;
  while (!pq.empty()) {
    cout << pq.top() << endl;
    pq.pop();
  }
}


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

int main(){
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  
  int sol, sug;
  double conc = 0.0;
  for (int i = 0; i <= f; i += 100 * a){
    for (int j = 0; j <= f - i; j += 100 * b){
      int rem = min(f - i - j, (i + j) / 100 * e);
      for (int k = 0; k <= rem; k += c){
        int l = d * ((rem - k) / d);
        if (i + j + k + k == 0) continue;
        double cur_conc = (double)(100 * (k + l)) / (i + j + k + l);
        if (conc <= cur_conc){
          conc = cur_conc;
          sug = k + l;
          sol = i + j + k + l;
        }
      }
    }
  }
  cout << sol << " " << sug << endl;
}


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

int main() {
	long long n,c;
	cin>>n>>c;
	long long w[n],p[n];
	long long i,j;
	for(i=0;i<n;i++)
		cin>>w[i]>>p[i];
	long long a[n+1][c+1];	

	for(i=0;i<=n;i++){
		for(j=0;j<=c;j++){
			if(i==0)a[i][j]=0;
			else{
				if(w[i-1]<=j)
					a[i][j]=max(a[i-1][j],a[i-1][j-w[i-1]]+p[i-1]);
				else a[i][j]=a[i-1][j];
				}
		}		
	}	
	cout<<a[n][c];
	return 0;
}

Measured memory_bytes: 79104
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    char str[10];
    scanf("%s",str);
    int len=strlen(str);
    int i;
    for(i=0;i<len;i++){
        if(str[i]=='A'){
            if(str[i+1]=='C'){
                break;
            }
        }
    }
    if(i==len) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h> 
#include <string> 
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;

int main() {

	long res;
	long N, M; cin >> N >> M; if (N >= M) { cout << 0 << endl; return 0; }
	long X[100009]; for (int i = 1; i <= M; i++) cin >> X[i];

	sort(X + 1, X + M + 1);

	long dX[100009]; for (int i = 1; i <= M - 1; i++) dX[i] = X[i + 1] - X[i];

	sort(dX + 1, dX + M ); 

	res = accumulate(dX + 1, dX + M - N + 1, (long)0);

	cout << res << endl;

}

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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
int mod = 998244353;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}

/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  

double eps = .000000001;

int main ()
{
  prep();
  vector<pair<int, int> > graph[1001][1001];
  vector<pair<int, int> > opp[1001][1001];
  int n;
  cin >> n;
  for (int i=0; i<n; i++){
      int arr[n-1];
      for (int j=0; j<n-1; j++){
          cin >> arr[j];
      }
      for (int j=1; j<n-1; j++){
          int a = min(i+1, arr[j]);
          int b = max(i+1, arr[j]);
          int toa = min(i+1, arr[j-1]);
          int tob = max(i+1, arr[j-1]);
          graph[toa][tob].emplace_back(a, b);
          opp[a][b].emplace_back(toa, tob);
      }
  }
  bool vis[1001][1001];
  memset(vis, false, sizeof(bool)*1001*1001);
  queue<pair<pair<int, int>, int> > q;
  for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
          if (j >= i){
              break;
          }
          if ((int)opp[j+1][i+1].size() == 0){
              q.emplace(make_pair(j+1, i+1), 1);
          }
      }
  }
  
  int maxday = -1;
  while (!q.empty()){
      pair<pair<int, int>, int> f = q.front();
      q.pop();
      int a = f.first.first;
      int b = f.first.second;
      
      int len = f.second;
      
      if (vis[a][b]){
          continue;
      }
      //cout << a << " " << b << " " <<len << endl;
      maxday = max(maxday, len);
      // mark as vis if reqs are done
     
      vis[a][b] = true;
      
      for (int i=0; i<graph[a][b].size(); i++){
          int cura = graph[a][b][i].first;
          int curb = graph[a][b][i].second;
          
          bool good = true;
          for (int j=0; j<opp[cura][curb].size(); j++){
              if (!vis[opp[cura][curb][j].first][opp[cura][curb][j].second]){
                  good = false;
                  break;
              }
          }
          
          if (good){
              q.emplace(graph[a][b][i], len+1);
          }
          
      }
      
  }
  for (int i=0; i<n && maxday != -1; i++){
      for (int j=0; j<n; j++){
          if (j >= i){
              break;
          }
          if (!vis[j+1][i+1]){
              maxday = -1;
              break;
          }
      }
  }
  cout << maxday;
  return 0; 
}

Measured memory_bytes: 79488
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int area = a*b;
		int length = (a+b)*2;
		System.out.println(area + " " + length);
		sc.close();
	}
}


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

namespace AtCoder
{
    class Program
    {
        static Stack<int[]> dp;

        static void Main(string[] args)
        {
            //[summary]C - Vacation
            int N = int.Parse(Console.ReadLine());
            dp = new Stack<int[]>();

            //スタート時は参照(Peek)するものがないので、空の配列を入れておく
            dp.Push(new int[3]);

            for(int i = 0; i < N; i++)
            {
                Update();

                //Console.WriteLine(String.Join(" ", dp.Peek()));
            }

            Console.WriteLine(dp.Peek().Max());            
        }

        static void Update()
        {
            var last = dp.Peek();
            var today = ReadLine();
            var sum = new int[3];

            for(int i = 0; i < 3; i++)
            {
                for(int j = 0; j < 3; j++)
                {
                    if (i != j)
                    {
                        if (last[i] + today[j] > sum[j])
                        {
                            sum[j] = last[i] + today[j];
                        }
                    }
                }
            }

            dp.Push(sum);
        }

        static List<int> ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => int.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 26032
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	var abcd string
	fmt.Scan(&abcd)

	arr := strings.Split(abcd, "")
	len := 4

	for bit := 0; bit < (1 << uint(len-1)); bit++ {
		expr := arr[0]
		eval, _ := strconv.Atoi(arr[0])
		for i := 0; i < len-1; i++ {
			if 1&(bit>>uint(i)) == 1 {
				expr += "+" + arr[i+1]
				tmp, _ := strconv.Atoi(arr[i+1])
				eval += tmp
			} else {
				expr += "-" + arr[i+1]
				tmp, _ := strconv.Atoi(arr[i+1])
				eval -= tmp
			}
		}

		if eval == 7 {
			fmt.Printf("%v=7\n", expr)
			return
		}
	}
}


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

struct Edge { int to; ll cost; };
vector<Edge> G[1010];
ll INF = 1e18;

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

  int V, E; cin >> V >> E;
  int r; cin >> r;
  vector<ll> d(V, INF);

  for (int i = 0; i < E; i++) {
    int a, b; cin >> a >> b;//  a--; b--;
    ll c; cin >> c;
    G[a].emplace_back(Edge({b, c}));
    // G[b].emplace_back(Edge({a, c}));
  }

  d[r] = 0;
  for (int t = 0; t < V * 2; t++) {
    for (int i = 0; i < V; i++) {
      if (d[i] == INF) continue;
      for (auto e: G[i]) {
        if (d[e.to] > d[i] + e.cost) {
          d[e.to] = d[i] + e.cost;
          if (t > V) {
            cout << "NEGATIVE CYCLE" << '\n';
            return 0;
          }
        }
      }
    }
  }
  for (ll i = 0; i < V; i++) {
    ll ans = d[i];
    if (ans == INF) cout << "INF" << '\n';
    else cout << ans << '\n';
  }

  return 0;
}


Measured memory_bytes: 3308
#include <algorithm>
#include <cassert>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

bool test(int N, int M, const vector<vector<int>>& A, int k)
{
    vector<bool> used(M, false);

    vector<vector<int>::const_iterator> ps(N);
    vector<vector<int>::const_iterator> ends(N);
    for (int i = 0; i < N; ++i) {
        ps[i] = A[i].begin();
        ends[i] = A[i].end();
    }

    while (true) {
        vector<int> cnt(M);
        for (int i = 0; i < N; ++i) {
            if (ps[i] != ends[i])
                ++cnt[*ps[i]];
        }

        vector<pair<int, int>> rank;
        for (int i = 0; i < M; ++i) {
            rank.push_back(make_pair(cnt[i], i));
        }
        sort(rank.begin(), rank.end(), greater<pair<int, int>>());

        if (rank[0].first > k) {
            for (auto pr : rank) {
                int c = pr.first;
                int i = pr.second;
                if (c <= k)
                    break;
                used[i] = true;
            }

            for (int i = 0; i < N; ++i) {
                if (ps[i] == ends[i])
                    continue;

                while (ps[i] != ends[i] && used[*ps[i]])
                    ++ps[i];
                if (ps[i] == ends[i])
                    return false;
            }
        } else {
            break;
        }
    }

    return true;
}

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

    vector<vector<int>> A(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> A[i][j];
            --A[i][j];
        }
    }

    int mn = 0;
    int mx = 300;
    while (mx - mn > 1) {
        int mid = (mn + mx) / 2;
        if (test(N, M, A, mid))
            mx = mid;
        else
            mn = mid;
    }

    cout << mx << '\n';

    return 0;
}


Measured memory_bytes: 768
def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    K = int(buflist[1])
    count = 0
    for i in range(0, N, 2):
        count += 1
    if count >= K:
        print("YES")
    else:
        print("NO")

if __name__ == '__main__':
    main()


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

typedef struct
{
  int h, p;
} Rect;

int main()
{
  int m;
  cin >> m;
  while (m--) {
    vector<vector<int> > map(5, vector<int>(6, 0));
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j)
	cin >> map[i][j];
    }

    for (int i = 0; i < 5; ++i) {
      for (int j = 1; j < 5; ++j) {
	if (map[j][i] != 0)
	  map[j][i] += map[j-1][i];
      }
    }

    int ans = 0;
    for (int i = 0; i < map.size(); ++i) {
      stack<Rect> stack;
      for (int j = 0; j < map[i].size(); ++j) {
	if (stack.empty()) {
	  stack.push((Rect){map[i][j], j});
	} else if (stack.top().h < map[i][j]) {
	    stack.push((Rect){map[i][j], j});
	} else if (stack.top().h > map[i][j]) {
	  int left = j;
	  while (!stack.empty() && stack.top().h >= map[i][j]) {
	    const Rect rect = stack.top();
	    stack.pop();
	    ans = max(ans, rect.h * (j - rect.p));
	    left = rect.p;
	  }
	  stack.push((Rect){map[i][j], left});
	}
      }
    }

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

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

using namespace std;

int main(){

    int a, b, c;
    cin >> a >> b >> c;

    int count = 0;

    if(a != b && b != c && c != a){
        count = 3;
    }else if(a == b && b == c){
        count = 1;
    }else{
        count = 2;
    }

    cout << count << endl;
    return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define du2(a,b) scanf("%d %d",&(a),&(b))
#define du1(a) scanf("%d",&(a));
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}
void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}
inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
map<string, int> vis;
std::vector<string> v;
string x;
int main()
{
    //freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    n = readint();
    int ans = 0;
    repd(i, 1, n)
    {
        cin >> x;
        vis[x]++;
        if (vis[x] > ans)
        {
            ans = vis[x];
        }
    }
    for (auto t : vis)
    {
        if (t.se == ans)
        {
            v.push_back(t.fi);
        }
    }
    sort(ALL(v));
    for(auto y: v)
    {
        cout << y << endl;
    }

    return 0;
}




Measured memory_bytes: 26932
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.next());
        String s = sc.next();
        System.out.println(s.length() <= k ? s : s.substring(0, k) + "...");
    }
}


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

int main() {
    int N;
    string S, T, ans;

    cin >> N;
    cin >> S >> T;
    for (int i = 0; i < N; i++) {
        ans += S[i];
        ans += T[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	// sum[i][j]: iから始まりjで終わる数がいくつあるか
	sum := make([][]int, 10)
	for i := range sum {
		sum[i] = make([]int, 10)
	}
	for i := 1; i <= n; i++ {
		x := strconv.Itoa(i)
		sum[x[0]-'0'][x[len(x)-1]-'0']++
	}

	ans := 0
	for i := 1; i <= n; i++ {
		x := strconv.Itoa(i)
		ans += sum[x[len(x)-1]-'0'][x[0]-'0']
	}
	puts(ans)
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


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

typedef long long ll;
const ll INF = 1LL << 60;
const ll VMAX = 100100;

inline bool chmin(ll& a, ll b) { if (a > b) { a = b; return true; } return false; }
inline bool chmax(ll& a, ll b) { if (a < b) { a = b; return true; } return false; }

int N, W;
vector<ll> wi, vi;
vector<vector<ll>> sum;

int main() {

  cin >> N >> W;
  wi = vector<ll>(N+10,0);
  vi = vector<ll>(N+10,0);
  sum = vector<vector<ll>>(N+10,vector<ll>(VMAX,INF));

  for (ll i=0; i<N; i++){
    cin >> wi.at(i) >> vi.at(i);
  }

  sum.at(0).at(0) = 0;

  for (ll i=0;i<N;i++){
    for (ll j=0;j<VMAX;j++){
      if (j-vi.at(i)>=0) {
        chmin(sum.at(i+1).at(j),sum.at(i).at(j-vi.at(i)) + wi.at(i));
      }
      chmin(sum.at(i+1).at(j),sum.at(i).at(j));
    }
  }

  ll ans = 0;
  for (int j=0;j<VMAX;j++){
    if (sum.at(N).at(j) <= W) ans = j;
  }

  cout << ans << endl;
}

Measured memory_bytes: 87296
import sys
from operator import add, itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(lambda n: int(n) - 1, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    query = sorted([(left - 1, right, idx) for idx, (left, right) in enumerate(lr)], key=itemgetter(1))
    seg_tree = SegmentTree([0] * N, add, 0)
    c_to_idx = [-1] * N
    
    p_right = 0
    ans = [0] * Q
    for left, right, idx in query:
        for i in range(p_right, right):
            if c_to_idx[c[i]] != -1:
                seg_tree.update(c_to_idx[c[i]], 0)
            seg_tree.update(i, 1)
            c_to_idx[c[i]] = i
        p_right = right
        ans[idx] = seg_tree.query(left, right)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 273480
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(){
  int h,w;
  string map[1000];

  cin >> h >> w;
  for (int i = 0; i < h; i++) cin >> map[i];

  queue<pair<int,int>> todo;
  vector<vector<int>> seen(h,vector<int>(w,-1));
  //初期の黒マスをすべてtodoリストのキューにプッシュ
  for (int i = 0; i < h; i++){
    for (int j = 0; j < w; j++){
      if(map[i][j] == '#'){
        todo.push(make_pair(i,j));
        seen[i][j] = 0;
      }
    }
  }


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

  while(!todo.empty()){
    pair<int,int> pos = todo.front();
    todo.pop();
    int x = pos.first;
    int y = pos.second;
    for (int i = 0; i < 4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
      if(map[nx][ny] == '#') continue;
      if(seen[nx][ny] == -1){
        todo.push(make_pair(nx,ny));
        map[nx][ny] = '#';
        seen[nx][ny] = seen[x][y] + 1;
      }
    }
  }

  // sort(seen.begin(), seen.end());

  // cout << seen[h-1][w-1] << endl;

  int currentmax = seen[0][0];
  for (int i = 0; i < h; i++){
    for (int j = 0; j < w; j++){
        if(seen[i][j] > currentmax) currentmax = seen[i][j];
    }
  }
  cout << currentmax << endl;

}

Measured memory_bytes: 13456
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

struct Node {
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node *treeMinimum(Node *x)
{
    while (x->left != NIL) x = x->left;
    return x;
}

Node *find(Node *u, int k)
{
    while (u != NIL && k != u->key) {
        if (k < u->key) u = u->left;
        else u = u->right;
    }

    return u;
}

Node *treeSuccessor(Node *x)
{
    Node *y;

    if (x->right != NIL) return treeMinimum(x->right);
    y = x->parent;
    while (y != NIL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

void treeDelete(Node *z)
{
    Node *y;    // 削除する対象
    Node *x;    // y の子

    // 削除する節点を決める
    if (z->left == NIL || z->right == NIL) y = z;
    else y = treeSuccessor(z);

    // y の子 x を決める
    if (y->left != NIL) {
        x = y->left;
    } else {
        x = y->right;
    }

    if (x != NIL) {
        x->parent = y->parent;
    }

    if (y->parent == NIL) {
        root = x;
    } else {
        if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
    }

    if (y != z) {
        z->key = y->key;
    }

    free(y);
}

void insert(int k)
{
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while (x != NIL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u)
{
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u)
{
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main()
{
    int n, i, x;
    string com;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        cin >> com;
        if (com[0] == 'f') {
            Node *t;
            scanf("%d", &x);
            t = find(root, x);
            if (t != NIL) printf("yes\n");
            else printf("no\n");
        } else if (com == "insert") {
            scanf("%d", &x);
            insert(x);
        } else if (com == "print") {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        } else if (com == "delete") {
            scanf("%d", &x);
            treeDelete(find(root, x));
        }
    }

    return 0;
}


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

#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

int main() {
    ll M, N;
    cin >> N >> M;

    if (N%2 == 0) {
        rep(i, M) {
            if (i < M/2) {
                cout << i+1 << " " << 2*M+1-i << endl;
            }
            else {
                cout << i+1 << " " << 2*M-i << endl;
            }
        }
    }
    else {
        int l = 1, r = N;
        rep(i, M) {
            cout << l << " " << r << endl;
            l++;
            r--;
        }
    }
}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int expr(string& s, int& i);
int term(string& s, int& i);
int factor(string& s, int& i);
int number(string& s, int& i);

int expr(string& s, int& i) {
    int val = term(s, i);
    while (s[i] == '+' || s[i] == '-') {
        char op = s[i];
        ++i;
        int val2 = term(s, i);
        if (op == '+') val += val2;
        else val -= val2;
    }
    return val;
}

int term(string& s, int& i) {
    int val = factor(s, i);
    while (s[i] == '*' || s[i] == '/') {
        char op = s[i];
        ++i;
        int val2 = factor(s, i);
        if (op == '*') val *= val2;
        else val /= val2;
    }
    return val;
}

int factor(string& s, int& i) {
    if (isdigit(s[i])) return number(s, i);
    ++i;
    int res = expr(s, i);
    ++i;
    return res;
}

int number(string& s, int& i) {
    int res = s[i++] - '0';
    while (isdigit(s[i])) res = res * 10 + s[i++] - '0';
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        s = s.substr(0, s.size() - 1);
        int j = 0;
        cout << expr(s, j) << endl;
    }
}


Measured memory_bytes: 3144
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll min(ll a, ll b){
    if(a < b) return a;
    else return b;
}
ll max(ll a, ll b){
    if(a > b) return a;
    else return b;
}
int main(){
    cout << fixed << setprecision(10);
    ll n,a,b;
    cin >> n >> a >> b;
    if((b - a)%2 == 0){
        cout << (b - a)/2 << endl;
    }else{
        if(n -  a > b - 1){
            cout <<a  + (b - (a - 1) - 1)/2 << endl;
        }else{
            cout << n - b + 1 + (n - (a  + (n - b)) - 1)/2 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long ans=0,a[5],n;
	cin>>n;
	for(int i=0;i<5;i++){
		a[i]=0;
	}
	for(long long i=0;i<n;i++){
		string s;
		cin>>s;
		if(s[0]=='A'){
			a[0]++;
		}
		else{
			if(s[0]=='C'){
				a[1]++;
			}
			else{
				if(s[0]=='H'){
					a[2]++;
				}
				else{
					if(s[0]=='M'){
						a[3]++;
					}
					else{
						if(s[0]=='R'){
							a[4]++;
						}
					}
				}
			}
		}
	}
	for(int i=0;i<5;i++){
		for(int j=i+1;j<5;j++){
			for(int k=j+1;k<5;k++){
				ans+=a[i]*a[j]*a[k];
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP2(i,n,s) for(int i=(int)s;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

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

    ll s = x * ((a+x-1)/x);
    if (s > b) cout << 0 << endl;
    else cout << (b-s)/x+1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

int main(){
    int temp;
    for(int i = 0; i < 5; i++){
        cin >> temp;
        if(temp == 0){
            cout << i+1 << endl;
            return 0;
        }
    }
    return 0;

}

Measured memory_bytes: 3588
n=int(input())
#a,b=map(int,input().split())
a=list(map(int,input().split()))
#n=int(input())
#s=input()

sa=sum(a)
ans=10**10+1
x=0
for i in range(0,n-1):
  x+=a[i]
  if abs(2*x-sa)<ans:
    ans=abs(2*x-sa)
print(ans)

Measured memory_bytes: 23796
A, B, C, D = map(int, input().split())

Thit = A
Tatk = B
Ahit = C
Aatk = D
win = False

while True:
    Ahit = Ahit - Tatk
    if Ahit <= 0:
        win = True
        break
    Thit = Thit - Aatk
    if Thit <= 0:
        win = False
        break

if win:
    print("Yes")
else:
    print("No")

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

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

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

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

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

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

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

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


int N; string s;
bool dp[30005][4][1005];

void solve() {
    cin >> N >> s;
    dp[0][0][0] = true;

    rep(i, N){
        rep(j, 4){
            rep(k, 1000){
                if(dp[i][j][k] == false) continue;

                dp[i+1][j][k] = true;
                if(j <= 2){
                    dp[i+1][j+1][k*10 + (s[i]-'0')] = true;
                }
            }
        }
    }

    ll ans = 0;
    rep(i, 1000) if(dp[N][3][i]) ans++;

    cout << ans << endl;
}

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


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


using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	int odd = 0, even = 0;

	for (int i = 0; i < n; ++i) {
		int a;
		scanf("%d", &a);

		if(a&1) odd++;
		else even++;
	}
	even += odd/2;
	odd %=2;
	if(odd == 1) puts("NO");
	else puts("YES");

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
typedef long long llong;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   int n;
   cin >> n;
   vector<int> p(n);
   rep(i, n) cin >> p[i];
   int ans = 0;
   for (int i = 1; i < n - 1; i++) {
      if (p[i] > p[i - 1] && p[i] < p[i + 1])
         ans++;
      else if (p[i] > p[i + 1] && p[i] < p[i - 1])
         ans++;
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define int               long long
#define M                 1000000007
#define MM                998244353
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}
template<typename T1,typename T2>std::istream& operator>>(std::istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>std::ostream& operator<<(std::ostream& out,pair<T1,T2> &a){out<<a.fr<<" "<<a.sc;return out;}

const int N=0;

void solve(){
	string s;
	cin>>s;
	for(char x:s)cout<<'x';
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SEIVE
		seive();
	#endif
	#ifdef NCR
		init();
	#endif
	#ifdef DSU
		cleardsu(MAXDSUSIZE);
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 256
C = { 
  48 => 'light fly',
  51 => 'fly',
  54 => 'bantam',
  57 => 'feather',
  60 => 'light',
  64 => 'light welter',
  69 => 'welter',
  75 => 'light middle',
  81 => 'middle',
  91 => 'light heavy',
  9999 => 'heavy'
}

while s = gets
  w = s.to_f
  n = nil 
  C.sort.each { |k, v|
    if w <= k
      n = v 
      break
    end 
  }
  n = C[9999] if n.nil?

  puts n
end

Measured memory_bytes: 54000
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int b=sc.nextInt();
    int c=sc.nextInt();
    int d=0;
    if(a>b){
      d=a;
      a=b;
      b=d;
    }
    if(b>c){
      d=b;
      b=c;
      c=d;
    }
    if(a>b){
      d=a;
      a=b;
      b=d;
    }
    System.out.println(a+" "+b+" "+c);
  }
}


Measured memory_bytes: 26112
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string>
#include<cassert>
using namespace std;
#define N1 4
#define N2 16
#define LIMIT 100

static const int dx[4] = {0,-1,0,1};
static const int dy[4] = {1,0,-1,0};
static const char dir[4] = {'r','u','l','d'};
int MDT[N2][N2];

struct Puzzle{int f[N2],space,MD;};

Puzzle state;
int limit;
int path[LIMIT];

int getAllMD(Puzzle pz){
  int sum = 0;
  for(int i=0;i<N2;i++){
    if(pz.f[i]==N2) continue;
    sum += MDT[i][pz.f[i] - 1];
  }
  return sum;
}

bool isSolved(){
  for(int i=0;i<N2;i++){
    if(state.f[i]!= i+1) return false;
  }
  return true;
}

bool dfs(int depth,int prev){
  if(state.MD == 0) return true;
  if(depth + state.MD > limit) return false;

  int sx = state.space / N1;
  int sy = state.space % N1;
  Puzzle tmp;

  for(int r=0;r<4;r++){
    int tx = sx + dx[r];
    int ty = sy + dy[r];
    if(tx < 0 || ty < 0 || tx >= N1 || ty >= N1) continue;
    if(max(prev,r)-min(prev,r) == 2) continue;
    tmp = state;
    state.MD -= MDT[tx*N1 + ty][state.f[tx*N1 + ty] - 1];
    state.MD += MDT[sx*N1 + sy][state.f[tx*N1 + ty] - 1];
    swap(state.f[tx*N1 +ty],state.f[sx*N1 + sy]);
    state.space = tx*N1 + ty;
    if(dfs(depth + 1,r)){
      path[depth] = r;
      return true;
    }
    state = tmp;
  }

  return false;
}

string iterative_deepening(Puzzle in){
  in.MD = getAllMD(in);

  for(limit = in.MD;limit<= LIMIT;limit++){
    state = in;
    if(dfs(0,-100)){
	string ans = "";
	for(int i=0;i<limit;i++) ans += dir[path[i]];
	return ans;
      }
  }

  return "unsolvable";
}

int main(){
  for(int i=0;i<N2;i++){
    for(int j=0;j<N2;j++){
      MDT[i][j] = abs(i/N1 - j/N1) + abs(i%N1 - j%N1);
    }
  }

  Puzzle in;
  for(int i=0;i<N2;i++){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }
  string ans = iterative_deepening(in);
  cout << ans.size() << endl;

  return 0;
}



Measured memory_bytes: 3192
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Random;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	int D;
	int[] c;
	int[][] s;

	int[] ans;

	long score(int[] a, int dd) {
		int[] last = new int[26];

		long res = 0;

		for (int d = 0; d < dd; d++) {
			res += s[d][a[d]];
			last[a[d]] = d + 1;

			for (int j = 0; j < 26; j++) {
				res -= (c[j] * (d + 1 - last[j]));
			}
//			System.err.println(res);
		}
		return res ;
	}
	
	//問題iについてのスコア
	long scores(int i, int[] a) {
		int last = 0;
		long res = 0;

		for (int d = 0; d < D; d++) {
			res += s[d][i];
			last = d + 1;

			res -= (c[i] * (d + 1 - last));
		}
		return res ;		
	}

	public void _main(String[] args) {
		long st = System.currentTimeMillis();
		Scanner sc = new Scanner(in);

		D = sc.nextInt();
		c = new int[26];
		for (int i = 0; i < 26; i++) {
			c[i] = sc.nextInt();
		}

		s = new int[D][26];
		for (int i = 0; i < D; i++) {
			for (int j = 0; j < 26; j++) {
				s[i][j] = sc.nextInt();
			}
		}

		sc.close();

		ans = new int[D];


		for(int d=0;d<D;d++) {
			long max = score(ans, d+1);
			
			for(int i=0;i<26;i++) {
				int t = ans[d];
				ans[d] = i;
				long s = score(ans, d+1);
				
				if(s > max) {
					max = s;
				}else {
					ans[d] = t;
				}
			}
		}
		Random random = new Random();
		long max = score(ans, D);
		while (System.currentTimeMillis() - st < 1900) {
			int d = random.nextInt(D);
			int i = random.nextInt(26);
			
			int t = ans[d];
			if(t==i) continue;
			
			long s = 0;
			s -= scores(i,ans);
			s -= scores(t,ans);
			
			ans[d] = i;
			
			s += scores(i, ans);
			s += scores(t, ans);
			
			if(s > 0) {
				max += s;
			}else {
				ans[d] = t;
			}
		}

//		System.err.println(max);

		StringBuilder sb = new StringBuilder();
		for (int x : ans) {
			sb.append(x+1);
			sb.append("\n");
		}
		out.print(sb.toString());

	}

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


Measured memory_bytes: 47872
#include "bits/stdc++.h"
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair <ll, ll > pll;

bool comp(const pll &a, const pll &b) {
	return a.first < b.first;
}
std::vector<int> enum_div(int n)//nの約数を列挙
{
	std::vector<int> ret;
	for (int i = 1; i*i <= n; ++i)
	{
		if (n%i == 0)
		{
			ret.push_back(i);
			if (i != 1 && i*i != n)
			{
				ret.push_back(n / i);
			}
		}
	}
	return ret;
}


template<int N>
int factorial() {
	return factorial<N - 1>() * N;
}

template<>  /// 特殊化：factorial<N=”1”>だったら，値を返す
int factorial<1>() {
	return 1;
}
int main()
{
	priority_queue<int> q;
	string s = {};
	string s1 = {};
	ll h = 0, w = 0, k = 0, a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, ans = 0;
	ll x[300005] = {};
	ll y[300005] = {};
	ll y2[302][302] = {};
	cin >> a;
	for (int i = 0; i < a; i++)
	{
		cin >> x[i];
	}
	b = x[0];
	for (int i = 0; i < a; i++)
	{
		if (x[i]<=b)
		{
			ans++;
			b = x[i];
		}
	}

	cout << ans << endl;



	//return 0;

	/*cout << c << endl;
	cout << b << endl;*/
	//cout << fixed << setprecision(10) <<tmp << endl;
	//cout<<factorial<10><<endl;
	return 0;
}
//2つの組の数をソートしたりするやつ
//vector<pair<ll, ll> > hoges(a);
//for (int i = 1; i <= a; i++)
//{
//	cin >> h;
//	hoges[i - 1] = make_pair(h, i);
//}
//sort(hoges.begin(), hoges.end(), comp);
//for (int i = 0; i < a; i++)
//{
//	cout << hoges[i].second << endl;
//}


Measured memory_bytes: 2560
n = gets.chomp!.to_i
x_n = gets.chomp!.split(" ").map(&:to_i)
y_n = x_n.sort
 
left = y_n[y_n.length / 2 - 1]
right = y_n[y_n.length / 2]
 
x_n.each do |x|
    if x <= left
        puts right
    else
        puts left
    end
end

Measured memory_bytes: 23396
/*
    STARK_BOY
*/
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repe(i,a,b) for(ll i=a;i<=b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
typedef pair<ll,ll> pii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setbitc(x) __builtin_popcount(x)
#define init(x,a) memset(x,a,sizeof(x))
#define PI           3.14159265358979323846  /* pi */
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
#define N 1005
//Variables Start
ll inf=1e18,MOD=1e9+7;
ll n,m,k,ar[N],br[N];
string s,s1;
//Variables End

int main()
{
    ios
    int ti=1;
    //cin>>ti;
    while(ti--)
    {
		cin>>m>>n;
		ll maxi=0;
		rep(i,0,n){cin>>ar[i]>>br[i];maxi=max(maxi,ar[i]);}
		maxi+=(m+1);
		vi dp(maxi,inf);
		dp[0]=0;
		rep(sum,1,maxi)
		{
			rep(i,0,n)
			{
				if(sum>=ar[i])
				dp[sum]=min(dp[sum],dp[sum-ar[i]]+br[i]);
			}
		}
		ll ans=inf;
		rep(i,m,maxi)ans=min(ans,dp[i]);
		cout<<ans<<endl;

    }
    return 0;
        
}

Measured memory_bytes: 384
import Control.Monad
import Data.List
 
main :: IO ()
main = do
  [n, c] <- getInts
  ss <- replicateM n $ do
    [s, t, c] <- getInts
    return ((s, t), c)
  print $ solve ss
 
getInts :: IO [Int]
getInts = map read . words <$> getLine
 
solve xs = maximum $ go (f xs) []
  where
    f = map fst . sort
      . concatMap (cnct . sort) 
      . groupBy (\(_, c1) (_, c2) -> c1 == c2)
      . sortBy (\(_, c1) (_, c2) -> compare c1 c2)
      where
        cnct [] = []
        cnct [x] = [x]
        cnct (x:y:zs) =
          case (x, y) of
            (((s1, t1), c), ((s2, t2), _))
              | t1 == s2 -> cnct (((s1, t2), c):zs)
            _ -> x : cnct (y:zs)
    go [] _ = []
    go (l@(s, t):ls) qs =
      let qs' =
            l : filter (\(s', t') ->
                           fromIntegral t' >= fromIntegral s  - 0.5) qs in
      length qs' : go ls qs'

Measured memory_bytes: 107900
N = int(input())
a = list(map(int, input().split()))

ans = 0
cnt = 0
num = 1
for i in range(N):
    if a[i] != num:
        cnt += 1

    else:
        ans += cnt
        cnt = 0
        num += 1

ans += cnt
if 1 not in a:
    print(-1)
else:
    print(ans)


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

int main(){
   int n;
   cin >> n; 
   string s;
   cin >> s;
   if (n%2==1) cout << "No" << endl;
   else {
       if(s.substr(0,n/2)==s.substr(n/2))
       {
           cout << "Yes" << endl;
       }
       else cout << "No" << endl;}
   }

Measured memory_bytes: 256
def selectionSort(A, N):
    counter = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j
        if A[i] != A[minj]:
            counter += 1
            A[i], A[minj] = A[minj], A[i]
    return A, counter

N = int(raw_input())
A = map(int,raw_input().split())

A, counter = selectionSort(A, N)
print " ".join(map(str, A))
print counter

Measured memory_bytes: 6404
#include <bits/stdc++.h>
using namespace std;
int main(){
  while (1){
    int H;
    cin >> H;
    if (H == 0){
      break;
    }
    vector<vector<int>> A(H, vector<int>(7, -1));
    for (int i = 0; i < H; i++){
      for (int j = 1; j <= 5; j++){
        cin >> A[i][j];
      }
    }
    int ans = 0;
    while (1){
      bool update = false;
      for (int i = 0; i < H; i++){
        if (A[i][3] != 0){
          int L = 3;
          while (A[i][L] == A[i][3]){
            L--;
          }
          int R = 3;
          while (A[i][R] == A[i][3]){
            R++;
          }
          if (R - L >= 4){
            for (int j = L + 1; j <= R - 1; j++){
              ans += A[i][j];
              A[i][j] = 0;
              update = true;
            }
          }
        }
      }
      if (!update){
        break;
      }
      for (int i = 1; i <= 5; i++){
        for (int j = H - 2; j >= 0; j--){
          if (A[j][i] != 0){
            int p = j;
            while (A[p + 1][i] == 0){
              swap(A[p][i], A[p + 1][i]);
              p++;
              if (p == H - 1){
                break;
              }
            }
          }
        }
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#include <fstream>
#define inf INFINITY
#define file freopen( "input.txt" , "r" , stdin) ; freopen( "output.txt" , "w" , stdout) ; 
#define Gamed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define _3102_ main()
#define endl '\n'
typedef long long ll ;
typedef unsigned long long ull ; 
typedef long double ld ; 
using namespace std ;
const int N = 1e5+100  ; 
const ll mod = 1e9 + 7  ;



int _3102_ {
    Gamed
    ll n , arr[N] , dp[N] ; 
    cin >> n ; 
    for ( int i = 0 ; i < n ; i ++){
        cin >> arr[i] ; 
    }
    dp[0] = 0 ; 
    dp[1] = abs(arr[0]-arr[1]) ; 
    for ( int i = 2 ; i < n ; i ++){
        dp[i] = min( abs(arr[i-1]-arr[i]) + dp[i-1] , dp[i-2] + abs(arr[i]-arr[i-2])) ; 
    }
    cout << dp[--n] << endl ; 
    return 0;
}

Measured memory_bytes: 1792