akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
# https://atcoder.jp/contests/abc101/tasks/abc101_a
S = read()[:-1]
ans = 0
for s in S:
    ans += 1 if s == '+' else - 1
print(ans)


Measured memory_bytes: 3316
// #pragma GCC optimize("unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC option("arch=native", "tune=native", "no-zero-upper")
// #pragma GCC
// target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("tree-vectorize","openmp","predictive-commoning")
// #pragma GCC option("D_GLIBCXX_PARALLEL","openmp")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

template <class T>
void chmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
  if (a < b) a = b;
}

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

#define endl "\n"

void solve() {
  int N, M;
  cin >> N >> M;
  vector<P> rs(M);
  cin >> rs;
  sort(all(rs), [](P a, P b) {
    if (a.second != b.second)
      return a.second < b.second;
    else
      return a.first < b.first;
  });
  int idx = 0;
  int ans = 0;
  while (idx < M) {
    int b = rs[idx].second;
    idx++;
    ans++;
    while (idx < M && rs[idx].first < b) idx++;
  }
  cout << ans << endl;
  return;
}

signed main() {
  fastio();
  solve();
  //   int t;
  //   cin >> t;
  //   while (t--) solve();

  // int t; cin >> t;
  // for(int i=1;i<=t;i++){
  //   cout << "Case #" << i << ": ";
  //   solve();
  // }
  return 0;
}


