akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
 
public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        long l = sc.nextLong();
        long r = sc.nextLong();
        long min = Long.MAX_VALUE;
 
        if (l - r >= 2018) {
            System.out.println(0);
        } else {
            for (long i = l; i <= r ; i++) {
                for (long j = i + 1; j <= r ; j++) {
                    long val = (i % 2019 * j % 2019) % 2019;
                    if (val == 0) {
                        System.out.println(0);
                        return;
                    }
                    min = Math.min(val , min);
                }
            }
            System.out.println(min);
        }
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long ans=0;
  int x;
  cin>>x;
  ans+=(x/500)*1000;
  x%=500;
  ans+=(x/5)*5;
  cout<<ans<<"\n";
  return 0;
  
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define f(i,a,b) for(int i=(a); i<(b);++i)
int main(){
    string s;
    int z=0,o=0;
    cin>>s;
    f(i,0,s.size()){
        if(s[i]=='0') z++;
        else o++;
        }
        o>z?printf("%d\n", 2*z):printf("%d\n", 2*o);
    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>
#include <math.h>

uint64_t get_gcd (uint64_t a, uint64_t b)
{
    if (b == 0) return a;
    else return get_gcd(b, a % b);
}

int main (int argc, char const *argv[])
{
    int64_t N, A[(int)1e5];
    int64_t l[(int)1e5], r[(int)1e5], tmp, ans = 0;

    scanf("%"PRId64, &N);
    for (int i = 0; i < N; i++) {
        scanf("%"PRId64, &A[i]);
    }

    l[0] = 0;
    r[N - 1] = 0;
    for (int i = 1; i < N; i++) {
        l[i] = get_gcd(l[i - 1], A[i - 1]);
        r[N - i - 1] = get_gcd(A[N - i], r[N - i]);
    }

    for (int i = 0; i < N; i++) {
        tmp = get_gcd(l[i], r[i]);
        if (tmp > ans) ans = tmp;
    }

    printf("%"PRId64"\n", ans);
}


Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
					
public class Program
{

	public static void Main()
	{
		solveHelper();
	}
	public static void solveHelper(){
	int n = int.Parse(Console.ReadLine());
	List<int> ls = (new List<string>(Console.ReadLine().Trim().Split(' '))).ConvertAll<int>(int.Parse);
	int q = int.Parse(Console.ReadLine());
	foreach(var x in Console.ReadLine().Trim().Split(' ')) 
		Console.WriteLine(solve(0, int.Parse(x), n, ls) ? "yes" : "no");
	}
	public static bool solve(int p, int t, int n, List<int> ls){
		if(t == 0) return true;
		else if(t < 0 || p >= n) return false;
		else return solve(p+1, t - ls[p], n, ls) || solve(p+1, t, n, ls);}
}


Measured memory_bytes: 17956
#include<bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define forp(i,a,b) for (int i = (a); i <(b); i++)
#define forn(i,a,b) for (int i = (a); i >(b); i--)
#define mod 1000000007
#define multiple_testcases_t int t;cin>>t;while(t--){solve();}
#define single_testcase_t solve();
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;


// <----- Actual solve() function to print output -----> //

void solve()
{
   ll n,m,k=0,w;
   cin>>n>>k>>w;
   m=n/k;
   if(n%k!=0)
   m++;

   cout<<m*w<<" ";
   //cout<<"\n";      //if t>1 uncomment this
}

// MAIN function --------------------------------------------------------------------------//
int main()
{
    fast_io
//  if taking input from input.txt then uncomment below line
//    freopen("input.txt", "r", stdin);
//  if writing output to output.txt then uncomment below line
//    freopen("output.txt", "w", stdout);

    single_testcase_t   //Uncomment this if only single testcase & single answer to print
  //multiple_testcases_t  //Uncomment this if t>1(t is given in question)(multiple testcases)
return 0;
}





Measured memory_bytes: 3648
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = {i:[] for i in range(n)}
ans = 0
for i in range(k):
    b[a[ans]-1].append(ans)
    if len(b[a[ans]-1]) == 2:
        c = [ans]
        ans = a[ans]-1
        while ans != c[0]:
            c.append(ans)
            ans = a[ans]-1
        ans = c[(k-i) % len(c)]
        break
    ans = a[ans]-1
print(ans+1)

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

namespace a
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            long a = long.Parse(input[0]);
            long b = long.Parse(input[1]);
            long c = long.Parse(input[2]);
            long k = long.Parse(input[3]);

            if (k % 2 == 0)
            {
                Console.WriteLine(a - b);
                return;
            }
            Console.WriteLine(b - a);
        }
    }
}

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

int main() {
    ll k,x=0;
    cin >> k;
    for (int i=1;i<=k;i++) {
        x=(x*10+7)%k;
        if (x==0) {cout << i; return 0;}
    }
    cout << -1 <<endl;
}


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

