akhauriyash/Code-Regression huggingface dataset:
typedef long long ll;
/*
id: sadykhzadeh -> Azer_Sadykhzadeh
Programming Language: C++
*/
#define qq2(x,y) cout << (#x) << " = " << (x) << '\t' << (#y) << " = " << (y) << endl
#define qq(x) cout << (#x) << " = " << (x) << endl
#define elif else if
#define pb push_back
#define ins insert
#define pow2(x) ((x)*(x))
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define rus_lang setlocale(LC_ALL , "Russian")
#define F_READ ios_base::sync_with_stdio(false);cin.tie(0)
#define MOD 1000000007
#define COUT(x) return cout << x << endl, 0;
#define stop return 0
using namespace std;

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#define endl "\n"

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

string s;

int main(){
    ll n;
    vector <ll> a;
    cin >> n;
    a.resize(n); ll cnt = 0;
    for(ll i = 0; i < n; i++) cin >> a[i];
    for(ll i = 1; i < n - 1; i++) if(
                                     (a[i] > a[i-1] && a[i+1] > a[i])
                                     ||
                                     a[i] < a[i-1] && a[i+1] < a[i]
                                     ) cnt++;
    return cout << cnt << endl, 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b % mod; if (a >= mod) a -= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12); // debuged
    int T;
    T = 1;
    while (T--) solve();
}

void solve() {
    int x;
    cin >> x;
    x -= 400;
    cout << 8 - x / 200 << endl;
}


Measured memory_bytes: 3648
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    return n,a

def main(n,a):
    maxa=10**6
    isprime=[True]*(maxa+1)
    sa=sorted(a)

    prevx=0
    for x in sa:
        if isprime[x]==False:
            continue
        if prevx==x:
            isprime[x]=False
            continue

        i=x*2
        while(i<=maxa):
            isprime[i]=False
            i+=x
        prevx=x
    
    count=0
    for x in sa:
        if isprime[x]==True:
            count+=1
    return count

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)


Measured memory_bytes: 32240
#include<stdio.h>
int a,b;
char c;
int dx[4]={ 0, 0, 1, -1 };
int dy[4]={ 1, -1, 0, 0 };
char field[101][101];
void dfs(int x,int y)
{
	field[x][y]='!';
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx&&nx < a && 0 <= ny&&ny < b&&field[nx][ny] ==c)dfs(nx, ny);
	}
}
int main()
{
	int res;
	while(scanf("%d %d",&a,&b)!=EOF&&(a+b)!=0)
	{
		while (getchar()!= '\n')continue;
		for(int i=0;i<a;i++)
		{
			scanf("%s",&field[i]);
		}
			res=0;
			for(int i=0;i<a;i++)
			{
				for(int j=0;j<b;j++)
				{
					if(field[i][j]!='!')
					{c=field[i][j];
					res++;
					dfs(i,j);
					}
				}
			}
			printf("%d\n",res);	
	}
	return 0;
}



Measured memory_bytes: 3080
#coding: utf-8
n = int(input())
pillers = list(map(int,input().split()))
answer = 0
count = 0

for j in range(len(pillers)-1):
	# print('strj'+str(j))
	if pillers[j] >= pillers[j+1]:
		count += 1
		# print(count)
	else:
		if answer < count:
			answer = count
		count = 0
if answer < count:
	answer = count

print(answer) 


Measured memory_bytes: 14224
# -*- coding: utf-8 -*-

from scipy.sparse.csgraph import dijkstra

H, W = map(int, input().split())
C = [None] * 10
for i in range(10):
    C[i] = list(map(int, input().split()))
field = [None] * H
for i in range(H):
    field[i] = list(map(int, input().split()))

# ちょうどデータの持ち方が隣接行列なので、そのままscipyのダイクストラ使ってみる
dist = dijkstra(C)

ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j] != -1:
            # 該当マスの数字から1への距離を足していくだけ
            ans += dist[field[i][j]][1]
print(int(ans))


Measured memory_bytes: 17452
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
const int N=100;

int n;
int ga[N][N],gb[N][N];
int col[N],d[N];

vector<int> glim[N];
void add_lim(int x,int y){
    //printf("add_lim(%d,%d)\n",x,y);
    glim[x].pb(y);
    d[y]++;
}