Measured memory_bytes: 1024
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    import bisect
    n, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    a.sort()
    que = deque()

    if n == k:
        que.extend(a)
    elif a[-1] < 0 and k % 2 == 1:
        que.extend(a)
        for _ in range(n - k):
            que.popleft()
    else:
        b = [[] for _ in range(n)]
        for i in range(n):
            b[i] = [abs(a[i]), a[i]]
        b.sort(reverse=True)
        b = deque(b)
        que1 = deque()
        que2 = deque()
        sign = 1

        for i in range(k):
            val_abs, val = b.popleft()
            if val > 0:
                que1.append(val_abs)
            elif val < 0:
                que2.append(val_abs)
                sign *= -1
            else:
                print(0)
                return

        if sign == -1:
            add1, add2 = 0, 0
            rmv1, rmv2 = 10 ** 19, 10 ** 19
            if que1:
                rmv1 = que1[-1]
                for x_abs, x in b:
                    if x < 0:
                        add1 = x_abs
                        break
            if que2:
                rmv2 = que2[-1]
                for x_abs, x in b:
                    if x > 0:
                        add2 = x_abs
                        break

            if add1 == add2:
                print(0)
                return

            if add1 * rmv2 > add2 * rmv1:
                que2.append(add1)
                que1.pop()
            else:
                que1.append(add2)
                que2.pop()

        que.extend(que1)
        que.extend(que2)

    while len(que) > 1:
        que.append(que.popleft() * que.popleft())

    print(que.popleft() % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 171412
n = int(input())
s = input()
max_l = 0

for i in range(n):
    # 検索元の部分文字列の一文字目i
    for l in range(max_l + 1,((n - i) // 2) + 1):
        # lは検索元の文字列の長さ
        # i文字目からi+l-1文字目がi+l文字目からn-1文字目
        if s[i:i+l] in s[i+l:]:
            if l > max_l:
                max_l = l
        else:
            break
print(max_l)

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

const int N = 10;

int n, C, A[N], P[N], cnt;
double ans, f[350][35];

inline double dp() {
  memset(f, 0, sizeof(f));
  f[n * A[n - 1]][0] = 1;
  for (int i = 0; i < n * C; ++i) {
    if (!(i % n)) continue;
    for (int j = i; j <= n * C; ++j)
      for (int s = 0; s < 1 << (n - 1); ++s)
        if (!(s & (1 << P[i % n - 1]))) {
          int p = i + n * A[P[i % n - 1]];
          p = std::min(n * C, std::max(p, j));
          int t = s | (1 << P[i % n - 1]);
          f[p][t] += f[j][s];
        }
  }
  return f[n * C][(1 << (n - 1)) - 1];
}

int main() {
  std::cin >> n >> C;
  for (int i = 0; i < n; ++i) {
    std::cin >> A[i];
    P[i] = i;
  }
  std::sort(A, A + n);
  do ans += dp(), ++cnt;
  while (std::next_permutation(P, P + n - 1));
  ans = ans / cnt / std::pow(C, n - 1);
  printf("%.15lf\n", ans);
  return 0;
}


Measured memory_bytes: 512
N, M = gets.chomp.split(" ").map(&:to_i)
D = []
N.times{
  D << gets.chomp.split(" ").map(&:to_i)
}

D.sort_by!{|a, b| a}
ans, rst = [0, M]
while rst > 0 do
  a, b = D.shift
  if rst >= b then
    ans += a * b
    rst -= b
  else
    ans += a * rst
    rst = 0
  end
end

puts ans


Measured memory_bytes: 12664
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define MuhammedAly ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define popc(x) __builtin_popcount(x)
#define LLMX 1e18
#define NotinRange(n,m) i<0||i>=(n)||j<0||j>=(m)
#define mem(x,y) memset((x),(y),sizeof (x))
#define sz(a) (int)(a).size()
#define inFile(s) freopen((s),"r",stdin)
#define	outFile(s) freopen((s),"w",stdout)
#define biEdge(v, a, b) (v)[(a)].pb((b)), (v)[(b)].pb((a))
#define pi (2 * acos(0))
#define X real()
#define Y imag()
#define cross(a, b) ((conj(a) * (b)).Y)
#define dot(a, b) ((conj(a) * (b)).X)
#define vec(a,b) ((b) - (a))
#define ll long long
typedef long double ld;
typedef complex<double>point;
typedef tuple<int, int, int> line;
typedef pair<point, point>segment;
typedef vector<point>polygon;
const int N = 1e5 + 5, M = 20 + 5, OO = 0x3f3f3f3f, mod = 1e9 + 7, base = 131, mod2 = 1000136437, mod3 = 998244353;
const double EPS = 1e-9;
ll n, w, memo[105][N], W[105], v[105], sum;
ll solve(int i, int V)
{
    if(V == 0)
        return 0;
    if(i == n)
        return LLMX;
    ll &ret = memo[i][V];
    if(~ret)
        return ret;
    ret = solve(i + 1, V);
    if(V - v[i] >= 0)
        ret = min(ret, solve(i + 1, V - v[i]) + W[i]);
    return ret;
}
int main()
{
    MuhammedAly
    mem(memo, -1);
    cin >> n >> w;
    for(int i = 0 ; i < n ;i++)
        cin >> W[i] >> v[i], sum += v[i];
    int ans = 0;
    for(int i = 1 ; i <= sum ; i++)
        if(solve(0, i) <= w)
            ans = i;
    cout << ans;
    return 0;
}

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

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

long dp[100010];

int main(){
	int n, w;
	scanf("%d%d", &n, &w);
	int weight, value;
	for(int i = 0; i < n; i++) {
		scanf("%d%d", &weight, &value);
		for(int j=w-weight; j >= 0; j--)
			chmax(dp[j+weight], dp[j] + value);
	}
	long ret = 0;
	for(int i=0; i <= w; i++) chmax(ret, dp[i]);
	printf("%ld", ret);
}

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

using namespace std;
using ll = long long;

#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define REP(i,n) FOR(i, 0, n)
#define FORD(i,a,n) for(int i=(a); i>=(n); i--)
#define REPD(i,n) FOR(i, n, 0)

#define ALL(o) (o).begin(), (o).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T, vector<T>, greater<T> >;



int main(){
	char c;
	cin >> c;
	if(c >= 'a' && c <= 'z') {
		cout <<'a' << endl;
	} else {
		cout << 'A'<<endl;
	}
    // Failed to predict input format
    return 0;
}



Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
int N, Li[110], ans;
int ok(int a, int b, int c)
{
	if(a+b>c&&b+c>a&&c+a>b)
	    return 1;
	return 0;
}
int main()
{
	scanf("%d", &N);
	for(int i=1;i<=N;i++)
	    scanf("%d", &Li[i]);
	for(int i=1;i<=N;i++)
	    for(int j=i+1;j<=N;j++)
	        for(int k=j+1;k<=N;k++)
	        {
	        	if(Li[i]!=Li[j]&&Li[j]!=Li[k]&&Li[i]!=Li[k])
	        	{
	        		if(ok(Li[i], Li[j], Li[k]))
	        		    ans++;
				}
			}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1728
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt(),f=0;
    int[] a=new int[n];
    for(int i=0;i<n;i++){
      a[i]=sc.nextInt();
    }
    for(int i=0;i<n;i++){
      if(a[a[i]-1]==i+1){
        f++;
      }
    }
    System.out.println(f/2);
  }
}


Measured memory_bytes: 50780
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main() {
	int N;
	cin >> N;
	long long back = ceil(N/15) *200;
	long long price = N*800 - back;
	cout << price << endl;
	
	return 0;
}

Measured memory_bytes: 256
use proconio::{fastout, input};
use std::*;

#[allow(dead_code)]
#[fastout]
fn main() {
    input! {
        k: usize
    }
    let mut a = vec![0; k + 1];
    a[1] = 7 % k;
    for i in 2..k + 1 {
        a[i] = (a[i - 1] * 10 + 7) % k;
    }
    for i in 1..k + 1 {
        if a[i] == 0 {
            println!("{}", i);
            return;
        }
    }
    println!("-1");
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

  string S=in<string>();
  int len=0,start=-1,max_len=0;
  for(int i=0,ei=S.size();i<ei;i++){
    if(S[i]=='A' || S[i]=='T' || S[i]=='G' || S[i]=='C'){
      len++;
      if(start<0) start = i;
    }
    else{
      len = 0;
      start = -1;
    }
    max_len = max(len,max_len);
  }
  
  cout << max_len << endl;
  return 0;
}

Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
  stack<int> st;
  int n;
  while (cin >> n) {
    if (n == 0) {
      cout << st.top() << endl;
      st.pop();
    } else {
      st.push(n);
    }
  }
}

Measured memory_bytes: 1200
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    ans=[50]*26
    
 
    
    N=I()
    for i in range(N):
        S=input()
        temp=[0]*26
        for j in range(len(S)):
            m=ord(S[j])-97
            temp[m]+=1
        for j in range(26):
            ans[j]=min(ans[j],temp[j])
            
    res=""
    for j in range(26):
        res+=chr(j+97)*ans[j]
        
    print(res)
            
        
    
        

main()


Measured memory_bytes: 38768
from bisect import bisect_left,bisect

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i for i in range(n + 1) if is_prime[i]}

