akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

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

    int n, p;
    string s;
    cin >> n >> p >> s;
    ll ans=0;
    if(p==2) {
        for(int i=0; i<n; ++i)
            if((s[i]-'0')%2==0)
                ans+=i+1;
    } else if(p==5) {
        for(int i=0; i<n; ++i)
            if((s[i]-'0')%5==0)
                ans+=i+1;
    } else {
        map<int, int> mp;
        ++mp[0];
        int t=0, p2=1;
        for(int i=n-1; ~i; --i) {
            t=(t+(s[i]-'0')*p2)%p;
            ans+=mp[t];
            mp[t]++;
            p2=p2*10%p;
        }
    }
    cout << ans;
}


Measured memory_bytes: 916
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;

struct good
{
    int w,v;
}g[110];

bool cmp(good a,good b)
{
    return a.v > b.v;
}
good A[110],B[110],C[110],D[110];

LL swa[110],swb[110],swc[110],swd[110];
LL sva[110],svb[110],svc[110],svd[110];

int main(void)
{
    int n,w,i,j,k,l;
    int a,b,c,d;
    while(scanf("%d%d",&n,&w)==2)
    {
        a = b = c = d = 0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&g[i].w,&g[i].v);
            if(g[i].w == g[1].w)
                A[++a] = g[i];
            if(g[i].w == g[1].w + 1)
                B[++b] = g[i];
            if(g[i].w == g[1].w + 2)
                C[++c] = g[i];
            if(g[i].w == g[1].w + 3)
                D[++d] = g[i];
        }
        sort(A+1,A+a+1,cmp);
        sort(B+1,B+b+1,cmp);
        sort(C+1,C+c+1,cmp);
        sort(D+1,D+d+1,cmp);
        swa[0] = swb[0] = swc[0] = swd[0] = 0;
        sva[0] = svb[0] = svc[0] = svd[0] = 0;
        for(i=1;i<=a;i++)
        {
            swa[i] = swa[i-1] + A[i].w;
            sva[i] = sva[i-1] + A[i].v;
        }
        for(i=1;i<=b;i++)
        {
            swb[i] = swb[i-1] + B[i].w;
            svb[i] = svb[i-1] + B[i].v;
        }
        for(i=1;i<=c;i++)
        {
            swc[i] = swc[i-1] + C[i].w;
            svc[i] = svc[i-1] + C[i].v;
        }
        for(i=1;i<=d;i++)
        {
            swd[i] = swd[i-1] + D[i].w;
            svd[i] = svd[i-1] + D[i].v;
        }
        int sumv = 0;
        int ans = 0;
        for(i=0;i<=a;i++)
        {
            for(j=0;j<=b;j++)
            {
                for(k=0;k<=c;k++)
                {
                    for(l=0;l<=d;l++)
                    {
                        LL sum = swa[i] + swb[j] + swc[k] + swd[l];
                        if(sum <= (LL)w)
                        {
                            ans = max((LL)ans,sva[i]+svb[j]+svc[k]+svd[l]);
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


int main_B() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string S, T; cin >> S >> T;
    int SL = S.size();

    string ans = "No";
    string S2 = S + S;
    REP(i,SL) {
        string t = S2.substr(i, SL);
        if (t==T) {
            ans = "Yes";
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

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


public class Test
{	
    public static void Main()
	{
	    int[] n = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        if(n[0]%n[1] > 0) Console.WriteLine(1);
	    else Console.WriteLine(0);
	    
	} 
}

Measured memory_bytes: 13268
from sys import stdin

# 入力読み込み
n, k = stdin.readline().rstrip().split()
n = int(n)
k = int(k)
A_lst = []

for i in range(k):
  d = int(stdin.readline().rstrip())
  a_lst = [int(a) for a in stdin.readline().rstrip().split()]
  A_lst.extend(a_lst)
    
A_set = set(A_lst)
print(n - len(A_set))

Measured memory_bytes: 9124
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

Int modpow(Int a, Int n, Int mod) {
    Int ret = 1;
    while (n > 0) {
        if (n & 1) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }

    return ret;
}

vector<Int> factorials, invs;
bool is_ncr_table = false;
void calc_ncr_table(Int n, Int mod) {
    is_ncr_table = true;

    // 1! ~ n! の計算
    Int f = 1;
    factorials.push_back(f);
    for (Int i = 1; i <= n; i++) {
        f *= i;
        f %= mod;
        factorials.push_back(f);
    }

    // n!^-1 の計算
    Int inv = modpow(factorials[n], mod - 2, mod);
    // (n-1)!^-1 ~ 1!^-1 の計算
    invs.assign(n, 1);
    invs[n] = inv;
    for (Int i = n; i >= 1; i--) {
        inv *= i;
        inv %= mod;
        invs[i - 1] = inv;
    }
}

Int factorial(Int n, Int mod = 1) {
    Int ret = 1;
    if (mod == 1) {
        for (Int i = 1; i <= n; i++) {
            ret *= i;
        }

        return ret;
    } else {
        for (Int i = 1; i <= n; i++) {
            ret *= i;
            ret %= mod;
        }

        return ret;
    }
}

Int ncr(Int n, Int r, Int mod) {
    if (n < r) {
        return (Int)0;
    } else {
        if (is_ncr_table) {
            // modが素数の場合のみ
            return (factorials[n] * invs[r] % mod) * invs[n - r] % mod;
        } else {
            Int x = 1;
            for (Int i = n - r + 1; i <= n; i++) {
                x *= i;
                x %= mod;
            }
            return x * modpow(factorial(r, mod), mod - 2, mod) % mod;
        }
    }
}

int main() {
    Int n, k;
    cin >> n >> k;

    calc_ncr_table(2010, MOD);

    vector<Int> rr(k);
    for (Int i = 0; i <= k - 1; i++) {
        rr[i] = ncr(k - 1, i, MOD) % MOD;
    }

    for (Int i = 1; i <= k; i++) {
        Int ans = 0;
        Int nn = n - k + 1;
        ans += ncr(nn, i, MOD);
        ans *= rr[i - 1] % MOD;
        ans %= MOD;
        cout << ans << endl;
    }

    return 0;
}

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

using namespace std;

int main() {
  for (;;) {
    int n, m, ps[1000];
    cin >> n >> m;
    if (!n && !m) return 0;
    int r = 0;
    for (int i = 0; i < n; i++)
      cin >> ps[i];
    sort(ps, ps+n);
    for (int i = 0; i < n; i++)
      r += ps[i];
    for (int i = n % m; i < n; i += m)
      r -= ps[i];
    cout << r << endl;
  }
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    vector<ll> L(M,0);
    vector<ll> R(M,0);
    vector<ll> C(M,0);
    for(ll i=0;i<M;++i){cin>>L[i]>>R[i]>>C[i];L[i]--;R[i]--;}
    vector<vector<P>> G(N, vector<P>(0));
    for(ll i=0;i<M;++i)G[L[i]].emplace_back(P(R[i],C[i]));
    for(ll i=1;i<N;++i)G[i].emplace_back(P(i-1,0));

    //ダイクストラ法
    //vvl GにP(to,cost)って感じで隣接リストにしておく
    //計算量|E|log|V|
    //頂点数N
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<ll> d(N,INF);
    d[0]=0;
    pq.emplace(P(0,0));
    while(!pq.empty()){
        P x=pq.top();
        pq.pop();
        ll &y=x.first;
        ll &z=x.second;
        if(y>d[z])continue;
        for(auto p: G[z]){
            if(d[p.first]>d[z]+p.second){
                d[p.first]=d[z]+p.second;
                pq.emplace(P(d[p.first],p.first));
            }
        }
    }


    if(d[N-1]==INF)prt(-1)
    else prt(d[N-1])

    return 0;
}


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

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A.begin(), A.end());
	int ans = 0;
	for (int i = 0; i < K; i++) ans += A[i];
	cout << ans << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define cst(x) cout<<fixed<<setprecision(x)
#define pi 3.14159265359
#define mod 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;

Graph G;
vector<int> dp;

int dfs(int v){
    if(dp.at(v) != -1) return dp.at(v);

    int res = -1;

    for(auto nv : G.at(v)){
        chmax(res,dfs(nv));
    }

    return dp.at(v) = res+1;
}
int main(){

    int n,m; cin >> n >> m;
    G.resize(n);
    rep(i,m){
        int x,y; cin >> x >> y;
        --x;--y;
        G.at(x).push_back(y);
    }
    dp.assign(n,-1);

    rep(i,n) dfs(i);
    int ans = -1;
    rep(i,n) chmax(ans,dp.at(i));
    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
const ll MOD = 998244353;
const int INF = 1e8;
const ld PI = asin(1) * 2;

void setIO () {
    FAST_IO;
}

void setIO (string s) {
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}



int main() {
	setIO();

    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5])
        cout << "Yes";
    else
        cout << "No";

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  list<int>B;for(int i=0;i<N;i++){int b;cin>>b;B.push_back(b);}
  vector<int>ans;
  while(B.size()){
    int i=B.size();bool OK=false;
    auto itr=B.end();itr--;
    while(1){
      if(*itr==i){ans.push_back(i);B.erase(itr);OK=true;break;}
      i--;
      if(itr==B.begin())break;
      itr--;
    }
    if(OK==false){cout<<-1;return 0;}
  }
  for(int i=N-1;i>=0;i--)cout<<ans[i]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    int a, b, c, k; cin >> a >> b >> c >> k;
    while(a >= b) {
        b *= 2;
        k--;
    }
    while(b >= c) {
        c *= 2;
        k--;
    }
    if(k >= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using ll = unsigned long long int;
using namespace std;

int main() {
    fastIO;
    int n;
    cin >> n;
    vector<int> Mochi(n);
    rep(i, n) cin >> Mochi.at(i);

    sort(Mochi.begin(), Mochi.end());

    int cnt = 1;
    for (size_t i = 0; i < Mochi.size() - 1; i++) {
        if (Mochi.at(i) != Mochi.at(i + 1))
            cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#include <ctime>
#include <unordered_map>
#include <stdlib.h>
using namespace std;
#define ll  long long int
#define mod 1000000007
#define modd 998244353
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #include<boost/multiprecision/cpp_int.hpp>
// using boost ::multiprecision::cpp_int;
/*__builtin_clz();
__builtin_ctz();
__builtin_popcount();*/
int main()
{
    boost;
    ll n;
    cin>>n;
    ll a[n];
    for(ll i =0;i<n;i++)
    cin>>a[i];
    ll ans[n]={0};
    ans[0]= 0;
    ans[1] = abs(a[1]-a[0]);
    for(ll i=2;i<n;i++)
    {
        ans[i] = min(ans[i-1] + abs(a[i]-a[i-1]),ans[i-2] + abs(a[i]-a[i-2]));
    }
    cout<<ans[n-1]<<"\n";
    cerr << "\nTime elapsed: " << 1000 * clock()/CLOCKS_PER_SEC << "ms\n";
}
/* AnsHuman_7 || Anshuman Gaur */

Measured memory_bytes: 5160
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
  int n;
  long long dp[20][20];
  int mt[20][20][20][20];

  cin >> n;
  for(int k=0;k<n;k++){
    int gx,gy;
    cin >> gx >> gy;
    for(int i=0;i<=gy;i++)
      for(int j=0;j<=gx;j++)
	dp[i][j] = 0;

    for(int i=0;i<=gy;i++)
      for(int j=0;j<=gx;j++)
	for(int n=0;n<=gy;n++)
	  for(int m=0;m<=gx;m++)
	    mt[j][i][m][n] = 0;
	
    int mata;
    cin >> mata;
    for(int i=0;i<mata;i++){
      int x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      mt[x1][y1][x2][y2] = 1;
      mt[x2][y2][x1][y1] = 1;
    }
    dp[0][0] = 1;
    for(int i=0;i<=gy;i++){
      for(int j=0;j<=gx;j++){
	if(i-1<0 || mt[j][i-1][j][i] || dp[i-1][j]==0){
	  if(j-1<0 || mt[j-1][i][j][i] || dp[i][j-1]==0){
	    continue;
	  }
	  else dp[i][j] = dp[i][j-1];
	}
	else if(j-1<0 || mt[j-1][i][j][i] || dp[i][j-1]==0){
	  dp[i][j] = dp[i-1][j];
	}
	else dp[i][j] = dp[i-1][j]+dp[i][j-1];
      }
    }
    if(dp[gy][gx] == 0) printf("Miserable Hokusai!\n");
    else printf("%d\n",dp[gy][gx]);
  }
  return 0;
}

Measured memory_bytes: 1608
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
//[int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

/*--------------------template--------------------*/

struct D { int w; ld g, lb, rb; };
vector<D> v;
bool ans;
vector<set<int>> tree;

void solve(int n)
{
	int w = v[n].w; ld g = v[n].g*w;
	for (auto it = tree[n].begin(); it != tree[n].end(); it++)
	{
		int nx = *it;
		solve(nx);
		w += v[nx].w;
		g += v[nx].g*v[nx].w;
	}
	v[n].w = w; v[n].g = g / w;

	if (v[n].g <= v[n].lb || v[n].g >= v[n].rb)
		ans = false;

}

int main()
{
	int w, h;
	while (cin >> w >> h, w)
	{
		v.clear();
		tree.clear();
		vs fld(h);
		REP(i, h) cin >> fld[i];
		vector<vector<pii>> blocks;
		vector<vector<bool>> visited(h, vector<bool>(w));
		REP(i, h)REP(j, w)
		{
			if (fld[i][j] != '.'&& !visited[i][j])
			{
				vector<pii> tmp;
				char c = fld[i][j];
				queue<pii> que; visited[i][j] = true;
				que.push(pii(i, j));
				tmp.push_back(pii(i, j));
				int wei = 0; ld g = 0;
				ld lb = 10000, rb = -10000;
				while (que.size())
				{
					int tx = que.front().first, ty = que.front().second;
					que.pop();
					wei++; g += ty;

					if (tx == h - 1 ||(fld[tx + 1][ty] != c&&fld[tx + 1][ty] != '.'))
					{
						chmin(lb, (ld)ty);
						chmax(rb, (ld)ty);
					}


					REP(k, 4)
					{
						int nx = tx + dx[k], ny = ty + dy[k];
						if (valid(nx, ny, h, w) && fld[nx][ny]==c && !visited[nx][ny])
						{
							visited[nx][ny] = true;
							que.push(pii(nx, ny));
							tmp.push_back(pii(nx, ny));
						}
					}
				}
				v.push_back(D{ wei,g / wei, lb - 0.5, rb + 0.5 });
				blocks.push_back(tmp);
			}
		}
		tree.resize(v.size());
		FOR(i, 1, h)REP(j, w)
		{
			if (fld[i][j] == '.'||fld[i - 1][j] == '.') continue;
			if (fld[i][j] != fld[i - 1][j])
			{
				int t, b;
				REP(k, v.size())
				{
					if (find(ALL(blocks[k]), pii(i, j)) != blocks[k].end()) b = k;
					if (find(ALL(blocks[k]), pii(i-1, j)) != blocks[k].end()) t = k;
				}
				tree[b].insert(t);
			}
		}


		ans = true;
		solve(v.size() - 1);
		cout << (ans ? "STABLE\n" : "UNSTABLE\n");
	}
	return 0;
}

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

using namespace std;

void output(const vector<int>& v, string mark)
{
	for (int i = 0; i < v.size(); i++)
	{
		if (v.at(i) == 0)
		{
			cout << mark << " " << i + 1 << endl;
		}
	}
}

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

	vector<int> s(13);
	vector<int> h(13);
	vector<int> c(13);
	vector<int> d(13);

	for (int i = 0; i < n; i++)
	{
		char mark;
		int  number;
		cin >> mark >> number;

		if (mark == 'S')
		{
			s.at(number - 1)++;
		}
		else if (mark == 'H')
		{
			h.at(number - 1)++;
		}
		else if (mark == 'C')
		{
			c.at(number - 1)++;
		}
		else
		{
			d.at(number - 1)++;
		}
	}

	output(s, "S");
	output(h, "H");
	output(c, "C");
	output(d, "D");
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
long long dp[110][110000];//dp[i][j]:=i番目までの品物を使って、重さwを超えないように持ち帰った時の、価値の総和の最大値
int w[110000],v[110000];
int main()
{
    int N,W;
    cin >> N >> W;
    rep(i,N){
        cin >> w[i] >> v[i];

    }
    rep(i,W){
        dp[0][i] = 0;
    }
    rep(i,N){
        rep(j,W+1){
        if (j-w[i]<0){
            dp[i+1][j] = dp[i][j];
                 
        }
        else{
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);

        }
        
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}

Measured memory_bytes: 87424
from collections import deque
n, m, k =map(int, input().split())


fd = dict()
directcount = [0] * n
visited = [[-1, -1] for i in range(n)]
q = deque(list())
g = []
for _ in range(n):
    g.append(deque(list()))


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    directcount[a] += 1
    directcount[b] += 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True

colorcount = [-1] * n
# dfs
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        #print(q)
        nextnode = q.popleft() # 次の探索
        if visited[nextnode][0] != -1:
            continue
        visited[nextnode] = [color, cnt]
        q.extend(g[nextnode]) # nextnodeの辺を足す
        cnt += 1
    colorcount[color]  = cnt - 1

# グループごとの色をカウント
#for i in range(n):
#    colorcount[visited[i][0]] = max(colorcount[visited[i][0]], visited[i][1])

#print(visited)
#print(colorcount)


res = [[visited[i][0], colorcount[visited[i][0]]] for i in range(n)]
#print(res)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if res[c][0] == res[d][0]:
        res[c][1] -= 1
        res[d][1] -= 1

output = []
for i in range(n):
    output.append(res[i][1] - directcount[i] - 1)

print(" ".join(list(map(lambda x: str(x), output))))

Measured memory_bytes: 167132
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
//#define rep(i,n) for(ll i = 0 ; i<n ; ++i);
int main(){
    ll enterN=0,enterE=0;
    ll flagN=0,flagE=0,flagW=0,flagS = 0;
    string s;
    cin>>s;
    ll len = s.size();
    for(ll i = 0 ; i<len ; ++i){

    if(s[i]=='N')
        {
            flagN = 1; enterN=1;}
        else if( s[i] == 'S') {flagS = 1; enterN=1;}
        else if( s[i]== 'E') {flagE = 1 ;enterE=1;}
        else {flagW = 1 ;enterE=1;}
    }
    flagN+=flagS , flagE+=flagW;
    if((flagN<2 && enterN) || (flagE<2 && enterE) )
        cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) (v.begin(),v.end())
#define ff first
#define ss second
const ll maxn=2e5+10;
const ll mod=998244353;


int main() {
  	fast;
  	ll k,s=0;
  	cin>>k;
  	for(ll a=1;a<=k;++a)
  	{
  		for(ll b=1;b<=k;++b)
  		{
  			for(ll c=1;c<=k;++c)
  			{
  				s+=__gcd(__gcd(a,b),c);
			  }
		  }
	  }
	  cout<<s;
}

Measured memory_bytes: 3652
a,b,c = map(int,input().split())
i,j,k,l = 0,0,0,0
if a == b:
    i = 1
if b == c:
    j = 1
if c == a:
    k = 1
if a == b & b == c:
    l = -1
print(3-(i+j+k+l))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    int b[n];
    for(int i=0; i<n; i++){
        a[i] -= i;
        b[i] = a[i];
    }
    sort(b,b+n);
    long long ans = 0;
    for(int i=0; i<n; i++){
        int k = -2*i-a[i];
        ans += (upper_bound(b,b+n,k)-lower_bound(b,b+n,k));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5116
#include<stdio.h>
#include<string.h>
int main(){
  char s[10];
  gets(s);
  //printf("%s",s);
  if(strcmp(s,"Sunny")==0){
    printf("Cloudy");
  }
  else if(strcmp(s,"Cloudy")==0){
    printf("Rainy");
  }
  else printf("Sunny");
  return 0;
}

Measured memory_bytes: 128
N, A, B = map(int, input().split())

d = abs(A - B)
if d % 2 == 0:
    print(d // 2)
else:
    a = min(abs(N - A), abs(N - B))
    b = min(abs(B - 1), abs(A - 1))
    if a > b:
        print(b + 1 + d // 2)
    else:
        print(a + 1 + d // 2)


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

using namespace std;
#define int long long
#define N 666666
int arr[N],sum1[N],sum2[N];
signed main(){
	int n,k;
	cin>>n>>k;
	int ans=0;
	for(int i=1;i<=n;i++){
		scanf("%lld",&arr[i]);
		sum1[i]=sum1[i-1]+arr[i];
		if(arr[i]>0)
			sum2[i]=sum2[i-1]+arr[i];
		else 
			sum2[i]=sum2[i-1];
	}
	ans=max(ans,sum1[n]);
	for(int i=1;i<=n-k+1;i++){
		int t1=sum2[i-1];
		int t2=sum2[n]-sum2[i+k-1];
		ans=max(ans,t1+t2);
		ans=max(ans,t1+t2+sum1[i+k-1]-sum1[i-1]);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5120
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

safe = [True]*(N+1)
for i in range(M):
    safe[(a[i])] = False

# print(a)
dp = [0]*(N+2)
#print('safe', safe)
dp[0] = 1
for i in range(0, N):
    if safe[i]:
        dp[i+1] = dp[i+1]+dp[i]
        dp[i+2] = dp[i+2]+dp[i]

    if not(safe[i]):
        dp[i] = 0
#print('dp', dp)
print(dp[N] % 1000000007)


Measured memory_bytes: 468988
N = int(input())
Vs = input().split()

if N == 2:
    print(sum([int(x) for x in Vs])/N)
else:
    lists = [int(x) for x in Vs]
    while N > 1:
        lists.sort()
        x = (lists.pop(0) + lists.pop(0)) / 2
        lists.insert(0, x)
        N -= 1

    print(lists[0])

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

A = [list(map(int, input().split())) for j in range(n)]
ans = 10 ** 7
for i in range(1 << n):
    s = [0] * (m + 1)
    for j in range(n):
        if i >> j & 1:
            for k in range(m+1):
                s[k] += A[j][k]
    if min(s[1:]) >= x:
        ans = min(ans, s[0])
print(-1) if ans == 10 ** 7 else print(ans)

Measured memory_bytes: 9188
/*
 * atcoder/abc089/b.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


void solve() {
  int a, b, c;
  cin >> a >> b >> c;
  if (a <= c and c <= b) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3504
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s= input()

t = input()

if(s==t[:-1]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 68388
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define strall(v) (v).cbegin(),(v).cend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
  int n,q;
  string s;
  cin >> n >> q >> s;
  vector<int>table(n+1,0);
  vector<int> l(q),r(q);
  rep(i,q) cin >> l[i] >> r[i];
  for(int i=0;i<n;i++){
    if(i < n && s[i] == 'A' && s[i+1] == 'C') table[i+1]= table[i]+1;
    else table[i+1] = table[i];
  }
  rep(i,q){
    int L = l[i]-1;
    int R = r[i]-1;
    cout << table[R] -table[L] << endl;
  } 
  
}

Measured memory_bytes: 2176
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;
#pragma endregion
// Warshall–Floyd algorithm ワーシャルフロイド法
std::vector<std::vector<long long>> warshallFloyd(const WGraph &G) {
    int n = (int)G.size();
    std::vector<std::vector<long long>> dis(n, std::vector<long long>(n, LINF));
    for (int i=0; i<n; i++) {
        dis.at(i).at(i) = 0;
    }
    for (int i=0; i<n; i++) {
        for (auto e : G.at(i)) {
            dis.at(i).at(e.first) = e.second;
        }
    }

    for (int k=0; k<n; k++) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                dis.at(i).at(j) = std::min(dis.at(i).at(j), dis.at(i).at(k) + dis.at(k).at(j));
            }
        }
    }

    return dis;
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> a.at(i).at(j);
        }
    }

    WGraph G(n);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            G.at(i).push_back({j, a.at(i).at(j)});
            G.at(j).push_back({i, a.at(i).at(j)});
        }
    }
    auto dis = warshallFloyd(G);

    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (a.at(i).at(j) > dis.at(i).at(j)) {
                cout << -1 << '\n';
                return;
            }
        }
    }

    ll res = 0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            bool rem = false;
            for (int k=0; k<n; k++) {
                if (k == i || k == j) continue;
                if (dis.at(i).at(k) + dis.at(k).at(j) == a.at(i).at(j)) {
                    rem = true;
                    break;
                }
            }
            if (!rem) res += a.at(i).at(j);
        }
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 3840
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){
int D,N;
cin >> D  >>N;
int x=1;

    rep(i,D){
    x*=100;
    }

long long ans=0;

    rep(i,N){
        ans+=x;
        if(i==99){
            ans+=x;
        }
    }
    
    cout <<ans <<endl;

 return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <limits>
#include <iterator>
#include <cmath>
#include <numeric>
#include <stack>
#include <cassert>
#include <forward_list>
#include <chrono>
#include <deque>
#include <list>
#include <random>
#include <cstdio>
#include <sstream>

using namespace std;

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

	int digit = S.size()-1;

	unsigned long long ans = 0;
	for (int bit = 0; bit < (1<<digit); ++bit)
	{
		vector<int> a;
		for (int i = 0; i < digit; ++i)
		{
			if (bit & (1 << i))
			{
				a.push_back(i);
			}
		}

		unsigned long long m = 0;
		int l = 0;
		for (int i = 0; i < a.size(); ++i)
		{
			string s;
			if (a.size() - 1 == i)
			{
				s = S.substr(l, a[i] - l + 1);
			}
			else {
				s = S.substr(l, a[i] - l + 1);
			}
			m += stoi(s);
			l = a[i] + 1;
		}
		m += stoull(S.substr(l,(S.size() - l)));
		ans += m;
	}

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

Measured memory_bytes: 256
#include<iostream>
#include<stack>
#include<stdlib.h>
 
 
using namespace std;
 
int main(void) {
  stack<int> S;
 
  int q;
  int next;
  string s;
  while(cin >> s) {
    if(s[0]=='+') {
        q=S.top();
        S.pop();
        next=S.top();
        S.pop();
        S.push(next+q);
    }
    else if(s[0]=='-') {
        q=S.top();
        S.pop();
        next=S.top();
        S.pop();
        S.push(next-q);
    }
    else if(s[0]=='*') {
        q = S.top();
        S.pop();
        next = S.top();
        S.pop();
        S.push(next*q);
    }
    else if(s[0]=='/') {
        q= S.top();
        S.pop();
        next=S.top();
        S.pop();
        S.push(next/q);
    }
    else {
        S.push(atoi(s.c_str()));
    }
  }
  cout << S.top() << endl;
  S.pop();
  return 0;
}


Measured memory_bytes: 3160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp120 {
    class Program {
        static void Main(string[] args) {
            int N = int.Parse(Console.ReadLine());

            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();

            Array.Sort(a);

            long ans = 1000000;

            for (int i = a[0]; i <= a.Max(); i++) {
                int cand = 0;
                for (int k = 0; k < N; k++) {
                    cand += (a[k] - i) * (a[k] - i);
                }

                ans = Math.Min(ans, cand);

            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13396
A, B, C, X = map(int, open(0).read().split())
ans = 0
for a in range(A+1):
    for b in range(B + 1):
        for c in range(C + 1):
            if 500 * a + 100 * b + 50 * c == X:
                ans += 1
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define repd(i,a,b) for (ll i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;
int main(void)
{
	int N, K;
	cin >> N >> K;
	vector<int> S(N);
	rep(i,N) S.at(i) = 0;

	int A, d;
	rep(i,K)
	{
		cin >> d;
		rep(j,d)
		{
			cin >> A;
			A--;
			S[A]++;
		}
	}

	int count = 0;
	rep(i,N) if(S[i]==0) count++;
	cout << count << endl;
	
	return 0;
}


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

using LL = long long;

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); ++(i))
#define RFOR(i, a, b) for (int(i) = (a); (i) > (b); --(i))
#define SORT(x) sort(ALL((x)))
#define RSORT(x) sort(RALL((x)))
#define SZ(x) (int)(x).size()
#define debug(x) cerr << #x << " : " << x << '\n'

const int INF = 1e9;
const int MOD = 1e9 + 7;
const LL LINF = 1e18;

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

  int ans = 0;
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> A(M);
  FOR(i, 0, M) { cin >> A[i]; }

  for (int i = 0; A[i] < X; ++i) {
    ans++;
  }

  ans = min(ans, SZ(A) - ans);

  cout << ans << '\n';

  return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

int main() {
    fastio;
    int n;
    cin >> n;
    string in;
    cin >> in;

    int m = 0, x = 0;
    for (auto i : in) {
        if (i == 'I') x++, m = max(m, x);
        else x--, m = max(m, x);
    }
    cout << m;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    string N;
    cin>>N;
    int cnt = 0;
    REP(i, N.size()){
        if(N[i] == '2'){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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();
    for (int i = 1; i <= B; i++) {
      if ((A * i) % B == C) {
        System.out.println("YES");
        return;
      }
    }
    System.out.println("NO");
  }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
char s1[100005],s2[100005];
int main()
{
   cin>>s1;
   int l;
   l=strlen(s1);
   for(int i=0;i<l;i++)
   {
   	s2[i]=s1[l-i-1];
   	//cout<<s2[i]<<endl;
   	if(s2[i]=='b')
    {
 	s2[i]='d';
 	continue;
	} 
	if(s2[i]=='d')
    {
 	s2[i]='b';
 	continue;
	} 
	if(s2[i]=='q')
    {
 	s2[i]='p';
 	continue;
	} 
	if(s2[i]=='p')
    {
 	s2[i]='q';
 	continue;
	} 
   }
   //cout<<s1<<"　"<<s2; 
   int flag=0;
   for(int i=0;i<=l;i++)
   {
   	if(s2[i]!=s1[i])
   	{
   		flag=1;
   		break;
	   }
   }
   if(!flag) cout<<"Yes";
   else cout<<"No";
   return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <cmath>
using namespace std;
#define fio ios::sync_with_stdio(0),cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int N, M;
int inp[300005];
ll psum[100005];
map<int, int> mp;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1;i <= N;i++) {
		scanf("%d", inp + i);
		psum[i] = psum[i - 1] + inp[i];
		psum[i] %= M;
	}
	ll ans = 0;
	mp[0] = 1;
	for (int i = 1;i <= N;i++) {
		ans += mp[psum[i]];
		mp[psum[i]]++;
	}
	printf("%lld", ans);

}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    int ct = 0, ans = 1;
    rep(i, N - 1) {
        if (ct == 0) {
            if (A[i] < A[i + 1]) ct = 1;
            else if (A[i] > A[i + 1]) ct = 2;
        }
        else if (ct == 1) {
            if (A[i] > A[i + 1]) {
                ct = 0;
                ans++;
            }
        }
        else {
            if (A[i] < A[i + 1]) {
                ct = 0;
                ans++;
            }
        }
        // cout << ct << " " << ans << endl;
    }

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

Measured memory_bytes: 3672
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;


template<typename T>
class BIT{
    public:
        vector<T> x_list;
        ll n;

        BIT(ll n=1, T fill_value=0): n(n){
            x_list.resize(n+1);
            fill(x_list.begin(), x_list.end(), fill_value);
        }

        void add(ll idx, T v){
            for(ll x=idx; x<= n;x += (x & -x)){
                x_list[x] += v;
            }
        }

        ll get_sum(ll idx){
            T v = 0;
            for(ll x=idx;x>0;x-=(x & -x)){
                v += x_list[x];
            }
            return v;
        }
};

void Main(){
    ll N, Q, c, l, r;
    cin >> N >> Q;
    vector<ll> as(N);
    vector<vector<pll>> qs(N);
    // vector<pll> qs_org(Q);
    vector<ll> ans(Q);
    rep(i, N){
        cin >> as[i];
    }

    rep(i, Q){
        cin >> l >> r;
        -- l;
        -- r;
        qs[r].emplace_back(l, i);
        // qs_org[i] = make_pair(r, l);
    }

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

    vector<ll> color_best(N+1, -1);
    // ll now_r = qs[0].first;

    BIT<ll> bitree(N, 0);

    rep(i, N){
        // if(color_best[as[i]]<=i){
            // continue;
        // }
        if(color_best[as[i]] >= 0){
            bitree.add(color_best[as[i]]+1, -1);
        }
        bitree.add(i+1, 1);
        color_best[as[i]] = i;
        if(qs[i].size() == 0){
            continue;
        }
        ll n_sum = bitree.get_sum(i+1);
        for(auto q:qs[i]){
            ans[q.second] = n_sum - bitree.get_sum(q.first);
        }
    }
    rep(i, Q){
        cout << ans[i] <<endl;
    }

}

int main(){
    Main();
}

Measured memory_bytes: 44176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)
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; }


int main() {
	int n;
	ll h, amax = 0;
	cin >> n >> h;
	vector<ll>  b(n);
	rep(i,n){
	    ll a;
	    cin >> a >> b[i];
	    if(amax < a) amax = a;
	}
	sort(b.rbegin(), b.rend());
	int i = 0;
	ll ans = 0;
	while(i < n){
        if(b[i] < amax) break;
        h -= b[i++];
        ans++;
        if(h <= 0) break;
	}
	if(h > 0){
        ans += (h + amax - 1)/amax;
	}
	cout << ans << endl;
}


Measured memory_bytes: 1152
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<tuple>
#include<string>
using namespace std;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 105
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;

int main(){
    int n,t,a;
    cin>>n>>t>>a;
    int ans=0;
    double m=INF;
    REP(i,n){
        int h;
        cin>>h;
        if(m>abs((double)((double)t-(double)0.006*(double)h)-a)){
            m=abs((double)((double)t-(double)0.006*(double)h)-a);
            ans=i+1;
        }
    }
    OUT(ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
int n;
int a[200005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=n;i>=1;i-=2)
	{
		printf("%d ",a[i]);
	}
		for(int i=1+(n&1);i<=n;i+=2)
		{
			printf("%d ",a[i]);
		}
	return 0;
}

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

int main()
{
    // sum{L} sum{R} f(L, R)
    // == sum{L} sum{R} (# of connected components in S)
    // == sum{L} sum{R} ((# of vertex in S) - (# of edge in S))
    // == sum{L} sum{R} (# of vertex in S) - sum{L} sum{R} (# of edge in S)
    size_t N;
    cin >> N;

    size_t ans = 0;
    for (size_t i = 1; i <= N; i++)
    {
        ans += i * (N - i + 1);
    }

    for (size_t i = 0; i < N - 1; i++)
    {
        size_t u, v;
        cin >> u >> v;
        if (u > v)
        {
            swap(u, v);
        }
        ans -= u * (N - v + 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3616
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
	int ans = 0,n,a[205];
	cin >> n;
	for(int i = 1;i <= 2 * n; i++)
		cin >> a[i];
		sort(a + 1,a + 1 + 2 * n);
	for(int i = 2 * n;i >= 1;i = i - 2)
		ans += a[i - 1];
		cout << ans << endl;
		return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n>>m;
  ll a[1005],b[1005],c[1005];
  rep(i,m) {
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
  }
  ll dist[1005][1005];
  rep(i,n) rep(j,n){
    if(i==j) dist[i][j] = 0;
    else dist[i][j] = INF;
  }
  rep(i,m){
    dist[a[i]][b[i]] = MIN(dist[a[i]][b[i]],c[i]);
    dist[b[i]][a[i]] = MIN(dist[b[i]][a[i]],c[i]);
  }
  rep(k,n)rep(i,n)rep(j,n) dist[i][j] = MIN(dist[i][j],dist[i][k]+dist[k][j]);
  ll ans = m;
  rep(i,m){
    bool shortest = false;
    rep(j,n) if(dist[j][a[i]]+ c[i] == dist[j][b[i]]) shortest = true;
    if(shortest) ans--;
  }
  cout<<ans<<endl;



}

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


Measured memory_bytes: 2560