/*-------------------Define Start-------------------*/
typedef bool BL;    					// 布尔类型
typedef char SB;    					// 有符号1字节,8位
typedef unsigned char UB;    			// 无符号1字节,8位
typedef short SW;    					// 有符号短整型,16位
typedef unsigned short UW;    			// 无符号短整型,16位
typedef long SDW;    					// 有符号整型,32位
typedef unsigned long UDW;   			// 无符号整型,32位
typedef long long SLL;    				// 有符号长整型,64位
typedef unsigned long long ULL;			// 无符号长整型,64位
typedef char CH;    					// 单个字符
typedef float R32;    					// 单精度浮点数
typedef double R64;    					// 双精度浮点数

#define Rep(i, n) for (register SDW i = 0; i < (n); ++i)
#define For(i, s, t) for (register SDW i = (s); i <= (t); ++i)
#define rFor(i, t, s) for (register SDW i = (t); i >= (s); --i)
#define foreach(i, c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,0x7f,sizeof(a))
#define LOWBIT(x) ((x)&(-x))

#define MP make_pair
#define PB push_back
#define ft first
#define sd second

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

const ULL mod = 1e9 + 7;				//常用模数(可根据题目需要修改)
const ULL inf = 0x7fffffff;				//用来表示无限大
const ULL infLL = 0x7fffffffffffffffLL;	//用来表示无限大
/*-------------------Define End-------------------*/

const UDW maxN = 1e3 + 7;
SDW H, W, K;
SDW S[13][maxN];
SDW ans = inf;

SDW getSum(SDW x1, SDW y1, SDW x2, SDW y2) {
	return S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1];
}

void input(){
	cin >> H >> W >> K;
	For(i, 1, H) {
		For(j, 1, W) {
			scanf("%1d", &S[i][j]);
			S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]; // 记录为前缀和,方便计算
		}
	}
}

void solve(){
	// 枚举水平方向上的所有切法
	Rep(i, 1 << (H - 1)) { 
		// 在竖直方向上采用贪心切法
		vector< SDW > pos; // 记录水平切的位置
		SDW tmp = i;
		SDW ret = __builtin_popcount(i);
		
		pos.PB(0);
		while(tmp) {
			SDW x = LOWBIT(tmp);
			tmp &= tmp - 1;
			
			pos.PB(__builtin_ctz(x) + 1);
		}
		pos.PB(H);
		
		SDW a = 1, b = 1;
		
		while(b <= W) {
			For(j, 1, pos.size() - 1) {
				if(getSum(pos[j - 1] + 1, a, pos[j], b) > K) {
					if(a == b) { // 无法切开的情况,直接跳出
						b = W + 1;
						ret = inf;
						break;
					}
					else {
						++ret;
						a = b;
						--b;
						break;
					}
				}
			}
			++b;
		}
		
		
		ans = min(ans, ret);
	}
}

void output(){
	cout << ans << endl;
}

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

Measured memory_bytes: 384
#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define endl '\n'
#define vi vector<int>
#define rep(i, n) for (i = 0; i < n; i++)



 
int main()
{ 
  ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   #endif 

   ll n;
   cin>>n;
   std::vector<char> v;
   

   
      while(n>0)
      {  
      	if(n%26==0)
      	{ //cout<<char(26+96);
      	  v.pb(char(26+96));
      	  n=n-26;
      	}
      	else
       // cout<<char((n%26)+96);
        v.pb(char((n%26)+96));
        n=n/26;


      }

  reverse(v.begin(),v.end());
     for (int i = 0; i < v.size(); i++) 
       cout << v[i]; 
    

  
    
}

Measured memory_bytes: 3584
import java.util.Scanner;

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

            int n =scan.nextInt();

            int i =1;

              for(;i<=n;i++){
              
                 if(i%3==0){
                 System.out.print(" "+i);
                 } else {
                   
                   int j=i;

                      while(j>0){

                          if(j%10==3){
                          System.out.print(" "+i);
                          break;
                          }

                      j/=10;

                      }
                   }
                 }                   
                          System.out.println();
        }
     }



Measured memory_bytes: 28676
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <cstring>
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <numeric>
#include <float.h>
using namespace std;
// repマクロの定義
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// allマクロの定義
#define all(v) v.begin(), v.end()
typedef unsigned long long ll;

int main(){
	int N; cin >> N;
	string S; cin >> S;
	int cnt = 1;
	rep(i,N-1){
		if(S[i] != S[i+1]) cnt++;
	}
		cout << cnt << endl;
}	

Measured memory_bytes: 512
#include<stdio.h>
int main(){
  int s;
  scanf("%d",&s);
  int a,b,c,d;
  a=s%10;
  b=(s/10)%10;
  c=(s/100)%10;
  d=(s/1000)%10;   
  if(a==b||b==c||c==d){
    printf("Bad");
  }
  else{
    printf("Good");
  }
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int, int>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<"\n";
#define debug(x) cerr << #x << ":" << (x) << "\n";

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &i : a)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;

  VAR(string, s);
  int N = s.size();
  
  if (s[0] == s.back()) N++;

  if (N % 2 == 0) cout << "Second" << endl;
  else cout << "First" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>