p = primes(10**5)
kouho = []
for i in p:
    if (i+1)//2 in p:
        kouho.append(i)
kouho.sort()
q = int(input())
for i in range(q):
    l , r = map(int,input().split())
    s = bisect_left(kouho,l)
    t = bisect(kouho,r)
    print(t-s)

Measured memory_bytes: 4596
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
  }

#[fastout]
fn main() {
    input!{
        a: usize,
        b: usize,
    }

    println!("{}", (a-1)*(b-1));

}


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

const int MAX_N = 1 << 19;
const int def = 1 << 25;
const int INF = 1 << 25;

typedef pair<int, int> ValIdx;
struct MinSegTreeIdx {
	int n;
	ValIdx node[2 * MAX_N - 1];

	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) node[i] = make_pair(def, -1);
	}

	ValIdx merge(ValIdx l, ValIdx r) {
		if(l.first <= r.first) return l;
		return r;
	}

	void update(int k, int a) {
		k += n - 1;
		node[k] = make_pair(a, k - (n - 1));
		while(k > 0) {
			k = (k - 1) / 2;
			node[k] = merge(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}

	ValIdx query(int a, int b) { return query(a, b, 0, 0, n); }

	ValIdx query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return make_pair(def, def);
		if(a <= l && r <= b) return node[k];
		ValIdx vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ValIdx vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return merge(vl, vr);
	}

	void show() {
		for(int i = 0; i < n; i++) cout << node[i + n - 1].first << " ";
		cout << endl;
	}
};

int a[200000];
MinSegTreeIdx even, odd;
int N;
set<int> s;

typedef pair<int, int> P;
typedef pair<P, int> Pi;

vector<P> ps;
vector<int> children[200000];

Pi f(int L, int R){
	int len = R - L;
	if(len <= 0) {
		return { {-1, -1}, -1 };
	}

	int id = ps.size();
	ps.push_back({ -1, -1 });

	if(len == 2) {
		ps[id] = { a[L], a[L + 1] };
		return { ps[id] ,id };
	}

	MinSegTreeIdx* st1 = &even;
	MinSegTreeIdx* st2 = &odd;
	if(L % 2 == 1) {
		st1 = &odd;
		st2 = &even;
	}

	auto res1 = st1->query(L, R - 1);
	//cout << res1.first << " " << res1.second << endl;
	int l = res1.second;
	int right = *s.upper_bound(l);
	auto res2 = st2->query(l + 1, right);
	//cout << res2.first << " " << res2.second << endl;
	int r = res2.second;

	s.insert(l);
	s.insert(r);

	auto k1 = f(L, l), k2 = f(l + 1, r), k3 = f(r + 1, R);
	if(k1.second != -1) children[id].push_back(k1.second);
	if(k2.second != -1) children[id].push_back(k2.second);
	if(k3.second != -1) children[id].push_back(k3.second);

	//st1->update(l, INF);
	//st1->update(r, INF);
	//st2->update(l, INF);
	//st2->update(r, INF);

	ps[id] = { a[l], a[r] };
	return { ps[id] ,id };
}

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

	cin >> N;

	even.init(N);
	odd.init(N);

	for(int i = 0; i < N; i++) {
		cin >> a[i];
		if(i % 2 == 0) {
			even.update(i, a[i]);
			odd.update(i, INF);
		}
		else {
			even.update(i, INF);
			odd.update(i, a[i]);
		}
	}
	//even.show();
	//odd.show();

	s.insert(N);

	deque<int> ans;
	priority_queue<Pi, vector<Pi>, greater<Pi>> q;
	auto res = f(0, N);
	q.push(res);
	while(q.size()) {
		auto pi = q.top();
		q.pop();
		ans.push_back(pi.first.first);
		ans.push_back(pi.first.second);
		int id = pi.second;
		for(auto c : children[id]) {
			q.push({ ps[c], c });
		}
	}

	for(int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}


