akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<a.size();zz++) cerr<<a[zz]<<" ";cerr<<endl
#define mod 1000000007ll
#define inf 9999999999999999ll

bool year(string s)
{
    ll n=0;
    n=(s[2]-'0')*10+s[3]-'0';
    if(n<=12 && n>=1)
        return true;
    return false;
}

bool month(string s)
{
    ll n=0;
    n=(s[0]-'0')*10 + s[1]-'0';
    if(n<=12 && n>=1)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(year(s) && month(s))
    {
        cout<<"AMBIGUOUS\n";
    }
    else if(year(s))
    {
        cout<<"YYMM\n";
    }
    else if(month(s))
    {
        cout<<"MMYY\n";
    }
    else
    {
        cout<<"NA\n";
    }
}


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

void main_()
{
    string S;
    cin >> S;

    int count = 0;

    string prev;
    string now;
    for (auto ch : S) {
        now.append(1, ch);
        if (now != prev) {
            count++;
            prev = move(now);
            now = "";
        }
    }

    cout << count << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


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

int main() {
 int n,x,t=0,c=1; cin>>n>>x;
  int l[n];
  for(int i=0;i<n;i++) cin>>l[i];
  
  for(int i=0;i<n;i++){
    t +=l[i];
    
    if(t<x+1) c++;
    else break;
  }
 cout<<c<<endl;    
}
  
  

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

using namespace std;


int main() {
	int N;
	cin >> N;
	vector<int>D( N );
	for( size_t i = 0; i < N; i++ ) {
		cin >> D[i];
	}
	double maxans = 1, minans = 0;
	for( size_t idx = 0; idx < 30; idx++ ) {
		double midans = ( maxans + minans ) / 2;
		set<int>prev;
		prev.insert( 1 );
		for( size_t i = 0; i < N; i++ ) {
			double minvalue = D[i] * ( 1. - midans );
			double maxvalue = D[i] * ( 1. + midans );
			set<int>next;
			for( auto one : prev ) {
				for( int j = minvalue / one + 1; j <= maxvalue / one; j++ ) {
					next.insert( j*one );
				}
			}
			prev = next;
		}
		if( prev.size() ) {
			maxans = midans;
		} else {
			minans = midans;
		}

	}
	cout << fixed << setprecision( 20 ) << minans << endl;
}

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

int main(){
	int n;
  	cin >> n;
	if(n/1000 + n/100%10 + n/10 % 10 + n%10 == 7)
    	printf("%d+%d+%d+%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 + n/100%10 + n/10 % 10 - n%10 == 7)
    	printf("%d+%d+%d-%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 + n/100%10 - n/10 % 10 + n%10 == 7)
    	printf("%d+%d-%d+%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 + n/100%10 - n/10 % 10 - n%10 == 7)
    	printf("%d+%d-%d-%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 - n/100%10 + n/10 % 10 + n%10 == 7)
    	printf("%d-%d+%d+%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 - n/100%10 + n/10 % 10 - n%10 == 7)
    	printf("%d-%d+%d-%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 - n/100%10 - n/10 % 10 + n%10 == 7)
    	printf("%d-%d-%d+%d=7\n",n/1000,n/100%10, n/10%10, n%10);
	else if(n/1000 - n/100%10 - n/10 % 10 - n%10 == 7)
    	printf("%d-%d-%d-%d=7\n",n/1000,n/100%10, n/10%10, n%10);
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <istream>

#include <map>
#include <math.h>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace asl
{
    
    template <typename numeric_type>
    class point
    {
    public:
        numeric_type x, y;

        point(numeric_type x = 0, numeric_type y = 0) : x(x), y(y) {}

        point<numeric_type> &operator-=(const point<numeric_type> &ri)
        {
            x -= ri.x;
            y -= ri.y;
            return *this;
        }

        friend point<numeric_type> operator-(const point<numeric_type> &a, const point<numeric_type> &b)
        {
            return point<numeric_type>(a) -= b;
        }

    };

    template <typename numeric_type>
    std::istream &operator>>(std::istream &is, point<numeric_type> &p)
    {
        return is >> p.x >> p.y;
    }

    template <typename numeric_type>
    numeric_type imag(point<numeric_type> a)
    {
        return a.y;
    }
 
    template <typename numeric_type>
    numeric_type cross(point<numeric_type> a, point<numeric_type> b)
    {
        return a.x * b.y - a.y * b.x;
    }

    template <typename numeric_type>
    numeric_type dot(point<numeric_type> a, point<numeric_type> b)
    {
        return a.x * b.x + a.y * b.y;
    }

#include <stdint.h>

    template <typename T>
    std::istream &operator>>(std::istream &is, std::vector<T> &vec)
    {
        for (auto &value : vec)
            is >> value;
        return is;
    }

} 

#include <experimental/optional>

#define _NEXT(i) (((i) + 1) == n ? 0 : ((i) + 1))

namespace asl
{
    template <typename numeric_type>
    using polygon = std::vector<point<numeric_type>>;

    enum PointInPolygon
    {
        OUT = 0,
        ON = 1,
        IN = 2,
    };

    template <typename numeric_type>
    PointInPolygon contains(const polygon<numeric_type> &P, const point<numeric_type> &p)
    {
        bool in = false;
        for (int i = 0, n = P.size(); i < n; ++i)
        {
            point<numeric_type> a = P[i] - p, b = P[_NEXT(i)] - p;
            if (imag(a) > imag(b))
                std::swap(a, b);

            if (imag(a) <= 0 && 0 < imag(b))
                if (cross(a, b) < 0)
                    in = !in;

            if (cross(a, b) == 0 && dot(a, b) <= 0)
                return PointInPolygon::ON;
        }
        return in ? PointInPolygon::IN : PointInPolygon::OUT;
    }

} 

#include <random>

#define endl '\n'

using namespace std;
using namespace asl;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(1);
    cout << fixed;

    int n;
    cin >> n;

    polygon<int> pol(n);
    cin >> pol;

    int q;
    cin >> q;

    while (q--)
    {
        point<int> p;
        cin >> p;

        cout << contains(pol, p) << endl;
    }

    return 0;
}





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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)
int main() {
    long long n, k, ans = 0;
    cin >> n >> k;
    vector<long long> as(k + 1);
    vector<long long> bs(k + 1);
    for (int i = 1; i <= k; i++) {
        as[i] = modpow((k / i), n);
    }
    for (int i = k; i >= 1; i--) {
        bs[i] = as[i];
        for (int j = 2; i * j <= k; j++) {
            bs[i] -= bs[i * j];
        }
    }
    for (int i = 1; i <= k; i++) {
        ans += i * bs[i];
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4776
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll cost[105][2];    //cost[][0] - represents weight 
ll dp[105][1000005];      //cost[][1] - represents val  
ll n,W,maxc;
ll fun(ll i, ll w)
{ 
    if(i==n || w>W)
     return 0;
   if(dp[i][w]!=-1)
      return dp[i][w];
   
   
   if(w+cost[i][0]>W)
     return fun(i+1,w);
    else
    {
        return dp[i][w]=max(fun(i+1,w),fun(i+1,w+cost[i][0])  + cost[i][1]);
    }
    
     
}


int main()
{
    
    memset(dp,-1,sizeof(dp));
    cin>>n>>W;
    
    for(ll i=0;i<n;i++)    
      cin>>cost[i][0]>>cost[i][1];
      
    maxc=fun(0,0); 
    
    cout<<maxc<<"\n"; 
    
    return 0;
}

Measured memory_bytes: 823888
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second
#define hell 100000000
using namespace std;

int main()
{
  IOS
  ll n,l;
  ll i,j;
  cin>>n>>l;
  ll a[n+5];
  for(i=1;i<=n;i++)
  	a[i]=l+i-1;
  sort(a+1,a+n+1);
  ll sum=0;
  for(i=1;i<=n;i++)
  	sum+=a[i];
  ll mini=1e18,ans=0;
  for(i=1;i<=n;i++)
  {
  	ll sum1=0;
  	for(j=1;j<=n;j++)
  		if(j!=i)
  			sum1+=a[j];
  	if(abs(sum-sum1)<mini)
  	{
  		mini=abs(sum-sum1);
  		ans=sum1;
  	}
  }
  cout<<ans;
  return 0; 
}

Measured memory_bytes: 256
import sys
from collections import defaultdict

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


def main():
    N = int(readline())

    dp = [defaultdict(int) for _ in range(N)]
    for c in 'ACGT':
        dp[0][c + 'XX'] = 1

    for i in range(1, N):
        for s, v in dp[i - 1].items():
            for c in 'AT':
                dp[i][c + s[:2]] = (dp[i][c + s[:2]] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + s[:2]] = (dp[i]['G' + s[:2]] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + s[:2]] = (dp[i]['C' + s[:2]] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


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

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	ll M, N;
	cin >> M >> N;
	vector<ll> P(M);
	for (int i = 0; i < M; i++) {
		cin >> P[i];
	}
	sort(P.rbegin(), P.rend());
	vector<ll> sum(M + 1);
	for (int i = 0; i < M; i++) {
		sum[i + 1] = sum[i] + P[i];
	}
	vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 1e15));
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		ll C, E;
		cin >> C >> E;
		dp[i + 1] = dp[i];
		for (int j = 0; j <= M; j++) {
			dp[i + 1][min(j + C, M)] = min(dp[i + 1][min(j + C, M)], dp[i][j] + E);
		}
	}
	ll res = 0;
	for (int i = 0; i <= M; i++) {
		res = max(res, sum[i] - dp[N][i]);
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 42220
K = int(input())
X, Y = map(int, input().split())

def golf(a, b):
  if a < 0:
    t = golf(-a, b)
    return (-t[0], t[1])
  if b < 0:
    t = golf(a, -b)
    return (t[0], -t[1])
  if a > b:
    t = golf(b, a)
    return (t[1], t[0])
  
  if a + b >= K * 2:
    return (a, b - K)
  if a + b == K:
    return (0, 0)
  r = K - (a + b) // 2
  return (-r, a + b + r - K)

if K % 2 == 0 and (X + Y) % 2 == 1:
  print(-1)
else:
  res = []
  while X or Y:
    res.append((X, Y))
    X, Y = golf(X, Y)
  print(len(res))
  for r in res[: : -1]:
    print(r[0], r[1])

Measured memory_bytes: 27876
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

static const int MAX_N = 1001;
static const ll MOD = 1e9 + 7LL;

int main()
{
    int isPrime[MAX_N];

    memset(isPrime, 0, sizeof(isPrime));

    int a, b;

    for (a = 2; a * a < MAX_N; a++) {
        if (isPrime[a] == 1) continue;
        for (b = a * a; b < MAX_N; b += a) isPrime[b] = 1;
    }

    int N;

    scanf("%d", &N);

    ll x = 1LL;

    int i, j, n;

    for (i = 2; i <= N; i++) {
        if (isPrime[i] == 0) {
            n = 1;

            for (j = i; j <= N; j *= i) n += N / j;

            x = (x * n) % MOD;
        }
    }

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

    return 0;
}


Measured memory_bytes: 128
def main():
    n, k = map(int, input().split())

    p1 = n % k
    p2 = abs(p1 - k)

    ans = min(p1, p2)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
void err() {
  cout << "NO" << endl;
  exit(0);
}
int main() {
  int h, w, n;
  cin >> h >> w >> n;
  int sx, sy;
  cin >> sx >> sy;
  sx--, sy--;
  vector<int> s = {
    sx, h - 1 - sx
  , sy, w - 1 - sy
  };
  vector<int> L = {
    0, 0
  , 0, 0
  };
  vector<int> R = {
    h, h
  , w, w
  };
  vector<vector<int>> a(4, vector<int>(n));
  vector<vector<int>> b(4, vector<int>(n));
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    switch (c) {
    case 'D':
      a[0][i]++;
      break;
    case 'U':
      a[1][i]++;
      break;
    case 'R':
      a[2][i]++;
      break;
    case 'L':
      a[3][i]++;
      break;
    default:
      assert(false);
    }
  }
  for (int i = 0; i < n; i++) {
    char c;
    cin >> c;
    switch (c) {
    case 'U':
      b[0][i]++;
      break;
    case 'D':
      b[1][i]++;
      break;
    case 'L':
      b[2][i]++;
      break;
    case 'R':
      b[3][i]++;
      break;
    default:
      assert(false);
    }
  }
  for (int k = 0; k < 4; k++) {
    int l = s[k];
    int r = s[k] + 1;
    for (int i = 0; i < n; i++) {
      if (a[k][i]) {
        l++;
        r++;
      }
      if (l < 0) l = 0;
      if (R[k] < r) r = R[k];
      if (r == l) err();
      if (b[k][i]){
        l--;
      }
      if (l < 0) l = 0;
      if (R[k] < r) r = R[k];
      if (r == l) err();
    }
    cout << endl;
  }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 7280
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL
int n;
vector<ll> a;
vector<ll> asum;

int main()
{
  ll ans;

  cin >> n;

  a.resize(n); asum.resize(n);
  for (int i=0; i<n; i++) {
    cin >> a[i];
  }
  ans=0;
  asum[n-1] = a[n-1];
//printf("asum[%d] = %lld\n", n-1, asum[n-1]);
  for (int i=n-2; i>0; i--) {
    asum[i] = a[i] + asum[i+1];
    asum[i] %= MOD;
//printf("asum[%d] = %lld\n", i, asum[i]);
  }
  for (int i=0; i<n-1; i++) {
//printf("a[%d](%lld) * asum[%d](%lld)\n", i, a[i], i+1, asum[i+1]);
    ans += a[i]*asum[i+1];
    ans %= MOD;
  }

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


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

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; ++i)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; --i)

template <typename Tp> void in(Tp &x) {
	char ch = getchar(), f = 1; x = 0;
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') f = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}
template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}

int n, m;

int main()
{
	in(n); in(m);
	if (n > m) std::swap(n, m);
	if (n == 1 && m == 1) puts("1");
	else if (n == 1) {
		printf("%d\n", m - 2);
	}
	else {
		printf("%lld\n", 1ll * (n - 2) * (m - 2));
	}
	return 0;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    string s[2];
    cin >> s[0] >> s[1];
    if(n == 1){
        cout << 3 << endl;
        return 0;
    }
    if(n == 2){
        cout << 6 << endl;
        return 0;
    }
    LL ans = 0;
    if(s[0][0] == s[1][0]){
        ans = 3;
    }else{
        ans = 6;
    }
    inc(i, 1, n){
        if(s[0][i] == s[0][i-1]){
        }else{
            if(s[0][i] == s[1][i]){
                if(s[0][i-1] == s[1][i-1]){
                    MODP(ans, 2LL);
                }else{
                }
            }else{
                if(s[0][i-1] == s[1][i-1]){
                    MODP(ans, 2LL);
                }else{
                    MODP(ans, 3LL);
                }
            }
        }
        //cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

char S[1010][40];
char B[1010][1010];
char hoge[1010];


int main(){

    for(ll N, M, Q; cin >> N >> M >> Q, N;){
		rep(i, Q){
			rep(j, N)cin >> S[i][j];
			rep(j, M)cin >> B[i][j];
		}
		rep(i, M){
			rep(j, Q){
				if(j == 0)hoge[j] = B[j][i];
				else if(B[j][i] != B[j - 1][i])hoge[j] = '1';
				else hoge[j] = '0';
			}
			ll cnt = 0;
			ll tmp = 0;
			rep(j, N){
				ll f = 1;
				rep(k, Q)if(S[k][j] != hoge[k])f = 0;
				if(f){
					cnt++;
					tmp = j;
				}
			}
			if(cnt == 1){
				if(tmp < 10)cout << tmp;
				else cout << (char)('A' + tmp - 10);
			}
			else cout << "?";
		}
		cout << endl;
	}

    return 0;
}


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

const ll INF  = 1e11;

int main(){
  int N;
  cin >> N;
  ll A[N];
  rep(i,N) cin >> A[i];

  ll dp[N+2];
  rep(i,N+2) dp[i] = -1;

  rep(i,N){
    int l = -1, r = N;
    while(l+1 < r){
      int mid = (l+r)/2;
      if(dp[mid] < A[i]) r = mid;
      else  l = mid;
    }
    if(dp[l] == A[i]) dp[r] = A[i];
    else dp[r] = A[i];
  }

  int ans = 0;
  rep(i,N+2) {
    if(dp[i] != -1) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  int a, b, t;
  scan(a, b, t);
  print(t / a * b);
  return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() ll int t;cin>>t;while(t--)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {

fast();
ll x;
cin>>x;
ll a=x/11;
a*=2;
ll b=x%11;
if(b>0)
{
if(b<=6)
{
     a++;
}
else
{
  a+=2;
}
}
cout<<a<<endl;
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << '\n';
typedef int64_t Int;
Int mod = 1e9+7;
Int INF = 1e9+18;

int main() {
    ios::sync_with_stdio(false);
    Int H, W;
    cin >> H >> W;
    Int h, w;
    cin >> h >> w;
    dump((H - h) * (W - w));
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
// ascending order
#define asort(array, N) sort(array, array + N)
// descending order
#define asort_r(array, N) sort(array, array + N, greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

ll N;
vector<ll> d;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 0; i < N; i++) {
		ll a;
		cin >> a;
		d.push_back(a);
	}
	vsort(d);
	int i = 0;
	int ans = 0;
	while(i < d.size()) {
		int tmp = d[i];
		int j = i;
		int count = 0;
		while(true) {
			if(tmp == d[j]) {
				count++;
				j++;
				continue;
			} 
			break;
		}
		i = j;
		if(count % 2 != 0) ans++;
	}
	cout << ans << endl;
}


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

using namespace std;

int main(){
    int n;
    cin>>n;
    
    for(int i =1; i<= n;i++){
        int x = i;
        if(x % 3 ==0){
            cout<<" "<<i;
            
        }
        else{
            while(x){
                if(x % 10 == 3){
                    cout << " "<< i;
                    
                    break;
                }
                x/=10;
            }
        }
    }
    cout<<endl;
    
    return 0;
}


Measured memory_bytes: 3100
#include<iostream>
using namespace std;
int main()
{
  int n,t,y,a,b,c;
  cin >> n >> y;
  y/=1000;
  a=y/10;
  b=(y-a*10)/5;
  c=y-a*10-b*5;
  t=n-a-b-c;
  if(t<0){
    cout << "-1 -1 -1" << endl;
    return 0;
  }
  while(t>0){
    if(t>=4&&b>0){
      c+=5;
      b--;
      t-=4;
    }else if(a>0){
      b+=2;
      a--;
      t--;
    }else{
      cout << "-1 -1 -1" << endl;
      return 0;
    }
  }
  cout << a << " " << b << " " << c << endl;
  return 0;
}

Measured memory_bytes: 256
N, x = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in range(1, N):
	s = a[i-1] + a[i]
	ov = s - x
	if ov > 0:
		cnt += ov
		if a[i] < ov:
			a[i] = 0
		else:
			a[i] -= ov
print(cnt)

Measured memory_bytes: 14132
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n,m = mp()
x = ip()
h = {}
graph = {}
for i in range(1,n+1):
    graph[i] = []
    h[i] = x[i-1]
for i in range(m):
    a,b = mp()
    graph[a].append(b)
    graph[b].append(a)
ctr = 0
for i in graph:
    graph[i] = list(set(graph[i]))
    t = [h[j] for j in graph[i]]
    if t == []:
        ctr += 1
        continue
    if h[i] > max(t):
        ctr += 1
print(ctr)
    

Measured memory_bytes: 112624
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


N = int(input())

def solve(N):
    if N % 2 == 1:
        return 0
    else:
        num_10 = N // 10

        k = 50
        num_5 = 0
        while k < 1e19:
            num_5 += N // k
            k *= 5

        return num_10 + num_5

# def brute(N):
#     s = 1
#     for n in range(N, 0, -2):
#         s *= n
    
#     st = reversed(str(s))
#     ans = 0
#     for ch in st:
#         if ch == '0':
#             ans += 1
#         else:
#             break
#     return ans

# for i in range(2, 252, 2):
#     print(i, brute(i))

# for i in range(1, 1000000):
#     ans = solve(i)
#     gt = brute(i)
#     if ans != gt:
#         print(i, ans, gt)
#         break

print(solve(N))    




Measured memory_bytes: 8616
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>

#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF (1<<30)
#define ALEN(ARR) (sizeof(ARR) / sizeof((ARR)[0]))
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back

#if DEBUG
#define _DEBUG(x) cout<<#x<<": "<<x<<endl
#define _DDEBUG(x,y) cout<<#x<<": "<<x<<", "<<#y<<": "<<y<<endl
#else
#define _DEBUG(x) ;
#define _DDEBUG(x,y) ;
#endif

#define ll long long
#define ull unsigned long long
#define MOD 1000000007

/** FOR VECTOR DEBUG */
template <typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    if ( !v.empty() ) {
        out << '[';
        copy (v.begin(), v.end(), ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


/* template end */
int dp[200010][5];

int min_num(int a[], int l) {
    int r = INF;
    for(int i = 0; i <= l; i++) {
        r = min(r, a[i]);
    }
    return r;
}

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

    int n;
    cin >> n;
    vector<int> v(n);
    REP(i, n) {
        cin >> v[i];
    }

    for(int i = 0; i < n + 1; i++) {
        for(int j = 0; j < 5; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 5; j++) {
            int add_cost = [&] {
                if(j == 0 || j == 4) {
                    return v[i];
                }
                if(j == 1 || j == 3) {
                    return v[i] == 0 ? 2 : v[i] % 2;
                }
                return v[i] == 0 ? 1 : (v[i] % 2 == 0);
            }();
            dp[i + 1][j] = min(dp[i + 1][j], min_num(dp[i], j) + add_cost);
        }
    }

    int ans = INF;
    REP(i, 5) {
        ans = min(ans, dp[n][i]);
    }

#if DEBUG
    cout << "** RESULT **" << endl; // debug
#endif
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
// Date: 2020-04-03

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define IO freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout)
#define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define D(x) cout << #x << " = " << x << endl;
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)x.size())
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

#define mid ((l + r) >> 1)
#define lc (rt << 1)
#define rc (rt << 1 | 1)
#define lson lc, l, mid
#define rson rc, mid+1, r

int n, m;
LL add[N<<2], val[N<<2];

void pd(int rt) {
    if(add[rt]) {
        add[lc] += add[rt], val[lc] += add[rt];
        add[rc] += add[rt], val[rc] += add[rt];
        add[rt] = 0;
    }
}

void update(int rt, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        add[rt] += v;
        val[rt] += v;
        return;
    }
    pd(rt);
    if(ql <= mid) update(lson, ql, qr, v);
    if(qr > mid) update(rson, ql, qr, v);
}

LL ask(int rt, int l, int r, int x) {
    if(l == r) return val[rt];
    pd(rt);
    if(x <= mid) return ask(lson, x);
    else return ask(rson, x);
}

int a[N], cnt[N];

LL cal(int x) {
    return -ask(1, 1, 2*m-1, x) + 1LL*cnt[x]*x;
}

int main() {
    FIO;
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    LL ans = 0;
    rep(i, 1, n-1) {
        int l = a[i], r = a[i+1];
        if(l > r) r += m;
        ans += r-l;
        if(l+1 < r) {
            update(1, 1, 2*m-1, l+2, r, l+1);
            cnt[l+2]++, cnt[r+1]--;
        }
    }
    rep(i, 1, 2*m) cnt[i] += cnt[i-1];
    LL mx = 0;
    rep(i, 1, m) {
        LL val = cal(i);
        if(i < m) val += cal(i+m);
        chkmax(mx, val);
    }
    ans -= mx;
    cout << ans;


    return 0;
}

Measured memory_bytes: 12160
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int main()
{
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    a--;b--;c--;d--;
    string s;
    cin>>s;
    if(s.substr(a,max(c,d)-a+1).find("##")!=string::npos)cout<<"No"<<endl;
    else if(s.substr(b-1,min(c,d)-b+1+1+1).find("...")!=string::npos)cout<<"Yes"<<endl;
    else if(c>d)cout<<"No"<<endl;
    else if(c<d)cout<<"Yes"<<endl;
}

Measured memory_bytes: 772
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
	int n;
	scanf("%d",&n);
	if(n%10==7){
		printf("Yes");
		return 0;
	} 
	else if((n/10)%10==7){
		printf("Yes");
		return 0;
	}
	else if(n/100==7){
		printf("Yes");
		return 0;
	}
	printf("No");
}


Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, K;
string S;
int T[MAX_N];

vector<pi> vec;

void solve() {
	cin >> N >> K;
	cin >> S;
	if(S[0] == '0') vec.pb(pi(1, 0));
	rep(i, 0, N) {
		if(i == 0 || vec.back().fst != (S[i] == '1')) vec.pb(pi((S[i] == '1'), 1));
		else vec.back().sec++;
	}
	if(vec.back().fst == 0) vec.pb(pi(1, 0));
	rep(i, 0, sz(vec)) {
		T[i + 1] = T[i] + vec[i].sec;
	}
	// debug(vec, vi(T, T + sz(vec)));
	if(sz(vec) <= 2 * K + 1) cout << N << "\n";
	else {
		int res = 0;
		for(int i = 0; i + 2 * K + 1 <= sz(vec); i += 2) {
			MAX(res, T[i + 2 * K + 1] - T[i]);
		}
		cout << res << "\n";
	}
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 1732
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

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

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

	string ans = "No";
	rep(i, N + 1)rep(j, M + 1) {
		if (i*j + (N - i)*(M - j) == K) { ans = "Yes"; }
	}
	cout << ans;
	system("PAUSE");
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

struct Query {
  int l,r,i;
  int ans;
  Query(int _l,int _r,int _i):
    l(_l),r(_r),i(_i) {};
};

class BIT {
public:
  int N;
  vi arr;
  BIT(int n) {
    N = n;
    arr = vi(N+1,0);
  }
  int sum(int x) {
    int s = 0;
    for(int i = x+1;i > 0;i -=i&(-i)) {
      s += arr[i];
    }
    return s;
  }
  void add(int x,int k) {
    for(int i = x+1;i <= N;i +=i&(-i)) {
      arr[i] += k;
    }
  }
  int get(int l,int r) {
    return sum(r)-sum(l-1);
  }
};

int main() {
  int N,q;
  cin >> N >> q;
  vvi pos(N);
  vi A(N);
  rep(i,N) {
    cin >> A[i];
    A[i]--;
    pos[A[i]].push_back(i);
  }
  vector<Query> query;
  rep(i,q) {
    int l,r;
    cin >> l >> r;
    l--;r--;
    query.emplace_back(l,r,i);
  }
  sort(rng(query),[](Query l,Query r) {
    return l.l<r.l;
  });
  // 各色において、範囲内のうちもっとも左側にある頂点
  BIT imp(N);
  vi isimp(N,0);
  int nl=query[0].l;
  {
    int nr=query[0].r;
    srep(k,nl,N) {
      int c = A[k];
      int p = lower_bound(rng(pos[c]),k)-pos[c].begin();
      if(p==0) {
        imp.add(k,1);
        isimp[k]++;
      }
    }
    query[0].ans = imp.get(nl,nr);
  }
  srep(i,1,q) {
    int l=query[i].l;
    int r=query[i].r;
    srep(k,nl,l) {
      if(!isimp[k]) continue;
      int c = A[k];
      int p = lower_bound(rng(pos[c]),k)-pos[c].begin();
      if(p==sz(pos[c])-1) continue;
      p++;
      isimp[pos[c][p]]++;
      imp.add(pos[c][p],1);
    }
    query[i].ans=imp.get(l,r);
    nl=l;
  }
  sort(rng(query),[&](Query l,Query r) {
    return l.i<r.i;
  });
  for(Query qu:query) {
    cout << qu.ans << endl;
  }
  return 0;
}

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

int timer[200001];

int main() {

    int n,t;

    cin >> n >> t;

    long long int ans = 0;

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

    for(int i=0; i<n-1; i++){

        ans += min(timer[i+1] - timer[i],t);

    }

    ans += t;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;


pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let n = read::<i32>();
  let mut ans: f64 = 0.0;

  for _ in 0..n {
    let value = read::<f64>();
    let unit = read::<String>();

    if unit == "BTC" {
      ans += value * 380000.0;
    } else {
      ans += value;
    }
  }

  println!("{}", ans);
}



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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, i, j;
    cin >> n;
    vi cnt(n+1, 1);
    cnt[1] = 1;
    ll ans = 1;
    for(i=2;i<=n;i++){
        cnt[i]++;
        ans += cnt[i]*ll(i);
        for(j = 2*i ; j<=n; j+=i) cnt[j]++;
    }
    cout << ans <<"\n";

    return 0;
}

Measured memory_bytes: 42212
n = int(input())
A = list(map(int, input().split()))
# a, b, c = map(int, input().split())
evens = []
judge = True
for a in A:
    if a % 2 == 0:
        evens.append(a)
for even in evens:
    if even % 3 != 0 and even % 5 != 0:
        judge = False
print("APPROVED") if judge else print("DENIED")


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

#define Fast           ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO             freopen("in.txt", "r", stdin)
#define FC             freopen("out.txt", "w", stdout)
#define aise           cout<<"aise"<<endl
#define pb             push_back
#define pf             push_front
#define ppb            pop_back
#define ppf            pop_front
#define mp             make_pair
#define ll             long long
#define all(x)         x.begin(), x.end()
#define mset(v, a)     memset(v, a, sizeof(v))
#define pll            pair< ll, ll >
#define pd             pair< double, double >
#define ff             first
#define ss             second
#define pi             acos(-1.0)
#define mxN            2010
#define inf            1e14
#define mod            1000000007

//NCR iterative
/*voidcomb_table(intN)
{
    for(inti=0; i<=N; ++i)
    {
        for(intj=0; j<=i; ++j)
        {
            if(j==0or j==i)
            {
                C[i][j]=1LL;
            }
            else
            {
                C[i][j]=(C[i-1][j-1]+C[i-1][j]);
            }
        }
    }
}*/


//NCR recursive
/*ll dp[55][55];

ll NCR(ll n,ll r)
{

    if(n==r)
        return dp[n][r]=1;
    if(r==0)
        return dp[n][r]= 1;
    if(r==1)
        return dp[n][r]=n ;
    if(dp[n][r] != -1)
        return dp[n][r];
    return dp[n][r] = NCR(n-1,r)+NCR(n-1,r-1);
}*/

//Sieve:
/*bool Flag[1000010];
vector<ll> Prime;

void sieve()
{

    ll val=sqrt(1000010);
    for(ll i=4;i<=1000005; i+=2) Flag[i]=1;
    for(ll i=3;i <= val;i+=2)
    {

        if(Flag[i]==0)
        {

            for(ll j=i*i;j<=1000005;j+=i) Flag[j]=1;
        }
    }
    Flag[1]=1;
    for(ll i=1;i<=1000000;i++)
        if(Flag[i]==0) Prime.pb(i);
}*/


//Conversion
/*string bin(ll x)
{

    string ret;
    while(x)
    {

        ll t=x%2;
        char c;
        if(t==1)
            c='1';
        else
            c='0';
        ret.pb(c);
        x/=2;
    }
    reverse(all(ret));
    return ret;
}*/

/*ll lcm(ll x, ll y)
{

    ll ret=__gcd(x,y);
    return (x*y)/ret;
}*/

/*ll dx[]= {0,0,1,-1};
ll dy[]= {1,-1,0,0};*/

int main()
{

    ll n,m;
    cin >> n >> m;
    char a[n][m];
    for(ll i=0;i<n;i++)
    {

        for(ll j=0;j<m;j++) scanf(" %c",&a[i][j]);
    }
    for(ll i=0;i<n;i++)
    {

        for(ll t=0;t<2;t++)
        {

            for(ll j=0;j<m;j++) cout << a[i][j];
            cout << endl;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    
    ll l, r, d; cin >> l >> r >> d;
    print(r / d - (l - 1) / d)
    
    return 0;
}

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

#define rep(i,c) for(int i = 0; i < (int)c; ++i)
using llint = long long int ;
using namespace std;


int main(){
    int x;
    cin>>x;
    int ans=x;
    while(1){
        bool check=true;
        for (int i = 2; i <= ans/2; i++)
        {
            if (ans%i==0)
            {
                check=false;
                break;
            }
            
        }
        if (check==true)
        {
            cout<<ans<<endl;
            break;
        }
        ++ans;
    }
    return 0;
}

Measured memory_bytes: 256
A = list(input())
B = list(input())
C = list(input())

A.append("#")
B.append("#")
C.append("#")
game = {
  "A" : A,
  "B" : B,
  "C" : C
}
turn = "A"
finished = False

while not finished:
  next_turn = game[turn].pop(0)
  if next_turn == "#":
    print(turn)
    finished = True
  else:
    turn = next_turn.upper()


Measured memory_bytes: 9060
#include <stdio.h>

using namespace std;


int main(int argc, const char * argv[]) {
    // insert code here...
    int m, f, r;
    char grade;
    while(true){
        scanf("%d %d %d", &m, &f, &r);
        if(m == -1 && f == -1 && r == -1) break;
        if(m == -1 || f == -1){
            grade = 'F';
        }else if(m+f >= 80){
            grade = 'A';
        }else if(m+f >= 65){
            grade = 'B';
        }else if(m+f >= 50){
            grade = 'C';
        }else if(m+f >= 30){
            grade = (r >= 50)? 'C':'D';
        }else{
            grade = 'F';
        }
        printf("%c\n",grade);
    }
    return 0;
}


Measured memory_bytes: 2684