#define TARO 0
#define HANAKO 1

int main(void)
{
    int game, win = 3, draw = 1;
    char taro[101], hanako[101];
    int score[2] = {0, 0};

    scanf("%d", &game);
    for (int i = 0; i < game; i++)
    {
        scanf("%s %s", taro, hanako);
        int result = strcmp(taro, hanako);
        if (result < 0)
            score[HANAKO] += win;
        else if (result == 0)
        {
            score[TARO] += draw;
            score[HANAKO] += draw;
        }
        else
        {
            score[TARO] += win;
        }
    }
    printf("%d %d\n", score[TARO], score[HANAKO]);
    return 0;
}


Measured memory_bytes: 2064
/*input
6
5
3
1
3
4
3
*/
fn main() {
    let mut s = format!("");
    std::io::stdin().read_line(&mut s).expect("");
    let mut m;
    let (mut min, mut max) = (std::i32::MAX, std::i32::MIN);
    for _ in 0..s.clone().trim().parse::<i32>().unwrap() {
        s = format!("");
        std::io::stdin().read_line(&mut s).expect("");
        //println!("{:?}", s);
        m = s.trim().parse::<i32>().unwrap();
        if max < m - min {
            max = m - min;
        }
        if min > m {
            min = m;
        }
    }
    println!("{}", max);
}



Measured memory_bytes: 5044
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b; cin>>a>>b;
	int x=a*b;
	if (x%2) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


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

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


int main()
{
	int x, y, z, k;
	cin >> x >> y >> z >> k;
	vector<ll> a(x), b(y), c(z);
	for(int i = 0; i < x; i++)cin >> a[i]; sort(a.begin(), a.end(), greater<ll>());
	for(int i = 0; i < y; i++)cin >> b[i]; sort(b.begin(), b.end(), greater<ll>());
	for(int i = 0; i < z; i++)cin >> c[i]; sort(c.begin(), c.end(), greater<ll>());

	vector<ll> arr;
	for(int i = 0; i < x; i++) {
		for(int j = 0; j < y; j++) {
			for(int t = 0; t < z; t++) {

				if((i + 1) * (j + 1) * (t * 1) > k + 10)break;
				else arr.emplace_back(a[i] + b[j] + c[t]);
			}
		} 
	}
	sort(arr.begin(), arr.end(), greater<ll>());
	for(int i = 0; i < k; i++)cout << arr[i] << endl;

}

Measured memory_bytes: 18796
import java.util.*;
class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt(); //種類数
    int x = sc.nextInt(); //総合の材料
    int[] param = new int[n];
    
     int sum = 0; //まず最低限必要な材料
    
    for(int i=0 ; i<n ; i++){
      param[i] = sc.nextInt();
      sum += param[i];
    }
    
    int min = x;
    for(int i=0 ; i<n ; i++){
      if(param[i]<=min){
        min = param[i];
      }
    }
    int num = (x-sum)/min;
    System.out.println(n+num);
  }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int G[MAX][MAX];
int color[MAX], d[MAX], p[MAX];
int n;

int prim();

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> G[i][j];
            if(G[i][j] == -1) G[i][j] = INT_MAX;
        }
    }

    cout << prim() << endl;

    // for(int i = 0; i < n; i++){
    //     cout << i << " " << p[i] << endl;
    // }

    return 0;
}

int prim(){
    // プリムのアルゴリズム
    // 重み付きグラフから最小全域木を求め、その辺の重みの合計を求める
    // colorは訪問状態を表す　
    // d[i]は頂点iから繋がる辺の内最小のもの　
    // p[i]は頂点iの親（木なので）
    for(int i = 0; i < n; i++){
        color[i] = WHITE;
        d[i] = INT_MAX;
        p[i] = -1;
    }
    
    d[0] = 0;

    while(1){
        int min = INT_MAX, u = -1;
        
        // 隣接する最小の辺を持つところに行く 頂点番号u 辺のおもみmin
        for(int i = 0; i < n; i++){
            if(d[i] < min && color[i] != BLACK){
                min = d[i];
                u = i;
            }
        }

        // 隣接するところが全てblack、または最小のものが存在しない時は探索終了
        if(u == -1) break;

        // 頂点番号uのところに訪問
        color[u] = BLACK;

        // uから繋がるところでまだ訪問してないところの内、最小のものを見つける
        for(int i = 0 ; i < n; i++){
            if(color[i] != BLACK && G[u][i] != INT_MAX){
                if(d[i] > G[u][i]){
                    d[i] = G[u][i];
                    p[i] = u;
                    color[i] = GRAY;
                }
            }
        }
    }

    int sum = 0;
    for(int i = 0; i < n; i++){
        if(p[i] != -1) sum += G[i][p[i]];
    }

    return sum;
}