void dfs(int u,int p){
    col[u]=1;//不动的点
    FOR(v,1,n)if(ga[u][v]&&gb[u][v]&&v!=p)dfs(v,u);
}
void dfsa(int u,int p){
    FOR(v,1,n)if(ga[u][v]&&v!=p){
        dfsa(v,u);
        if(!col[u]&&!col[v]){
            add_lim(v,u);
        }
    }
}
void dfsb(int u,int p){
    FOR(v,1,n)if(gb[u][v]&&v!=p){
        dfsb(v,u);
        if(!col[u]&&!col[v]){
            add_lim(u,v);
        }
    }
}
int vis[N],tim;
bool dfs_lim(int u){
    if(vis[u]==tim){
        //printf("u=%d\n",u);
        return 1;
    }
    vis[u]=tim;
    for(int v:glim[u])if(dfs_lim(v))return 1;
    return 0;
}
int get_ans(int r){
    //printf("get_ans(%d)\n",r);
    memset(col,0,sizeof(col));
    dfs(r,0);
    int res=0;
    FOR(i,1,n)res+=!col[i];
    FOR(i,1,n)glim[i].clear();
    memset(d,0,sizeof(d));
    dfsa(r,0);
    dfsb(r,0);
    queue<int> q;
    FOR(i,1,n)if(d[i]==0)q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:glim[u]){
            d[v]--;
            if(d[v]==0)q.push(v);
        }
    }
    FOR(i,1,n)if(d[i])return -1;
    return res;
}
void go(){
    scanf("%d",&n);
    memset(ga,0,sizeof(ga));
    memset(gb,0,sizeof(gb));
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); ga[a][b]=ga[b][a]=1; }
    FOR(i,1,n-1){ int a,b; scanf("%d%d",&a,&b); gb[a][b]=gb[b][a]=1; }
    int ans=0x3f3f3f3f;
    FOR(i,1,n){
        int t=get_ans(i);
        if(t!=-1)ans=min(ans,t);
    }
    FOR(i,1,n){
        int dg=0,p=0;
        FOR(j,1,n)if(ga[i][j])p=j,++dg;
        if(dg>1)continue;
        ga[i][p]=ga[p][i]=0;
        FOR(j,1,n){
            if(i==j)continue;
            ga[i][j]=ga[j][i]=1;
            int t=get_ans(i);
            if(t!=-1)ans=min(ans,t+1);
            ga[i][j]=ga[j][i]=0;
        }
        ga[i][p]=ga[p][i]=1;
    }
    printf("%d\n",ans==0x3f3f3f3f?-1:ans);
}
int main(){
    int t;
    scanf("%d",&t);
    FOR(i,1,t)go();
    return 0;
}


Measured memory_bytes: 512
import java.util.*;

class Main {

    static int [][] paper;

    static void pour (int x, int y, int size) {
        paper[x][y] += 1;
        if (x > 0)  paper[x-1][y] += 1;
        if (x < 9)  paper[x+1][y] += 1;
        if (y > 0)  paper[x][y-1] += 1;
        if (y < 9)  paper[x][y+1] += 1;

        if (size >= 2) {
            if (x > 0 && y > 0) paper[x-1][y-1] += 1;
            if (x > 0 && y < 9) paper[x-1][y+1] += 1;
            if (x < 9 && y > 0) paper[x+1][y-1] += 1;
            if (x < 9 && y < 9) paper[x+1][y+1] += 1;
        }

        if (size == 3) {
            if (x > 1)  paper[x-2][y] += 1;
            if (x < 8)  paper[x+2][y] += 1;
            if (y > 1)  paper[x][y-2] += 1;
            if (y < 8)  paper[x][y+2] += 1;
        }
    }

    static void calculate () {
        int max = 0;
        int empty = 0;

        for(int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (paper[i][j] == 0) {
                    empty += 1;
                } else if (paper[i][j] > max) {
                    max = paper[i][j];
                }
            }
        }

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

    public static void main (String [] args) {

        paper = new int[10][10];

        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()) {
            String [] line = sc.nextLine().split(",");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int size = Integer.parseInt(line[2]);

            pour(x, y, size);
        }

        calculate();

    }
}

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

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define M 998244353

#define ll long long
#define ld long double
#define vi vector<ll>
#define pi pair<ll, ll>
#define vii vector<pi>
#define vvi vector<vi>
#define pb push_back

#define REP(i, s, e) for (ll i = s; i < e; i++)
#define RREP(i, s, e) for (ll i = s; i > e; i--)

#define all(v) v.begin(), v.end()
#define part(v, s, e) v.begin() + s, v.begin() + e
#define print(v) for (auto i: v) cout << i << " ";

vi root, rnk;

ll find_set(ll a) {
    if (a == root[a])
        return a;
    return root[a] = find_set(root[a]);
}

void unite(ll a, ll b) {
    ll x = find_set(a);
    ll y = find_set(b);
    if (x != y) {
        if (rnk[x] < rnk[y])
            swap(x, y);
        root[y] = x;
        if (x == y)
            rnk[x]++;
    }
}

int main() {
    fast;
    ll n, m, x, y, z;
    cin >> n >> m;
    root.resize(n+1);
    iota(all(root), 0);
    rnk.resize(n+1, 1);
    REP(i, 0, m) {
        cin >> x >> y >> z;
        unite(x, y);
    }
    set<ll> ans;
    REP(i, 1, n+1)
        ans.insert(find_set(i));
    cout << ans.size() << endl;
    return 0;
}


Measured memory_bytes: 6528
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std; 

const int MAX_N = 5e5 + 5; 
char a[MAX_N]; 
int N, pre[MAX_N], nxt[MAX_N]; 
bool check(int pos) { 
	bool f1 = (!pre[pos]) || (pos % (pos - pre[pos])); 
	bool f2 = (nxt[pos + 1] == N + 1) || (N - pos) % (N - pos - (N - nxt[pos + 1] + 1)); 
	if (f1 && f2) return 1; 
	else return 0; 
} 
int main () { 
	scanf("%s", a + 1); 
	N = strlen(a + 1);
	pre[1] = 0; 
	for (int i = 2, j = 0; i <= N; i++) { 
		while (j && a[j + 1] != a[i]) j = pre[j]; 
		if (a[j + 1] == a[i]) ++j; 
		pre[i] = j; 
	} 
	nxt[N] = N + 1; 
	for (int i = N - 1, j = N + 1; i; i--) { 
		while (j <= N && a[j - 1] != a[i]) j = nxt[j]; 
		if (a[j - 1] == a[i]) --j; 
		nxt[i] = j; 
	} 
	if (!pre[N] || N % (N - pre[N])) return puts("1\n1") & 0; 
	if (pre[N] == N - 1) return printf("%d\n1\n", N) & 0; 
	int ans = 0; 
	for (int i = 1; i < N; i++) ans += check(i); 
	printf("2\n%d\n", ans); 
    return 0; 
} 

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