Measured memory_bytes: 65652
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


# MOD = int(1e09) + 7
MOD = 998244353
INF = int(1e15)


def divisor(N):
    res = []
    i = 2
    while i * i <= N:
        if N % i == 0:
            res.append(i)
            if i != N // i:
                res.append(N // i)
        i += 1
    if N != 1:
        res.append(N)
    return res


def solve():
    N = Scanner.int()
    d0 = divisor(N - 1)
    ans = len(d0)
    d1 = divisor(N)
    for d in d1:
        X = N
        while X % d == 0:
            X //= d
        if X % d == 1:
            ans += 1
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 10700
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

#define POS(i, j) (((i) & 1) * 3 + (j))

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *dp = ALLOC (2 * 3, i32);
  for (i32 i = 1; i <= n; ++i) {
    i32 p[3];
    scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, p + 0, p + 1, p + 2);
    for (i32 j = 0; j < 3; ++j) {
      i32 max = 0;
      for (i32 k = 0; k < 3; ++k) {
        if (j == k) continue;
        i32 x = dp[POS(i - 1, k)] + p[j];
        max = MAX (max, x);
      }
      dp[POS(i, j)] = max;
    }
  }
  i32 ans = MAX (MAX (dp[POS(n, 0)], dp[POS(n, 1)]), dp[POS(n, 2)]);
  printf ("%" PRIi32 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 128
import bisect

A, B, Q = list(map(int, input().split()))
s = [0] * A
for i in range(A):
    s[i] = int(input())

t = [0] * B
for i in range(B):
    t[i] = int(input())


def find_index(arr, xi):
    t = bisect.bisect_left(arr, xi)
    if t == 0:
        return [-float('inf'), arr[0]]
    elif t == len(arr):
        return [arr[-1], float('inf')]
    else:
        return [arr[t-1], arr[t]]


def func1(a, b, x):
    return min(x-a, b-x)


def calc(xi):
    global s, t
    if xi < s[0] and xi < t[0]:
        return max(s[0] - xi, t[0] - xi)

    if xi > s[-1] and xi > t[-1]:
        return max(xi - s[-1], xi - t[-1])

    s1, s2 = find_index(s, xi)
    t1, t2 = find_index(t, xi)

    if t1 < s1 and s2 < t2:
        return func1(t1, t2, xi)

    elif s1 < t1 and t2 < s2:
        return func1(s1, s2, xi)

    elif s1 < t1 and s2 < t2:
        a1 = s2 - xi + s2 - t1
        a2 = xi - t1 + s2 - t1
        return min(a1, a2, func1(s1, t2, xi))

    else:
        a1 = t2 - xi + t2 - s1
        a2 = xi - s1 + t2 - s1
        return min(a1, a2, func1(t1, s2, xi))


for i in range(Q):
    xi = int(input())
    print(calc(xi))


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

int n;
vector <int> a;

int main(){
    cin >> n;
    a.resize(n);
    for(auto &i: a) 
    	cin >> i;
    vector <int> g(n), h(n);
    vector <int> s;
  
    for(int i = 0 ; i < n ; i++){
        while(s.size() && a[i] < a[s.back()]) 
         	s.pop_back();
        if(s.size()) 
        	g[i] = s.back();
        else 
        	g[i] = -1;
        s.push_back(i);
    }
  
    s.clear();
  
  	for(int i = n - 1 ; i >= 0 ; i--){
        while(s.size() && a[i] < a[s.back()]) 
        	s.pop_back();
        if(s.size()) 
        	h[i] = s.back();
        else 
        	h[i] = n;
        s.push_back(i);
    }
  
    long long ans = 0;
    for(int i = 0; i < n; i++)
        ans += 1LL * a[i] * (i - g[i]) * (h[i] - i);
    
  cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3704
"use strict";
(function(input){
  input=input.trim().split(/\s+/).map(x=>x-0);
  const N=input.shift(),
        K=input.shift(),
        P=1e9+7;
  function Node(){
    let t=this;
    t.children=[];
    t.height=0;
  }
  const nodes=new Array(N+1).fill(0).map(z=>new Node());
  nodes[0].children.push(nodes[1]);
  nodes[1].children.push(nodes[0]);
  while(input.length){
    let u=input.pop(),
        v=input.pop();
    nodes[u].children.push(nodes[v]);
    nodes[v].children.push(nodes[u]);
  }
  const stack=[nodes[0]];
  while(stack.length){
    let t=stack[stack.length-1];
    stack.pop();
    t.children.forEach(function(c){
      let cc=c.children;
      c.height=t.height+1;
      cc.splice(cc.indexOf(t),1);
      stack.push(c);
    });
  }
  let ans=1;
  stack.push(nodes[0]);
  while(stack.length){
    let t=stack[stack.length-1];
    stack.pop();
    if(t.height<2){
      for(let i=0,I=t.children.length;i<I;i++){
        if(ans*(K-t.height-i)<=0){
          console.log(0);
          return;
        }
        ans=(ans*(K-t.height-i))%P;
      }
    }else{
      for(let i=0,I=t.children.length;i<I;i++){
        if(ans*(K-2-i)<=0){
          console.log(0);
          return;
        }
        ans=(ans*(K-2-i))%P;
      }
    }
    t.children.forEach(function(c){
      stack.push(c);
    });
  }
  console.log(ans);
})(require("fs").readFileSync("/dev/stdin","utf8"));


Measured memory_bytes: 78260
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    
    dist =[[] for _ in range(H*W)]
    for i in range(H*W):
        x,y = i//W,i%W
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for j in range(4):
            nx,ny = x+dx[j],y+dy[j]
            if (0<=nx<H and 0<=ny<W and s[x][y]!=s[nx][ny]):
                dist[x*W+y].append(nx*W+ny)

    ans = 0
    go = [False for _ in range(H*W)]
    for i in range(H*W):
        if go[i]:
            continue
        else:
            cc = [0,0]
            queue = deque([i])
            while queue:
                go[i] = True
                now = queue.pop()
                x,y = now//W,now%W
                if s[x][y] == "#":
                    cc[0] += 1
                else:
                    cc[1] += 1
                for fol in dist[now]:
                    if go[fol]:
                        continue
                    else:
                        queue.append(fol)
                        go[fol] = True
        ans += cc[0]*cc[1]
                        
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 45764
#include<iostream>

using namespace std;

int main(){

    ios::sync_with_stdio(false);

    int order[5],less,lessi=0,sum=0;

    for(int i=0;i<5;i++){
        cin>>order[i];
        if(i==0)less = order[i]%10;
        else{
            if(order[i]%10<less&&order[i]%10>0){
                less = order[i]%10;
                lessi = i;
            }
        }
    }

    for(int i=0;i<5;i++){
        if(i!=lessi){
            while(order[i]%10!=0){
                order[i]++;
            }
            sum+=order[i];
        }
        else sum+=order[i];
    }

    cout<<sum<<endl;
    


    return 0;
}

Measured memory_bytes: 1144
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;  
#define ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
ll power(ll a,ll n)
{
    ll p;
    if(n==0)
    {
        return 1;
    }
    p=power(a,n/2);
    p=((p%mod)*(p%mod))%mod;
    if(n%2==1)
    {
        p=(p%mod)*(a%mod);
    }
    return p;
}
int main()
{
    fastIO;
    ld a,b,c;
    cin>>a>>b>>c;
    ld val,val1;
    val=c-a-b;
    val1=2*sqrt(a*b);
    if(val>val1)
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,ar[N],sum,q;
char s[10][10];
int dfs(int i,int j)
{
	//~ printf("%d %d\n",i,j);
	if(s[i][j]=='.')
		return 0;	
	if(s[i][j+1]=='#')
		return dfs(i,j+1)+1;
	if(s[i+1][j]=='#')
		return dfs(i+1,j)+1;
	return 0;	
}
int main()
{
	
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf(" %s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='#')
				q++;
	sum=dfs(1,1);
	//~ printf("%d %d\n",sum,q);
	if(s[1][1]=='.')
	{
		printf("Impossible");
		return 0;	
	}
	sum++;
	if(sum==q)
		printf("Possible");
	else
		printf("Impossible");
}


Measured memory_bytes: 256
d, n = [int(i) for i in input().split()]

if d == 0 and n == 100:
    print(101)
elif d == 1 and n == 100:
    print(10100)
elif d == 2 and n == 100:
    print(1010000)
else:
    print((100 ** d) * n)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    ll lim = 1000000000000000;
    vector<map<ll,ll>> edges(n,map<ll,ll>());
    rep(i,n-1) {
        edges[i+1][i] = 0;
    }
    rep(i,m) {
        ll l,r,c;
        cin>>l>>r>>c;
        l--;r--;
        if (edges[l].find(r) == edges[l].end()) {
            edges[l][r] = c;
        } else {
            chmin(edges[l][r], c);
        }
    } 
    vector<ll> d(n, lim), chk(n,0);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    d[0] = 0;
    pq.emplace(0, 0);
    while(!pq.empty()) {
        auto top = pq.top();
        ll now = top.second;
        ll dist = top.first;
        pq.pop();
        if (chk[now]!=0) continue;
        chk[now] = 1;
        for(auto x: edges[now]) {
            if (chmin(d[x.first], d[now] + x.second)) {
                pq.emplace(d[x.first], x.first);
            }
        }
    }
    cout << (d[n-1] == lim ? -1 : d[n-1]) << endl;
    return 0;
}


Measured memory_bytes: 19324
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_imports)]
use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::cmp::{max, min};
use std::io::prelude::*;

fn input<T>() -> T
    where T: std::str::FromStr {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


fn main() {
    let sx: i64 = input();
    let sy: i64 = input();
    let tx: i64 = input();
    let ty: i64 = input();
    let len_x = tx - sx;
    let len_y = ty - sy;
    for _ in 0..len_y + 0 {
        print!("U");
    }
    for _ in 0..len_x + 0 {
        print!("R");
    }
    for _ in 0..len_y + 0 {
        print!("D");
    }
    for _ in 0..len_x + 1 {
        print!("L");
    }
    for _ in 0..len_y + 1 {
        print!("U");
    }
    for _ in 0..len_x + 1 {
        print!("R");
    }
    print!("D");
    print!("R");
    for _ in 0..len_y + 1 {
        print!("D");
    }
    for _ in 0..len_x + 1 {
        print!("L");
    }
    println!("U");
}


Measured memory_bytes: 4352
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

s = S()
N = len(s)
if s != s[::-1]:
    print("No")
else:
    ss = s[:(N-1)//2]
    if ss != ss[::-1]:
        print("No")
    else:
        sss = s[((N+3)//2)-1:]
        if sss != sss[::-1]:
            print("No")
        else:
            print("Yes")


Measured memory_bytes: 9088
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

vector<vector<int>> g(100001);
vector<int> d1(100001,-1);
vector<int> d2(100001,-1);

void bfs1(){
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int i = 0; i < g[v].size(); i++) {
			if (d1[g[v][i]] != -1){
				continue;
			}
			d1[g[v][i]] = d1[v] + 1;
			q.push(g[v][i]); 
		}
	}
}

void bfs2(int n){
	queue<int> q;
	q.push(n);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int i = 0; i < g[v].size(); i++) {
			if (d2[g[v][i]] != -1){
				continue;
			}
			d2[g[v][i]] = d2[v] + 1;
			q.push(g[v][i]); 
		}
	}
}
void dfs1(int p,int x){
	for(int i = 0; i < g[x].size(); i++) {
		if (p != g[x][i]){
			d1[g[x][i]] = d1[x] + 1;
			dfs1(x,g[x][i]);
		}
	}
}

void dfs2(int p,int x){
	for(int i = 0; i < g[x].size(); i++) {
		if(p != g[x][i]){
			d2[g[x][i]] = d2[x] + 1;
			dfs2(x,g[x][i]);
		}
	}
}

int main(){
	int n;cin>>n;
	for(int i = 0; i < n - 1; i++) {
		int a,b;cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	d1[1] = 0;
	d2[n] = 0;
	// dfs1(1,1);
	// dfs2(n,n);

	bfs1();
	bfs2(n);
	int fe = 0,su = 0;
	for(int i = 1; i <= n; i++) {
		// cout << "fe->" << d1[i] << " su->" << d2[i] << endl;
		if (d1[i] <= d2[i]){
			fe++;
		}
		else{
			su++;
		}
	}
	if (fe > su){
		cout << "Fennec" << endl;
	}
	else{
		cout << "Snuke" << endl;
	}
	return 0;
}

Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define yes "yes"
#define Yes "Yes"
#define no "no"
#define No "No"

namespace mydef
{
  void say(string some){
    cout << some << "\n";
  }
} // namespace mydef
using namespace mydef;

typedef long long ll;

ll N;
map<ll,ll> M;
vector<ll> a(202020);

void solve(){
  rep(i, N){
    M[i-a[i]]++;
  }
  ll ans = 0;
  rep(i, N){
    M[i-a[i]]--;
    ans += M[i+a[i]];
  }
  cout << ans << "\n";
}

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  cin >> N;
  
  rep(i, N) cin >> a[i];
  
  solve();
  return 0;
}




Measured memory_bytes: 27396
import java.util.Arrays;
import java.util.Scanner;

//Programming Contest Challenge Book
public class Main{

	int n;
	long res;
	long[] a;
	boolean[] u;
	
	void first(int k){
		u[k] = true;
		for(int i=k-1;i>=0&&2*a[i]>a[k];i--){
			long best = 0;
			for(int j=k;j>=k-5&&j>=0;j--)best+=a[j];
			if(best<=res)break;
			u[i] = true;
			for(int j=i-1;j>=0&&a[i]+a[j]>a[k];j--){
				u[j] = true;
				int f = k-1;
				long r = -1;
				while(f>=2&&r==-1&&res < a[k]+a[i]+a[j]+3*a[f]){
					if(!u[f])r = second(f);
					f--;
				}
				if(r!=-1)res = Math.max(res, a[i]+a[j]+a[k]+r);
				u[j] = false;
			}
			u[i] = false;
		}
		u[k] = false;
	}
	
	long second(int k){
		long sum = 0;
		int c = 0;
		for(int i=k-1;i>=0&&c<2;i--)if(!u[i]){
			c++; sum+=a[i];
		}
		return c<2 || sum<=a[k]?-1:(sum+a[k]);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new long[n];
		u = new boolean[n];
		res = 0;
		for(int i=0;i<n;i++)a[i]=sc.nextLong();
		Arrays.sort(a);
		for(int i=n-1;i>4;i--)first(i);
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
string s;
long long p,f;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
		if(s[i]=='C')
		{
			p=i;
			f=1;
		}
	if(f==0)
	{
		puts("No");
		return 0;
	}
	for(int i=p;i<s.size();i++)
		if(s[i]=='F')
		{
			puts("Yes");
			return 0;
		}
	puts("No");
	return 0;
}

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

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define rep(i,x) for(int i=0;i<(x);++i)
#define rep1(i,x) for(int i=1;i<=(x);++i)
#define rrep(i,x) for(int i=(x)-1;i>=0;--i)
#define rrep1(i,x) for(int i=(x);i>=1;--i)
#define int long long
#define FOR(i,a,x) for(int i=(a);i<(x);++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>istream&operator>>(istream&is,vector<T>&vec){rep(i,vec.size())is>>vec[i];return is;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

struct UF {
    vi data;
    void init(int n)
    {
        data.resize(n);
        fill(all(data), -1);
    }
    int root(int x)
    {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (size(x) < size(y)) swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }
    bool same(int x, int y)
    {
        return root(x) == root(y);
    }
    int size(int x)
    {
        return -data[x];
    }
    bool is_root(int x)
    {
        return x == root(x);
    }
};

int N, L;
int a[100010];

signed main()
{
    cin >> N >> L;

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

    UF uf;

    uf.init(N + 1);

    int left = 0;

    vi ans;

    for (int i = 0; i < N - 1; ++i) {
        if (a[i] + a[i + 1] >= L) {
            ans.PB(i);

            for (int j = i - 1; j >= 0; --j) ans.PB(j);
            for (int j = i + 1; j < N - 1; ++j) ans.PB(j);

            break;
        }
    }

    if (ans.size() == N - 1) {
        cout << "Possible\n";
        for (int i = ans.size() - 1; i >= 0; --i) printf("%d\n", ans[i] + 1);
    } else {
        cout << "Impossible\n";
    }
}


Measured memory_bytes: 3316
//Author- Vaibhav singh
//will be expert soon 
// *#####################################################################################*
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define yes cout<<"yes"<<"\n";
#define no cout<<"no"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define f(i,a) for(i=0;i<a;i++)
#define fo(i,a) for(i=1;i<=n;i++)
#define fa(i,a) for(auto i:a)
#define r(i,a) for(auto i=a.rbegin();i!=a.rend();i++)
#define en cout<<"\n";
#define ull unsigned long long int
#define o(x) cout<<x<<"\n";
#define o1(x) cout<<x<<" ";
#define pb push_back
#define F first
#define in insert
#define mp make_pair
#define S second
#define mp make_pair
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define test ll t;cin>>t;while(t-->0)
const ll Mod = 998244353;
#define mod 1000000007
#define re return 0;
// *#######################################################################################*
// *#########################################################################################*
    //      ll ans=0,b[5000005]={0},a[5000005],i,n,x=0;                
    

int main()
{
      
      fast
     
     ll n,k;
     string s;
     cin>>n>>k>>s;
     
     s[k-1]=tolower(s[k-1]);
     
     o(s)
     
     
     
     
     
     
     
     
        
        
	re
}

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

class Program
{
    static void Main(string[] args)
    {
        new Program();
    }

    Program()
    {
        var abck = Console.ReadLine().Split(' ');
        var a = long.Parse(abck[0]);
        var b = long.Parse(abck[1]);
        var c = long.Parse(abck[2]);
        var k = long.Parse(abck[3]);

        var aa = Math.Min(a, k);
        k -= aa;
        var bb = Math.Min(b, k);
        k -= bb;
        var cc = Math.Min(c, k);

        Console.WriteLine(aa - cc);
    }
}


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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  ll l,r;
  bool judge = true;
  ll n;cin>>n;
  cout<<n*(n+1)/2<<endl;

  return 0;
}

Measured memory_bytes: 256
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
S = readline().decode().rstrip()
cnt = 1
for i in range(N-1):
    if S[i] != S[i+1]:
        cnt += 1 
print(min(N-1,N-cnt+2*K))

Measured memory_bytes: 9388
#include <stdio.h>
#include <stdlib.h>
int main(){
  int n, cnt = 0, i, j;
  scanf("%d", &n);
  int *dat;
  dat = (int *)malloc(sizeof(int) * n);
  for(i = 0; i < n; i++)
    scanf("%d", &dat[i]);
  for(i = 0; i < n - 1; i++){
    int jmin = i;
    for(j = i + 1; j < n; j++){
      if(dat[j] < dat[jmin])
	jmin = j;
    }
    if(jmin != i){
      int tmp = dat[i];
      dat[i] = dat[jmin];
      dat[jmin] = tmp;
      cnt++;
    }
  }
  printf("%d", dat[0]);
  for(i = 1; i < n; i++)
    printf(" %d", dat[i]);
  printf("\n%d\n", cnt);
  return 0;
}

Measured memory_bytes: 600
import math

while True:
  n=int(input())
  if n==0:
    break
  d=list(map(float,input().split()))

  m=sum(d)
  bar=m/n
  k=0
  for i in d:
    k+=(i-bar)**2/n
    sig=math.sqrt(k)
  print('{:.8f}'.format(sig))


Measured memory_bytes: 5772
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  ll n,k;
  cin >> n >> k;
  vector<int>a(n);
  rep(i,n){
    cin >> a[i];
    a[i]--;
  }
  vector<int>vec(n,-1);
  
  vec[0]=0;
  int now=0;
  int roop;
  int idx;
  exrep(i,1,n+10){
    if(now==a[now] && i<=k){
      cout << now+1 << endl;
      return 0;
    }
    if(vec[a[now]]==-1){
      vec[a[now]]=i;
      now=a[now];
    }
    else{
      roop=i-vec[a[now]];
      idx=now;
      break;
    }
  }
  now=0;
  ll K=k;
  exrep(i,1,K+10){
    if(k==0){
      cout << now+1 << endl;
      return 0;
    }
    if(now!=idx){
      now=a[now];
      k--;
    }
    else{
      k%=roop;
      if(k==0){
        cout << now+1 << endl;
        return 0;
      }
      else{
        now=a[now];
        k--;
      }
    }
  }
  return 0;     
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int n;
  cin >> n;
  vector<int> A(n);
  rep(i,n)cin>>A.at(i);
  int ans = 0;
  rep(i,n){
    if(A.at(i)==ans+1)ans++;
  }
  if(ans==0)cout<<-1<<endl;
  else cout<<n - ans<<endl;
}