Measured memory_bytes: 3088
int main(){
    char top[3];
    int i;
    int count = 0;
    
    scanf("%s", top);
    for (i = 0; i < 3; i++){
        if(top[i] == 'o'){
            count += 1;
        }
    }
    switch(count){
        case 0: printf("700 \n"); break;
        case 1: printf("800 \n"); break;
        case 2: printf("900 \n"); break;
        case 3: printf("1000 \n"); break;
    }
    return 0;
}


Measured memory_bytes: 128
from collections import deque
SA = deque(input())
SB = deque(input())
SC = deque(input())
turn = 'a'
while True:
    if turn == 'a':
        if len(SA) == 0:
            print('A')
            exit()
        turn = SA.popleft()
    if turn == 'b':
        if len(SB) == 0:
            print('B')
            exit()
        turn = SB.popleft()
    if turn == 'c':
        if len(SC) == 0:
            print('C')
            exit()
        turn = SC.popleft()

Measured memory_bytes: 3316
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      int n = sc.nextInt();
      int [] data = new int[n];
      int count = 0;

      for (int i = 0;i<n ;i++ ) {
        data[i] = sc.nextInt();
      }

      for (int i = 1;i<n-1 ;i++ ) {
        if ((data[i-1]<data[i]&&data[i]<data[i+1])||(data[i-1]>data[i]&&data[i]>data[i+1])) {
          count++;
        }
      }

        System.out.println(count);



  }
}


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

using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int> a(n,0);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	vector<int> v(a[n-1]+1,1);
	int k=0;
	for(int i=0;i<n;i++){
		if(v[a[i]]==1&&i<n-1&&a[i]==a[i+1]){
			v[a[i]]=0;
			int s=a[i];
			while(s<=a[n-1]){
				v[s]=0;
				s+=a[i];
			}
		}
		if(v[a[i]]==1){
			k++;
			int s=a[i];
			while(s<=a[n-1]){
				v[s]=0;
				s+=a[i];
			}
		}
	}
	cout<<k<<endl;	
}



Measured memory_bytes: 7940
#include<bits/stdc++.h>
using namespace std;
int n,h,c;
struct p{
    int l;
    int r;
}a[1000005];
bool cmp(p xx,p yy){
    return xx.l>yy.l;
}
int main(int argc, char **argv){
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[c++].l);
        a[c].r=1;
        scanf("%d",&a[c++].l);
    }
    sort(a,a+c,cmp);
    int sum=0;
    for(int i=0;i<c;i++)
    {
        if(a[i].r==1)
        {
            sum++;
            h-=a[i].l;
            if(h<=0)
            {
                printf("%d",sum);
                return 0;
            }
        }
        else if(a[i].r!=1)
        {
            if(h%a[i].l==0) sum+=h/a[i].l;
            else sum+=h/a[i].l+1;
            printf("%d",sum);
            exit(0);
        }
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

class BIT{
public:
  ll n,bit[555555];
  BIT(){fill(bit,bit+555555,0);}
  void add(ll i,ll x){
    while(i<=n){
      bit[i]+=x;
      i+=i&-i;
    }
  }
  ll sum(ll i){
    ll s=0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }
};

BIT b;
int c[555555];
vector<int> v[555555];
vector<P> g[555555];
void Main() {
  ll n,T;
  cin >> n >> T;
  ll a[n];
  rep(i,n) R a[i];
  rep(i,n) v[a[i]].pb(i+1);
  b.n=n+1;
  rep(i,555555) {
    if(v[i].size()) b.add(v[i][0],1);
  }
  ll ans[T];
  mem(ans);
  rep(i,T) {
    ll l,r;
    cin >> l >> r;
    l--,r--;
    g[l].pb(P(r,i));
  }
  rep(i,n) {
    rep(j,g[i].size()) {
      int r=g[i][j].F,k=g[i][j].S;
      ans[k]=b.sum(r+1);
    }
    b.add(v[a[i]][c[a[i]]],-1);
    c[a[i]]++;
    if(c[a[i]]<v[a[i]].size()) b.add(v[a[i]][c[a[i]]],1);
  }
  rep(i,T) pr(ans[i]);
}

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


Measured memory_bytes: 72700
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#define __float128 long double
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

template<class T>
struct BIT{
	vector<T> dat;
	int n;

	BIT(int _n){
		n = _n+10;
		dat.resize(n);
	}

	void add(int x, T val){
		++x;
		for (int i = x; i < n; i += i&-i) dat[i] += val;
	}
	T sum(int x){
		T res = 0;
		++x;
		for (int i = x; i > 0; i -= i&-i) res += dat[i];
		return res;
	}
};

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

	ll a, b, p;
	while (cin >> a >> b >> p, a | b | p){
		ll n = b - a + 1;
		vector<string> v(n);
		rep(i, n) v[i] = to_string(a + i);

		auto sorted = v;
		sorted.push_back("0");
		sort(ALL(sorted));

		BIT<ll> dp(n + 1);

		dp.add(0, 1);
		rep(i, n){
			int id = lower_bound(ALL(sorted), v[i]) - sorted.begin();
			dp.add(id, dp.sum(id) % p);
		}
		cout << (dp.sum(n) + p - 1) % p << endl;
	}

	return 0;
}

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