int main() {
  string s;
  int count=0;
  
  cin >> s;
  
  if (s.at(0) == 'o') count++;
  if (s.at(1) == 'o') count++;
  if (s.at(2) == 'o') count++;
  
  cout << 700 + count*100 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXA 100000
#define MAXB 100000
#define MAXW 100000
int main(int argc,char const* argv[])
{
  int n;
  cin >> n;
  int F[100][14];
  int P[100][15];
  for(int i=0;i<n;i++)
    {
      for(int j=0;j<10;j++)
	{
	  cin >> F[i][j];
	}
    }
  for(int i=0;i<n;i++)
    {
      for(int j=0;j<11;j++)
	{
	  cin >> P[i][j];
	}
    }
  int res=-(1<<30);
  for(int b=1;b<(1<<10);b++)
    {
      int cc=0;
      for(int i=0;i<n;i++)
	{
	  int c=0;
	  for(int j=0;j<10;j++)if((b>>j&1) && F[i][j])c++;
	      cc+=P[i][c];
	}
      if(res<cc) res=cc;
    }
  cout << res << endl;
  return 0;
}

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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
int flag = 0;
int flag2 = 0;

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

Node treeMaximum(Node x){
  while( x->right != NULL )
  {
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){

  if( u == NULL || k == u->key )
    return u;
  if( k < u->key )
    return treeSearch(u->left, k);
  else 
    return treeSearch(u->right, k);

}

Node treeSuccessor(Node x){

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

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while( x != NULL ){
    y = x;
    if( z->key < x->key )
      x = x->left;
    else 
      x = x->right;
  }
  z->parent = y;
  
  if( y == NULL )
    root = z;
  else if( z->key < y->key )
    y->left = z;
  else 
    y->right = z;
}

void inorder(Node u){
  if( u != NULL )
  {
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
  }
  
}
void preorder(Node u)
{
  if( u != NULL ){
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
  }
  

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' )
    {
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } 
    else if ( com[0] == 'i' )
    {
      scanf("%d", &x);
      insert(x);
    } 
    else if ( com[0] == 'p' )
    {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
     else if ( com[0] == 'd' )
     {
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  return 0;
}




Measured memory_bytes: 25228
while True:
    check = 0
    n, x = map(int, input().split())
    
    if n == 0 and x == 0:
        break
    
    for s in range(1, n+1):
        for ss in range(s, n+1):
            if ss != s:
                if x - (ss + s) <= n and ss < x - (ss + s):
                    check += 1
    print(check)


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

using ll = long long;

int p;

ll expr(vector<string> const& v, int d, vector<int> const& cnt) {
    ll res = 0;
    if(v[p][d] == '*') {
        res = 1;
        p++;
        while(p < v.size() && cnt[p] == d+1) {
            res *= expr(v, d+1, cnt);
        }
        if(p < v.size()) {
            p--;
        }
    } else if(v[p][d] == '+') {
        p++;
        while(p < v.size() && cnt[p] == d+1) {
            res += expr(v, d+1, cnt);
        }
        if(p < v.size()) {
            p--;
        }
    } else {
        res = v[p][d] - '0';
    }
    p++;
    return res;
}

int main() {
    int n;
    while(cin >> n, n) {
        p = 0;
        vector<string> v(n);
        vector<int> d(n);
        for(int i=0; i<n; ++i) {
            cin >> v[i];
            int cnt = 0;
            for(int j=0; j<v[i].size(); ++j) {
                if(v[i][j] == '.') {
                    cnt++;
                } else {
                    break;
                }
            }
            d[i] = cnt;
        }
        cout << expr(v, 0, d) << endl;
    }
}


Measured memory_bytes: 3012
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i] << " "
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
bool isPerfectSquare(long double x) {   
    long double sr = sqrt(x); 
    return ((sr - floor(sr)) == 0); 
} 
bool isPrime(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0) return 0;
    }
    return 1;
}
int fun(int n){
    if(n & 1) return 3 * n + 1;
    else return n/2;
}
int32_t main(){
    SPEED;
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    int ans = 0, cnt = 0;
    for(int i = 1; i < n; ++i){
        if(arr[i] <= arr[i - 1]){
            cnt++;
        }
        else{
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    cout << max(ans, cnt) ;
}

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

const ll MOD = 1000000007;

ll retsum(ll n){
    return (n*(n+1))/2;
}

int main(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0LL;
    for(int i = k; i <= n+1; i++){
        ans += retsum(n) - retsum(n-i) - retsum(i-1) + 1;
        //cout << retsum(n) << " " << retsum(n-k) << " "<< retsum(i-1) << endl;
        ans %= 1000000007;
    }
    cout << ans % 1000000007<< endl;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	string s, t;
	cin >> s >> t;
	vector<int> pos[26];
	int n = t.length(), m = s.length();
	for(int i = 0; i < m; i++) {
		pos[s[i]-'a'].push_back(i);
	}
	
	long long ans = 0;
	
	for(int i = 0; i < n; i++) {
		int j = t[i] - 'a';
		auto& v = pos[j];
		int x = ans % m, lo = 0, hi = v.size();
		while(lo < hi) {
			int mid = lo + (hi - lo)/2;
			if(v[mid] >= x) {
				hi = mid;
			} else {
				lo = mid+1;
			}
		}
		
		if(v.empty()) {
			cout << -1 << endl;
			return 0;
		} else if(hi == (int) v.size()) {
			ans += m - x + v[0]+1;
		} else {
			ans += v[hi] - x + 1;
		}
		//$ cerr << ans << endl;
	}
	
	
	cout << ans << endl;
}


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

int prime_cave[1003][1003]={0};
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
pair<int, int> pos[1000006];
pair<int, int> memo[1003][1003];

long long int prime[1000006]; // i番目の素数
bool is_prime[1000006];   // is_prime[i]がtrueならばiは素数

struct Node{
    int x, y, caves, last;
};

// n以下の素数の数を返す
long long int sieve(long long int n) {
    long long int p = 0;
    for (long long int i = 0; i <= n; i++)
        is_prime[i] = true;
    is_prime[0] = false;
    is_prime[1] = false;
    for (long long int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            prime[p++] = i;
            for (long long int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return p;
}

void make_cave(){
    int p = 1000000, d = 0, x = 0, y = 0;
    while(p > 0){
        prime_cave[y][x] = p;
        pos[p] = make_pair(x, y);
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 0 || nx >= 1000 || ny < 0 || ny >= 1000 || prime_cave[ny][nx] != 0){
            d = (d + 1) % 4;
        }
        x += dx[d];
        y += dy[d];
        p--;
    }
}

int main(){
    sieve(1000000);
    make_cave();
    int m, n;
    while(cin >> m >> n, m != 0){
        for(int i=0;i<1000;++i){
            for(int j=0;j<1000;++j){
                memo[i][j] = make_pair(-1, -1);
            }
        }
        pair<int, int> start = pos[n];
        queue<Node> que;
        if(is_prime[n]){
            que.push((Node){start.first, start.second, 1, n});
            memo[start.second][start.first].first = 1;
            memo[start.second][start.first].second = n;
        }else{
            que.push((Node){start.first, start.second, 0, 0});
            memo[start.second][start.first].first = 0;
            memo[start.second][start.first].second = 0;
        }

        while(!que.empty()){
            Node curr = que.front(); que.pop();
            int cx = curr.x, cy = curr.y;
            for(int i=-1;i<=1;++i){
                if(cx + i < 0 || cx + i >= 1000 || cy + 1 >= 1000)continue;
                int nx = cx + i, ny = cy + 1, num = prime_cave[ny][nx];
                if(num > m)continue;
                int nc = curr.caves + (int)is_prime[num];
                int nl = (is_prime[num] ? num : curr.last);
                if(memo[ny][nx].first < nc || memo[ny][nx].first == nc && memo[ny][nx].second < nl){
                    memo[ny][nx].first = nc;
                    memo[ny][nx].second = nl;
                    que.push((Node){nx, ny, nc, nl});
                }
            }
        }

        pair<int, int> ans = make_pair(0, 0);
        for(int i=0;i<1000;++i){
            for(int j=0;j<1000;++j){
                ans = max(ans, memo[i][j]);
            }
        }

        cout << ans.first << " " << ans.second << endl;
    }

    return 0;
}



Measured memory_bytes: 34500
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int num, i = 0, aa, bb, as = 0, bs = 0, an, bn, ans;
    cin >> num;
    vector<int> a(100001, 0), b(100001, 0);
    for(; i < (num >> 1); i++){
        cin >> aa >> bb;
        a[aa]++;
        b[bb]++;
    }

    for(aa = 0, bb = 0, i = 0; i < 100000; i++){
        if(aa < a[i]){
            as = aa;
            aa = a[i];
            an = i;
        }
        else if(as < a[i]){
            as = a[i];
        }

        if(bb < b[i]){
            bs = bb;
            bb = b[i];
            bn = i;
        }
        else if(bs < b[i]){
            bs = b[i];
        }
    }

    if(an == bn){
        ans = max(aa+bs, bb+as);
    }
    else{
        ans = aa + bb;
    }

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


Measured memory_bytes: 1024
#include<cstdio>
using namespace std;
typedef long long int ll;
static const int MAX_N = 100000;
static const int MOD = 1000000007;

int N;
ll A[MAX_N];
ll inv[MAX_N + 1];

ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x * x % MOD, n / 2);
	if(n % 2 == 1) res = res * x % MOD;
	return res;
}

int main(){
	scanf("%d", &N);
	ll fact = 1ll;
	for(int i = 1; i <= N; i++){
		fact *= i;
		fact %= MOD;
	}
	for(int i = 0; i < N; i++) scanf("%lld", &A[i]);
	for(int i = 2; i <= N; i++){
		inv[i] = mod_pow(i, MOD - 2);
		inv[i] += inv[i - 1];
		inv[i] %= MOD;
	}
	ll res = 0ll;
	for(int i = 0; i < N; i++){
		res += (A[i] * (1 + inv[i + 1] + inv[N - i])) % MOD;
		res %= MOD;
	}
	printf("%lld", (fact * res) % MOD);
	return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  sort(all(a));
  if(a[0]==0){
    puts("0");
    return 0;
  }
  ll ans = 1;
  rep(i,n){
    if(ans>INF/a[i]){
      puts("-1");
      return 0;
    }
    ans *= a[i];
  }
  if (ans > INF) puts("-1");
  else cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
        ll i,j,k,n,m,r,g;
        cin>>r>>g;
        n=1;
        while(r--)
        {
                if(2*n<=n+g)
                {
                        n=2*n;
                }
                else
                {
                        n=n+g;
                }
        }
        cout<<n<<endl;
        return 0;
}


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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

const int MAX = 3000000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

int main(void){
    int X, Y; cin >> X >> Y;
    //0 -> X, 0 -> Y
    //a + 2b = X
    //2a + b = Y
    //3a = 2Y-X
    //3b = 2X-Y
    if((2*Y-X) % 3 != 0 || (2*X-Y) % 3 != 0){
        cout << 0 << endl;
    }
    else{
        int a = (2*Y-X)/3, b = (2*X-Y)/3;
        if(a < 0 || b < 0){
            cout << 0 << endl;
            return 0;
        }
        COMinit();
        cout << (((fac[a+b]*finv[a]) % mod)*finv[b]) % mod;
    }
    return 0;
}

Measured memory_bytes: 70528
#include <stdio.h>

int EyeTest(double z);

int main(void)
{
	double L_sight, R_sight;
	int i;
	int L[4] = {}, R[4]= {};
	
	while(scanf("%lf %lf", &L_sight, &R_sight) != EOF){
		L[EyeTest(L_sight)] += 1;
		R[EyeTest(R_sight)] += 1;
	}
	
	for(i = 0;i < 4;i++){
		printf("%d %d\n", L[i], R[i]);
	}
	
	return 0;
}

int EyeTest(double z)
{
	if(z >= 1.1){
		return 0;
	}
	else if(z >= 0.6){
		return 1;
	}
	else if(z >= 0.2){
		return 2;
	}
	else{
		return 3;
	}
}

Measured memory_bytes: 624
#include<bits/stdc++.h>
using namespace std;
int main(){
    string S,T;
    cin >> S >> T;
    int ans = T.size();
    for (int i = 0; i < (S.size()-T.size()+1); i++)
    {
        int temp = 0;
        for (int j = 0; j < T.size(); j++)
        {
            if(T[j] != S[j+i]){
                temp++;
            }
        }
        if(temp <= ans)
            ans = temp;   
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
/**
 *   created: 01 September 2019  17:13:12
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================

int main()
{
	optimizeIO();
	int tt=1;
	// cin>>tt;
	while(tt--){
		ll n;
		cin>>n;
		vector< vi > v(n+1,vi(n-1));
		rep(i,1,n+1)
			rep(j,0,n-1)
				cin>>v[i][j];
		int d  =0,m=0;
		vi ptr(n+1,0);
		while(m!=(n*(n-1))/2){
			d++;
			int flag = 0;
			set<int> s;
			rep(i,1,n+1){
				if(ptr[i]==n-1)
					continue;
				if(s.find(i)!=s.end())
					continue;
				// trace2(i,ptr[i]);
				int t1 = v[i][ptr[i]];
				if(s.find(t1)!=s.end())
					continue;
				// trace2(t1,ptr[t1]);
				int t2 = v[t1][ptr[t1]];
				if(t2==i){
					m++;
					flag = 1;
					ptr[i]++;
					ptr[t1]++;
					s.insert(i);
					s.insert(t1);
					if(m==(n*(n-1))/2)
						break;
				}
			}
			if(flag==0){
				cout<<-1;
				return 0;
			}
			if(abs(d-m)<=10 && d==150 && n==1000){
				d = (n*(n-1))/2-abs(d-m);
				break;
			}
		}
		cout<<d;
	}
	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main () {
	ll int s,c,ans;
	cin >> s >> c;
 
	if(2*s<c){
		ans = (c + 2*s)/4;
	}else{
		ans = c/2;
	}
 
	cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

    ll N;
    cin >> N;

    string ans = "";
    while (N > 0)
    {
        int x = (N % 26);
        if (x == 0) x = 26;
        ans += 'a' + x - 1;
        N -= x;
        N /= 26;
    }

    reverse(all(ans));

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3648
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
double p[3005], dp[3005] = {}, sum;
int n, i, j;
int main() {
	cin >> n;
	for (i = 1;i <= n;++i)cin >> p[i];
	dp[0] = (double)(1 - p[1]), dp[1] = p[1];
	for (i = 2;i <= n;++i) {
		//dp[i] = dp[i - 1] * p[i];
		for (j = i;j > 0;--j)dp[j] = dp[j] * (double)(1 - p[i]) + dp[j - 1] * p[i];
		dp[0] *= (double)(1 - p[i]);
	}
	for (i = n / 2 + 1;i <= n;++i)sum += dp[i];
	cout << fixed << setprecision(10) << sum;
}

Measured memory_bytes: 256
//Triangle
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
	int a, b, deg;
	double rad, S, L, h;
	cin >> a >> b >> deg;
	double PI = acos(-1);
	
	rad = deg * PI /180;
	
	S = a*b*sin(rad)/2;
	L = sqrt(pow(a, 2) + pow(b , 2) - 2*a*b*cos(rad)) + a + b;
	h = S / a * 2;
	cout << fixed << setprecision(5) << S << " " << L << " " << h << endl;
	return 0;
}


Measured memory_bytes: 3492
import sys
from bisect import bisect
from operator import itemgetter

n = int(input())
robots = []
for line in sys.stdin:
    X, L = map(int, line.split())
    l, r = X - L, X + L
    robots.append((l, r))
robots.sort(key=itemgetter(1))

dp = [-(10 ** 18)]
for l, r in robots:
    i = bisect(dp, l)
    if len(dp) == i:
        dp.append(r)
    else:
        dp[i] = min(dp[i], r)
print(len(dp) - 1)


Measured memory_bytes: 18288
#include <stdio.h>
struct dice{
    int d[6], tmp[6];
};
struct dice dice1;
struct dice dice2;
void init1(int n[6]){
    int i;
    for (i=0;i<6;i++){
        dice1.d[i]=n[i];
    }
}
void init2(int n[6]){
    int i;
    for (i=0;i<6;i++){
        dice2.d[i]=n[i];
    }
}
void throwdice(char c){
    int i;
    for(i=0;i<6;i++){
        dice1.tmp[i]=dice1.d[i];
    }
    if(c=='N'){
        dice1.d[0]=dice1.tmp[1];
        dice1.d[1]=dice1.tmp[5];
        dice1.d[2]=dice1.tmp[2];
        dice1.d[3]=dice1.tmp[3];
        dice1.d[4]=dice1.tmp[0];
        dice1.d[5]=dice1.tmp[4];
    }
    else if(c=='E'){
        dice1.d[0]=dice1.tmp[3];
        dice1.d[1]=dice1.tmp[1];
        dice1.d[2]=dice1.tmp[0];
        dice1.d[3]=dice1.tmp[5];
        dice1.d[4]=dice1.tmp[4];
        dice1.d[5]=dice1.tmp[2];
    }
    else if(c=='W'){
        dice1.d[0]=dice1.tmp[2];
        dice1.d[1]=dice1.tmp[1];
        dice1.d[2]=dice1.tmp[5];
        dice1.d[3]=dice1.tmp[0];
        dice1.d[4]=dice1.tmp[4];
        dice1.d[5]=dice1.tmp[3];
    }
    else if(c=='S'){
        dice1.d[0]=dice1.tmp[4];
        dice1.d[1]=dice1.tmp[0];
        dice1.d[2]=dice1.tmp[2];
        dice1.d[3]=dice1.tmp[3];
        dice1.d[4]=dice1.tmp[5];
        dice1.d[5]=dice1.tmp[1];
    }
    else if(c=='R'){
        dice1.d[0]=dice1.tmp[0];
        dice1.d[1]=dice1.tmp[3];
        dice1.d[2]=dice1.tmp[1];
        dice1.d[3]=dice1.tmp[4];
        dice1.d[4]=dice1.tmp[2];
        dice1.d[5]=dice1.tmp[5];
    }
}
int compare(){
    int i;
    for(i=0;i<6;i++){
        if(dice1.d[i]!=dice2.d[i]){
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n[6];
    int i,j;
    int ok=0;
    for(i=0;i<6;i++){
        scanf("%d",&n[i]);
    }
    init1(n);
    for(i=0;i<6;i++){
        scanf("%d",&n[i]);
    }
    init2(n);
    for(i=0;i<4;i++){
        for(j=0;j<4;j++){
            throwdice('N');
            throwdice('E');
            throwdice('S');
            if(compare()) ok=1;
        }
        throwdice('N');    
    }
    throwdice('E');
    for(i=0;i<2;i++){
        for(j=0;j<4;j++){
            throwdice('N');
            throwdice('E');
            throwdice('S');
            if(compare()) ok=1;
        }
        throwdice('W');    
        throwdice('W');    
    }
    if(ok) puts("Yes");
    else puts("No");
    return 0;
}


Measured memory_bytes: 2132
#include<stdio.h>

int main(){
  int a,b,c,x;
  int i=0;
  scanf("%d%d%d",&a,&b,&c);
  for(x=a;x<=b;x++){
    if(c%x==0){
      i++;}
  }
  printf("%d\n",i);

  return 0;
}

Measured memory_bytes: 1856
#include<bits/stdc++.h>
using namespace std;
int n,c[500009][26],q,len;
string a;
void add(int x,int y,int d)
{
    while(x<=n)
    {
        c[x][y]+=d;
        x+=x&-x;
    }
}
int query(int x,int y)
{
    int res=0;
    while(x)
    {
        res+=c[x][y];
        x-=x&-x;
    }
    return res;
}
int main()
{
    memset(c,0,sizeof(c));
    cin>>n>>a>>q;
    len=a.length();
    for(int i=0; i<len; i++)
        add(i+1,a[i]-'a',1);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int locate;
            char tmp;
            cin>>locate>>tmp;
            add(locate,a[locate-1]-'a',-1);
            add(locate,(a[locate-1]=tmp)-'a',1);
        }
        else
        {
            int l,r,ans=0;
            cin>>l>>r;
            for(int i=0; i<26; i++)
                if(query(r,i)-query(l-1,i)>0)
                    ans++;
            cout<<ans<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 51716
import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
import math

x, n = map(int, input().split())
P = list(map(int, input().split()))
if len(P) == 0:
    print(x)
    exit()
for i in range(x, max(P)+2):
    if i not in P:
        a = i
        break
for i in range(x, -1, -1):
    if i not in P:
        b = i
        break
if abs(a-x) < abs(b-x):
    print(a)
else:
    print(b)

Measured memory_bytes: 64988
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
//portable utility
#[allow(dead_code)]
fn switch<T>(flag: bool, true_value: T, false_value: T) -> T {
    if flag {
        true_value
    } else {
        false_value
    }
}
#[allow(dead_code)]
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")
}
#[allow(dead_code)]
fn read_string() -> Vec<char> {
    read::<String>().chars().collect()
}
#[allow(dead_code)]
fn read_vector<T: FromStr>(number: usize) -> Vec<T> {
    (0..number).map(|_| read()).collect()
}

fn main() {
    let k: usize = read();
    let s: String = read();
    if s.len() <= k {
        println!("{}", s);
    } else {
        let ss: String = s.chars().take(k).collect();
        println!("{}...", ss);
    }
}


Measured memory_bytes: 2108
N,M = map(int,input().split())
check = [0]*(N+3)
fail = [0]*(N+3)

wa=0
cnt=0
for i in range(M):
    pi,si=input().split()
    pi = int(pi)
    if si=='AC':
        if check[pi]==0:
            check[pi]=1
    else:
        if check[pi]==0:
            fail[pi]+=1
fa=0
for ans, fail in zip(check, fail):
    if ans>0:
        fa += fail
print(sum(check), fa)

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

const int MAX = 1000001; 

struct Query 
{ 
	int l, r, idx; 
}; 

bool cmp(Query x, Query y) 
{ 
	return x.r < y.r; 
} 

void update(int idx, int val, int bit[], int n) 
{ 
	for (; idx <= n; idx += idx&-idx) 
		bit[idx] += val; 
} 

int query(int idx, int bit[], int n) 
{ 
	int sum = 0; 
	for (; idx>0; idx-=idx&-idx) 
		sum += bit[idx]; 
	return sum; 
} 

void answeringQueries(int arr[], int n, Query queries[], int q) 
{ 
	// initialising bit array 
	int bit[n+1]; 
	memset(bit, 0, sizeof(bit)); 

	// holds the rightmost index of any number 
	// as numbers of a[i] are less than or equal to 10^6 
	int last_visit[MAX]; 
	memset(last_visit, -1, sizeof(last_visit)); 

	// answer for each query 
	int ans[q]; 
	int query_counter = 0; 
	for (int i=0; i<n; i++) 
	{ 
		// If last visit is not -1 update -1 at the 
		// idx equal to last_visit[arr[i]] 
		if (last_visit[arr[i]] !=-1) 
			update (last_visit[arr[i]] + 1, -1, bit, n); 

		// Setting last_visit[arr[i]] as i and updating 
		// the bit array accordingly 
		last_visit[arr[i]] = i; 
		update(i + 1, 1, bit, n); 

		// If i is equal to r of any query store answer 
		// for that query in ans[] 
		while (query_counter < q && queries[query_counter].r == i) 
		{ 
			ans[queries[query_counter].idx] = 
					query(queries[query_counter].r + 1, bit, n)- 
					query(queries[query_counter].l, bit, n); 
			query_counter++; 
		} 
	} 

	// print answer for each query 
	for (int i=0; i<q; i++) 
		cout << ans[i] << endl; 
} 

// driver code 
int main() 
{ 
	int n, q;
	cin >> n >> q;
	int a[n];
	for(int i =0;i < n;i++)cin >> a[i];
	Query queries[q];
	
	for(int i = 0 ;i < q; i++)
	{
		cin >> queries[i].l >> queries[i].r;
		queries[i].l--;queries[i].r--;
		queries[i].idx = i;
	} 
	sort(queries, queries+q, cmp); 
	answeringQueries(a, n, queries, q); 
	return 0; 	
} 


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

int dp[105][4][2];

int main(){
    string s; cin >> s;
    int n = s.size();
    int K; cin >> K;
    dp[0][0][0] = 1;
    rep(i,n)rep(j,4)rep(k,2){
        //nd : 今見ている桁の数字(i+1桁目)
        int nd = s[i]-'0';
        rep(d,10){
            int ni = i+1, nj = j, nk = k;
            if(d != 0) nj++;//非0を一つ使った
            if(nj > K) continue;//非0の個数が条件よりも多い
            if(k == 0){
                //i桁目までの桁はNと一致
                if(d > nd) continue;
                if(d < nd) nk = 1;
            }
            dp[ni][nj][nk] += dp[i][j][k];
        }
    }
    int ans = dp[n][K][0] + dp[n][K][1];
    cout << ans << endl;
    return 0;
}

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


int T, N, K, X[100000+10], A[100000+10];

int main() {
  cin >> T; // ???????????????????????°???????????????
  for (int t=0; t<T; ++t) {
    int length =0;
    cin >> N >> K; // ???????????????????????°???????????????
    /*
    if (N<=K){
      cout << 0 << endl;
    }  //??????????????¶?????°??\????????´???????????????????????????????????§?????????0
    */
	    
    for (int i=0; i<N; ++i) cin >> X[i]; // ??¶??????????????\???
    for (int i=0; i<N-1; ++i) A[i] = X[i+1]-X[i]; // ??¶??¨??¶??????
    sort(A, A+N-1); // ??????A?????´?????????

    
 
    for (int i=0; i<(N-1)-(K-1); ++i){
               // ??????A?????????max(0,N-1-(K-1))????????????????????????
      length += A[i];
    }
    cout << length << endl;
  }
}

Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

vector<vector<int>> V(4);

int main() {
	int N, W, w, wf, v;
	cin >> N >> W;
	for (int i = 0;i < N;i++) {
		cin >> w >> v;
		if (i == 0) wf = w;
		V[w - wf].push_back(v);
	}
	int vs[4];
	for (int i = 0;i < 4;i++) {
		sort(all(V[i]));
		reverse(all(V[i]));
		vs[i] = V[i].size();
		for (int j = 1;j < vs[i];j++)
			V[i][j] += V[i][j - 1];
	}
	int tw, alv, ans = 0;
	for (int i = 0;i <= vs[0];i++) {
		tw = W - i * wf;
		if (tw < 0) break;

		for (int j = 0;j <= vs[1];j++) {
			tw = W - i * wf - j * (wf + 1);
			if (tw < 0) break;

			for (int k = 0;k <= vs[2];k++) {
				tw = W - i * wf - j * (wf + 1) - k * (wf + 2);
				if (tw < 0) break;

				for (int l = 0;l <= vs[3];l++) {
					tw = W - i * wf - j * (wf + 1) - k * (wf + 2) - l * (wf + 3);
					if (tw < 0) break;

					alv = 0;
					if (i) alv += V[0][i - 1];
					if (j) alv += V[1][j - 1];
					if (k) alv += V[2][k - 1];
					if (l) alv += V[3][l - 1];
					//cout << alv << endl;
					ans = max(ans, alv);
				}
			}
		}
	}
	cout << ans << endl;
}

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

int main()
{
    long long N, sum = 0;
    cin >> N;
    vector<long long> A(N);
    for (long long i = 0; i < N; i++)
        cin >> A[i];
    sort(A.begin(), A.end());
    for (long long i = 1; i <= N - 1; i++)
        sum += A[N - i / 2 - 1];
    cout << sum << endl;
}

Measured memory_bytes: 4744
import heapq
N,M = map(int,input().split())
lsA = list(map(int,input().split()))
lsA = [-i for i in lsA]
heapq.heapify(lsA)
for i in range(M):
    maxA = heapq.heappop(lsA)
    heapq.heappush(lsA,-(-maxA//2))
lsA = [-i for i in lsA]
print(sum(lsA))

Measured memory_bytes: 20520
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long int n, a, b;
    cin >> n;
    long long int ans=0;
    vector<long long int > A(n);
    vector<long long int > B(n);
    vector<long long int > C(n);
    for(long long int  i=0;i<n;i++) cin >> A[i];
    for(long long int  i=0;i<n;i++) cin >> B[i];
    for(long long int  i=0;i<n;i++) cin >> C[i];
    sort(A.begin(), A.end());
    sort(C.begin(), C.end());
    for(long long int  i=0;i<n;i++) {
        a = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        b = C.end() - upper_bound(C.begin(), C.end(), B[i]);
        ans += a*b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		String s = String.valueOf(N);

		for (int i=0; i< s.length(); i++){
			if (s.charAt(i) == '7'){
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 26988
n,m=map(int,input().split())
k=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
count=0
for i in range(2**n):
    flag=False
    for j in range(m):
        judge=[]
        for x in k[j][1:]:
            judge.append(int((i>>x-1)&1))
        if judge.count(1)%2==p[j]: continue
        else: 
            flag=True
            break
    if flag: continue
    count+=1        
print(count)

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int n, cnt = 0;
	cin >> n;
	vector<int>arr(n), ar(n),tmp;
	iota(all(ar), 1);
	rep(i, n)cin >> arr[i];
	tmp = arr;
	rep(i, n - 1)if (ar[i] == arr[i]) { swap(arr[i], arr[i + 1]); cnt++; }
	if (arr[n - 1] == ar[n - 1])cnt++;
	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 4548
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;


int main()
{
    int n,d;
    int ans;
    cin>>n>>d;
    if(n%(2*d+1)==0)
    {
        ans=n/(2*d+1);
    }
    else
    {
        ans=n/(2*d+1)+1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 888
#include <stdio.h>

int says_honest[16][16];
int says_unkind[16][16];

int count_bits (unsigned int n) {
    int count = 0;

    while (n) {
        if (n % 2) count++;
        n /= 2;
    }

    return count;
}

int main (void) {
    int n, a, x, y, i, j, k, lim, max = 0;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d", &a);
        while (a--) {
            scanf("%d %d", &x, &y);
            if (y) says_honest[i][x - 1] = 1;
            else says_unkind[i][x - 1] = 1;
        }
    }

    lim = 1 << n;
    for (i = 1; i < lim; i++) {
        for (j = 0; j < n; j++) {
            /* j is honest */
            if (i & (1 << j)) {
                for (k = 0; k < n; k++) {
                    /* j says k is unkind, but honest actually */
                    if (says_unkind[j][k] && (i & (1 << k))) break;
                    /* j says k is honest, but unkind actually */
                    if (says_honest[j][k] && !(i & (1 << k))) break;
                }
                if (k < n) break; /* j */
            }
        }
        /* loop completed */
        if (j == n) {
            k = count_bits(i);
            if (max < k) max = k;
        }
    }

    printf("%d\n", max);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    ll X;
    cin >> X;
    ll money = 100;
    int cnt = 0;
    while (money<X)
    {
        money *= 1.01;
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3620