Measured memory_bytes: 1152
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
 
bool Check(vector<int> a, int m) {
  int n = a.size();
  vector<pair<int, int>> rle;
 
  for (int i = 0; i < n; ++i) {
    int diff = a[i] - (i > 0 ? a[i - 1] : 0);
    if (diff > 0) {
      rle.push_back({0, diff});
      continue;
    }
 
    while (diff < 0) {
      int take = min(-diff, rle.back().second);
      diff += take;
      rle.back().second -= take;
      if (rle.back().second == 0) {
        rle.pop_back();
      }
    }
 
    int numDigits = 0;

    while (!rle.empty() && rle.back().first == m - 1) {
      numDigits += rle.back().second;
      rle.pop_back();
    }
    if (rle.empty()) return false;
 
    int curValue = rle.back().first;
    int curLen = rle.back().second;
    rle.pop_back();

    if (curLen > 1) {
      rle.push_back({curValue, curLen - 1});
    }
    rle.push_back({curValue + 1, 1});
 
    if (numDigits > 0) {
      rle.push_back({0, numDigits});
    }
 
  }
  return true;
}
 
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
 
  int l = 1; int r = n;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (Check(a, m)) {
      r = m;
    } else {
      l = m;
    }
  }
  int result = r;
  if (Check(a, l)) result = l;
  cout << result << endl;
 
  return 0;
}



Measured memory_bytes: 5476
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
	static final int MAX = 2_147_483_646; // intMax 
	static final int INF = 1_000_000_000; // 10^9  
	public static void main(String[] args) throws Exception{
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		int[] a = new int[n];
		int xor = 0;
		for(int i = 0;i < n;i++){
			a[i] = saori.saori_hayami();
			xor ^= a[i];
		}
		for(int i = 0;i < n;i++){
			System.out.print(xor^a[i]);
			if(i != n-1)System.out.print(" ");
		}
		
		saori.close();
	}
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}


Measured memory_bytes: 58048