int N,M;
vector<vector<int>> graph(111111);
long long ans;
int b=0,w=0;
vector<int> bi(111111,-1);

bool BFS(){
	queue<int> que;
	que.push(0);
	bi[0]=0;
	while(!que.empty()){
		int f=que.front();
		que.pop();
		if(bi[f]==0)b++;
		else w++;
		for(auto t:graph[f]){
			if(bi[t]==-1){
				bi[t]=(bi[f]+1)%2;
				que.push(t);
			}
			else if(bi[t]==bi[f])return false;
		}
	}
	return true;
}

int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int A,B;
		cin >> A >> B;
		A--;
		B--;
		graph[A].push_back(B);
		graph[B].push_back(A);
	}
	
	if(BFS())ans=(long long)b*w-M;
	else ans=((long long)N*N-N)/2-M;
	
	cout << ans << endl;
	return 0;
}

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

int main(){
    constexpr long MOD = 1000000007;
    long N;
    cin >> N;
    long dp{N};
    vector<long> sum(4, (N - 1) * N % MOD);
    sum[0] = 0;
    for(long i = 3; i != N + 3; ++i){
        sum[3] = sum[2] - 1 + ((dp += sum[0]) %= MOD);
        swap(sum[1], sum[0]);
        swap(sum[1], sum[2]);
        swap(sum[3], sum[2]);
    }
    cout << dp << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
vector <int>  mp[101];
int A,B,C,D;
int n;
int main() {
 
 
  cin >> n;
 
  cin >> A >> B >> C >> D;
 
  A--;
  B--;
  C--;
  D--;
   
 
  int ans = 100000000;
  int c=n;
  while(c !=0) {
     
    int t = 0;
    int count = 0;
    /*
    for(int i=0;i<n;i++)mp[i].clear();
     
    for(int i=0;i<n;i++) {
      if(c == count) t++,count = 0;
      mp[t].push_back(i);
      count++;
    }
    */
    int x[4]={A%c,B%c,C%c,D%c};
    int y[4]={A/c,B/c,C/c,D/c};
    /*
    for(int i=0;i<n;i++) {
      if(mp[i].size()==0)break;
      for(int j=0;j<mp[i].size();j++) {
    if(mp[i][j] == A) x[0] = j,y[0] = i;
    if(mp[i][j] == B) x[1] = j,y[1] = i;
    if(mp[i][j] == C) x[2] = j,y[2] = i;
    if(mp[i][j] == D) x[3] = j,y[3] = i;
      }
    }
    */
    int ABx,DCx,ABy,DCy;
    ABx = x[0] - x[1] ;
    DCx = x[2] - x[3];
    if(ABx<0) ABx*=-1;
    if(DCx<0) DCx*=-1;
    ABy = y[0]-y[1];
    DCy = y[2] - y[3];
    if(ABy < 0) ABy *= -1;
    if(DCy < 0) DCy *= -1;
 
    if(ABx+ABy+DCx+DCy < ans) ans = ABx+ABy+DCx+DCy;
    if(ans==1){
      for(int I=0;I<4;I++)cout<<x[I]<<' '<<y[I]<<endl;
    }
 
    /*
    for(int i=0;i<n;i++) {
      if(mp[i].size()==0)break;
      for(int j=0;j<mp[i].size();j++) 
    cout <<mp[i][j] << " ";
      cout << endl;
    }
    */
    c--;
  }
     
  cout << ans << endl;
  return 0;
}
 

Measured memory_bytes: 1164
package main

import "fmt"

func main() {
	var A, B int
	fmt.Scan(&A, &B)
	for i := 1; i <= 3; i++ {
		if (A*B*i)%2 == 1 {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")

}


Measured memory_bytes: 512
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_D
#????°???????????????????

def processA(target_list, correct_list, i):

    cost = 0
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(correct_list[i])
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        #print("A", target_list)
    return cost
    
def processB(target_list, correct_list, i):
    minv = correct_list[0]
    target = correct_list[i]

    if minv == target:
        return 10 ** 9
    cost = (minv + target)
    #print(minv, target)
    mmi = target_list.index(minv)
    smi = target_list.index(target)
    target_list[mmi], target_list[smi] = target_list[smi], target_list[mmi]
    
    while not correct_list[i] == target_list[i]:
        min_i = target_list.index(minv)
        change_i = target_list.index(correct_list[min_i])
        cost += (target_list[min_i] + target_list[change_i])
        target_list[min_i], target_list[change_i] = target_list[change_i], target_list[min_i]
        #print("B",target_list)
    return cost
    
def minimum_cost_sort(target_list):
    correct_list = sorted([a for a in target_list])
    cost = 0
    i = 0
    while not correct_list == target_list:
        cost_b = processB([a for a in target_list], correct_list, i)
        cost_a = processA(target_list, correct_list, i)
        cost += min(cost_a, cost_b)
        #print(cost_a, cost_b)
        #print(target_list)
        i += 1
    return cost
def main():
    n_list = input()
    target_list = [int(s) for s in input().split()]
    print(minimum_cost_sort(target_list))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 7856
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
  int n;
  cin >> n;
  
  vector<int>stick(n * 2,0);
  
  for(int i=0;i<n * 2;i++){
    cin >> stick[i];
  }
  
  sort(stick.begin(),stick.end());
  
  int ans = 0;
  
  for(int i=0;i<n;i++){
    ans += min(stick[i * 2],stick[i * 2 + 1]);
  }
  
  cout << ans << endl;
  
  return 0;
}

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

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    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;
    }

}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define N 505


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

	int a[5], k;
	for (int i = 0; i < 5; ++i)
	{
		cin >> a[i];
	}
	cin >> k;
	int f = 1;
	for (int i = 0; i < 5; ++i)
	{
		for(int j = i + 1; j < 5; ++j)
			if(a[j] - a[i] > k)
				f = 0;
		if(!f)
			break;
	}
	if(f)
		cout << "Yay!";
	else
		cout << ":(";
	return 0;
}

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)       
        


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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			if (i * j != n) {
				continue;
			}

			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
typedef struct {
    ll b, c;
} p;

int cmp_ll(const void *, const void *);
int cmp_p(const void *, const void *);

ll n, m;
ll a[100005];
p query[100005];

int main()
{
    ll sum = 0;

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

    for (int i = 0; i < m; i++) {
        scanf("%lld %lld", &query[i].b, &query[i].c);
    }

    qsort(a, n, sizeof(ll), cmp_ll);
    qsort(query, m, sizeof(p), cmp_p);

    int k = 0;
    for (int i = 0; i < n; i++) {
        if (k < m) {
            if (query[k].c > a[i]) {
                sum += query[k].c;
                query[k].b--;

                if (query[k].b == 0) {
                    k++;
                }
            }
            else {
                sum += a[i];
            }
        }
        else {
            sum += a[i];
        }
    }

    printf("%lld\n", sum);

    return 0;
}

int cmp_ll(const void *x , const void *y)
{
    if (*(ll *)x > *(ll *)y) {
        return 1;
    }
    else if (*(ll *) x == *(ll *)y) {
        return 0;
    }
    else {
        return -1;
    }
}

int cmp_p(const void *x, const void *y)
{
    return -1 * cmp_ll(&(((p *)x)->c), &(((p *)y)->c));
}


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

ll combi(ll n, ll r) {
    ll res = 1;
    for (ll i = n; n - r < i; --i) {
        res = res*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        res = res / i;
    }
    return res;
}

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N,0);
    vector<ll> S(N,0);
    for(ll i=0;i<N;i++){
        ll a;cin>>a;
        A[i]=a;
        S[--a]++;
    }
    ll sum=0;
    for(ll i=0;i<N;i++){
        sum+=combi(S[i],2);
    }
    for(ll i=0;i<N;i++){
        ll index=--A[i];
        cout<<sum-combi(S[index],2)+combi(S[index]-1,2)<<endl;
    }
    return 0;
}

Measured memory_bytes: 6400
import math
A,B = map(int,input().split())
A_range = [math.ceil(100*A/8),100*(A+1)//8]
B_range = [10*B,10*(B+1)]

if(min(A_range[1],B_range[1])<=max(A_range[0],B_range[0])):
    print("-1")
else:
    print(max(A_range[0],B_range[0]))

Measured memory_bytes: 3064
#include <cstdio>
int main(){
	char x[9];
	while(scanf("%s",&x)!=EOF){
		if(x[0]==x[1] && x[1]==x[2] & x[0]=='o'){
			printf("o\n");
			continue;
		}
		if(x[3]==x[4] && x[4]==x[5] & x[3]=='o'){
			printf("o\n");
			continue;
		}		
		if(x[6]==x[7] && x[7]==x[8] & x[7]=='o'){
			printf("o\n");
			continue;
		}
		if(x[0]==x[3] && x[3]==x[6] & x[0]=='o'){
			printf("o\n");
			continue;
		}
		if(x[1]==x[4] && x[4]==x[7] & x[1]=='o'){
			printf("o\n");
			continue;
		}
		if(x[2]==x[5] && x[5]==x[8] & x[2]=='o'){
			printf("o\n");
			continue;
		}
		if(x[0]==x[4] && x[4]==x[8] & x[0]=='o'){
			printf("o\n");
			continue;
		}
		if(x[2]==x[4] && x[4]==x[6] & x[2]=='o'){
			printf("o\n");
			continue;
		}
		if(x[0]==x[1] && x[1]==x[2] & x[0]=='x'){
			printf("x\n");
			continue;
		}
		if(x[3]==x[4] && x[4]==x[5] & x[3]=='x'){
			printf("x\n");
			continue;
		}		
		if(x[6]==x[7] && x[7]==x[8] & x[7]=='x'){
			printf("x\n");
			continue;
		}
		if(x[0]==x[3] && x[3]==x[6] & x[0]=='x'){
			printf("x\n");
			continue;
		}
		if(x[1]==x[4] && x[4]==x[7] & x[1]=='x'){
			printf("x\n");
			continue;
		}
		if(x[2]==x[5] && x[5]==x[8] & x[2]=='x'){
			printf("x\n");
			continue;
		}
		if(x[0]==x[4] && x[4]==x[8] & x[0]=='x'){
			printf("x\n");
			continue;
		}
		if(x[2]==x[4] && x[4]==x[6] & x[2]=='x'){
			printf("x\n");
			continue;
		}
		printf("d\n");
	}
	return 0;
}

Measured memory_bytes: 948
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	char A[10][10]={
		"A","fri","sat","sun","mon","tue","wed","thu"
		};
	int x,s;
	
	cin>>x;
	
	if(x%7==0) s=7;
	else s=x%7;
	
	cout<<A[s]<<endl;
	
	return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

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

    int ans=0;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='+')ans++;
        else ans--;
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> P;
#define PI 3.141592653589793
#define MOD 1000000007
//#define MOD 998244353
#define ALL(obj) (obj).begin(),(obj).end()
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;}
const ll INF = 1LL << 60;

//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

vector<P> prime_factorize(ll N) {
    vector<P> res;
    for (ll a=2;a*a<= N;a++) {
        if (N%a!=0) continue;
        ll ex = 0;
        while (N%a==0) {
            ex++;
            N/=a;
        }
        res.push_back(P(a,ex));
    }
    if (N!=1)res.push_back(P(N, 1));
    return res;
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
        ans%=MOD;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans=ans*modinv(i,MOD)%MOD;
    }
    return ans;
}

int main() {
    ll n,m,ans=1;
    cin >> n >> m;
    vector<P> p=prime_factorize(m);
    for (ll i=0;i<p.size();i++){
        ll x=p[i].second;
        ans*=nCr(x+n-1,n-1);
        ans%=MOD;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

ll eru[222222][2];
ll aru[222222][2];
ll ans[222222];

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

	REP(i, str.size()){
		if(str[i] == 'R'){
			aru[i][0]++;
			aru[i+1][0] += aru[i][1];
			aru[i+1][1] += aru[i][0];
			aru[i][0] = 0;
			aru[i][1] = 0;
		}
	}
	REV(i, str.size()){
		if(str[i] == 'L'){
			eru[i][0]++;
			eru[i-1][0] += eru[i][1];
			eru[i-1][1] += eru[i][0];
			eru[i][0] = 0;
			eru[i][1] = 0;
		}
	}
	REP(i, str.size()){
		ans[i] += eru[i][0];
		ans[i] += aru[i][0];
		if(eru[i][1]){
			ans[i+1] += eru[i][1];
		}
		if(aru[i][1]){
			ans[i-1] += aru[i][1];
		}
	}

	REP(i, str.size())cout << ans[i] << " ";cout << endl;
	
	return 0;
}


Measured memory_bytes: 7888
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] set = new int[n];
        for(int i=0;i<m;i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            set[a]++;
            set[b]++;
        }
        for(int i=0;i<n;i++){
            System.out.println(set[i]);
        }
    }

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


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

using namespace std;

int main()
{
    int n;
    cin >> n;
    set<int> s;
    for(int i = 0; i < n; i++) {
        int in;
        cin >> in;
        s.insert(in);
    }
    cout << s.size() << endl;

    return 0;
}

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

using namespace std;

int main(void) {
  int n, c, k;
  cin >> n >> c >> k;

  vector<int> t(n);
  for (int i = 0; i < n; i++) {
    cin >> t[i];
  }
  sort(t.begin(), t.end());

  int i = 0, st, cc, ans = 0;
  while (i < n) {
    cc = c;
    st = i;
    while (cc-- && t[i] <= t[st] + k && i < n) {
      i++;
    }
    ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> cnt(n + 1, 1);
	vector<bool> may(n + 1);
	may[1] = true;
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		--cnt[x];
		++cnt[y];
		if (may[x]) {
			may[y] = true;
			if (cnt[x] == 0) may[x] = false;
		}
	}
	printf("%d\n", accumulate(may.begin() + 1, may.end(), 0));
}


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

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

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

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

use std::cmp::{max, min};

fn main() {
    let nm: Vec<usize> = read_vec();
    let n = nm[0];
    let m = nm[1];
    let mut neighbor: Vec<Vec<(u32, bool)>> = vec![vec![(1000000000, false); n]; n];
    for _ in 0..m {
        let abc: Vec<usize> = read_vec();
        let a = abc[0] - 1;
        let b = abc[1] - 1;
        let c = abc[2] as u32;
        let u = min(a, b);
        let v = max(a, b);
        neighbor[u][v] = (c, true);
    }

    for w in 0..n {
        for u in 0..n {
            if u == w {
                continue;
            }
            for v in u + 1..n {
                if v == w {
                    continue;
                }
                let c1 = neighbor[min(u, w)][max(u, w)].0;
                let c2 = neighbor[min(w, v)][max(w, v)].0;
                let c = neighbor[u][v].0;
                if c1 + c2 < c {
                    neighbor[u][v].0 = c1 + c2;
                    neighbor[u][v].1 = false;
                }
            }
        }
    }

    let mut cnt = 0;
    for u in 0..n {
        for v in u + 1..n {
            if neighbor[u][v].1 {
                cnt += 1;
            }
        }
    }
    println!("{}", m - cnt);
}


Measured memory_bytes: 4352
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9+7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;

bool comp(const P &p1, const P &p2) {
	int c1 = p1.first + 1, c2 = p2.first + 1;
	int d1 = p1.first + p1.second + 1, d2 = p2.first + p2.second + 1;
	return (c2 - 1)*d1 < (c1 - 1)*d2;
}
vector<P>v1, v0;

ll dp[200020][50];//i番目まででj個買った時の時間のmin

void solve() {
	int N, T; cin >> N >> T;
	vector<int>A(N), B(N);

	REP(i, N) {
		cin >> A[i] >> B[i];
		if (A[i] > 0)v1.push_back({ A[i],B[i] });
		else v0.push_back({ A[i],B[i] });
	}
	//print("input");
	if(v1.size()>0)sort(v1.begin(),v1.end(), comp);
	//print("sorted");
	//exit(0);
	VSORT(v0);
	int M = v1.size();
	REP(i, M + 1) {
		REP(j, 50) {
			dp[i][j] = 1e12;
		}
	}
	dp[0][0] = 0;
	REP(i, M) {
		REP(j, 49) {
			ll t = dp[i][j];
			if (t > T)continue;
			chmin(dp[i + 1][j], dp[i][j]);
			//買う
			ll nt = (t + 1)*v1[i].first + v1[i].second + t + 1;;
			if (nt > T)continue;
			chmin(dp[i + 1][j + 1], nt);
		}
	}
	ll ans = 0;
	//print("a");
	REP(k, 50) {
		if (dp[M][k] > T)continue;
		int cnt = k;
		int rem = T - dp[M][k];
		int mm = v0.size();
		REP(i, mm) {
			if (v0[i].second + 1 <= rem) {
				cnt++;
				rem -= (v0[i].second + 1);
			}
		}
		ans = max(ans, cnt);
	}
	print(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 85740
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, N) for(int i = 0; i < N; i++)

int N, K;
vector<int> x;

int main() {
    cin >> N >> K;
    rep(i, N) {
        int a;
        scanf("%d", &a);
        x.push_back(a);
    }
    int ans = 1000000000;
    for (auto it = x.begin(); it + K - 1 < x.end(); it++)
        ans = min(ans, min(abs(*it), abs(*(it + K - 1))) + abs(*it - *(it + K - 1)));
    cout << ans << endl;
}

Measured memory_bytes: 892
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  string s, t;

  cin >> s >> t;

  int ans = 1e9 + 42;

  for(int i = 0; i <= s.size() - t.size(); i++) {
    int cur = 0;
    for(int j = 0; j < t.size(); j++)
      cur += (s[i + j] != t[j]);
    ans = min(ans, cur);
  }

  cout << ans;

  return 0;
}
/*

*/


Measured memory_bytes: 3664
#include <stdio.h>

int main(void)
{
 int N,i,K,h[100000];
 int count=0;

 scanf("%d%d",&N,&K);

 for(i=0;i<N;i++){
  scanf("%d",&h[i]);
  if(h[i]>=K)
   count++;
 }

 printf("%d\n",count);
 return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int maxn=500001;
typedef long long ll;
int main()
{
    ll a,b;
    cin>>a>>b;
    if((a+b)%2)
    puts("IMPOSSIBLE");
    else printf("%lld\n",(a+b)/2);
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  long long fibo[31]={0,1,2,4};
  for(int i=4;i<=30;i++){
    fibo[i] = fibo[i-2]+fibo[i-1]+fibo[i-3];
  }
  int n;
  while(cin >> n,n){
    cout << (fibo[n]%3650?fibo[n]/3650+1:fibo[n]/3650) << endl;
  }
}

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

int main(void) {
  int a, b, c;
  cin >> a >> b >> c;
  if(a == (b + c) || b == (a + c) || c == (a + b)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }

  return 0;
}


Measured memory_bytes: 384