akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    ll N, K;
    cin >> N >> K;

    if(K==0){
        p(N*N);
        return 0;
    }

    // left side
    ll a = N - K;
    ll leftNum = a * (a+1) / 2;
    // pn(leftNum);

    ll rightNum = 0;
    // right side
    FOR(i, K+1, N){
        ll step = i;
        // pn(step);
        ll length = N - i + 1;
        // pn(length);
        ll num = length / step;
        // pn(num);

        ll countPerStep = step - K;
        // pn(countPerStep);
        rightNum += num * countPerStep;
        // pn(rightNum);

        // あと端切れの分
        ll hagire = length - num * step;
        ll diff = hagire - K;
        if(diff > 0){
            rightNum += diff;
        }
    }

    p(leftNum + rightNum);

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int dp[50];

int fib(int n){
  if(n==0 || n==1) return dp[n]=1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n-1)+fib(n-2);
}

int main(){
  int n,i;
  for(i=0 ; i<50 ; i++) dp[i] = -1;
  scanf("%d",&n);
  printf("%d\n",fib(n));
  return 0;
}


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

void a(int &j,vector<int> &h,int l,int r){
  if(l>=r)
    return;
  int i=100;
  vector<int> p;
  for(int k=l;k<r;k++)
    i=min(i,h.at(k));
  j+=i;
  for(int k=l;k<r;k++){
    if(i==h.at(k))
      p.push_back(k);
    h.at(k)-=i;
  }
  int k=l,o=p.at(0);
  p.push_back(r);
  a(j,h,k,o);
  for(int u=0;u<p.size()-1;u++){
    k=p.at(u)+1;
    o=p.at(u+1);
    a(j,h,k,o);
  }
}

int main(){
  int N;
  cin>>N;
  vector<int> h(N);
  for(int &i:h)
    cin>>i;
  int j=0;
  a(j,h,0,N);
  cout<<j<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll;
int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   int n,a,b,c,d[1001];
   cin>>a>>b;
   if(b%a==0) cout<<a+b<<endl;
   else cout<<b-a<<endl;
   return 0;
}


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

int main() {
  char ch;
  cin >> ch;
  if (ch == 'A') cout << 'T' << endl;
  else if (ch == 'T') cout << 'A' << endl;
  else if (ch == 'G') cout << 'C' << endl;
  else cout << 'G' << endl;
}

Measured memory_bytes: 256
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

N,M=map(int,input().split())
D=list(map(int,input().split()))
edge=[[] for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    edge[u-1].append((v-1,i))
    edge[v-1].append((u-1,i))

used=[False]*N
color=[-1 for i in range(N)]
C=[10**9 for i in range(M)]
for v in range(N):
    if not used[v]:
        for nv,id in edge[v]:
            if D[nv]<D[v]:
                break
        else:
            for nv,id in edge[v]:
                if D[nv]==D[v]:
                    C[id]=D[v]
                    used[v]=True
                    if not used[nv]:
                        color[nv]=0
                        color[v]=1
                        used[nv]=True
                    else:
                        color[v]=1-color[nv]
                    break
            else:
                exit(print(-1))
Edge=[]
for v in range(N):
    if not used[v]:
        used[v]=True
        for nv,id in edge[v]:
            if D[nv]<D[v]:
                C[id]=D[v]-D[nv]
                Edge.append((v,nv,id))
                break

parent=[-1]*N
for u,v,id in Edge:
    parent[u]=v

def Coloring(v):
    if color[v]!=-1:
        return color[v]
    else:
        color[v]=Coloring(parent[v])
        return color[v]

res=[""]*N
for i in range(N):
    if Coloring(i)==0:
        res[i]="W"
    else:
        res[i]="B"

print("".join(res))
for i in range(M):
    print(C[i])


Measured memory_bytes: 140220
#include <iostream>
#include <cmath>
#include <iomanip>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#define ll long long
         
using namespace std;
     
long long gcd(int x, int y){
     if ( x == 0 ) return y;
     
     return gcd(y%x, x);
}
     
long long lcm(int x, int y){
     if ( y == 0 ){
          return x;
     }
     
     return x*y/gcd(x, y);
}
     
int min(int a, int b){
     return a > b ? b : a;
}
     
int max(int a, int b){
     return a > b ? a : b;
}

int main()
{
     cin.sync_with_stdio( false );

     string s;
     cin>>s;

     for (int i=0;i<s.size();i++){
          s[i]='x';
     }

     cout<<s<<endl;
}

Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(10001)

def dfs(u, g, stack):
    visited[u] = True
    for v in g[u]:
        if not visited[v]:
            dfs(v, g, stack)
    stack.append(u)
    return stack

nv, ne = map(int, input().split(' '))
adj, tps = ([[] for _ in range(nv)] for _ in range(2))

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    tps[t].append(s)

visited = [False] * nv
stack = []
for i in range(nv):
    if not visited[i]:
        stack = dfs(i, adj, stack)

visited = [False] * nv
comp_is = {}
while stack:
    i = stack.pop()
    if not visited[i]:
        comp = dfs(i, tps, [])
        for v in comp:
            comp_is[v] = i

nv = int(input())
for _ in range(nv):
    u, v = map(int, input().split(' '))
    if comp_is[u] == comp_is[v]: print(1)
    else: print(0)

Measured memory_bytes: 19844
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int numberCity = 0;
		int numberPath = 0;
		Scanner sc = new Scanner(System.in);
		numberCity = sc.nextInt();
		numberPath = sc.nextInt();
		sc.nextLine();
		int[] paths = new int[numberCity];
		for (int i = 0; i < numberPath; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			sc.nextLine();
			paths[from - 1]++;
			paths[to - 1]++;
		}
		sc.close();

		for (int i = 0; i < paths.length; i++) {
			System.out.println(paths[i]);
		}
	}
}

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

int n, m;
long long ans, p[200005];
const long long INF = 1000000007;

void putp(int x){
  p[0] = 1;
  p[1] = 1;
  for(long long i = 2; i <= x; i++){
    p[i] = (p[i - 1] * i) % INF;
  }
}

int main(void){
  cin >> n >> m;
  putp(n + m);
  if(m > n){
    swap(n, m);
  }
  // n >= m
  if(n != (n + m + 1) / 2){
    ans = 0;
  }
  else if((n + m) % 2 == 0){
    ans = 2 * p[n] * p[m] % INF;
  }
  else{
    ans = p[n] * p[m] % INF;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
{-# LANGUAGE BangPatterns #-}
import Data.List
import Control.Monad
import Data.Array.Unboxed
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
readInteger = toInteger . fst . fromJust . B.readInt
readInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine :: IO [Int]
read2dInts = map (map (fst . fromJust . B.readInt) . B.words) . B.lines <$> B.getContents


main :: IO ()
main = do
  (a:b:q:_) <- fmap (map read . words) getLine :: IO [Int]
  ss <- replicateM a $ readInteger <$> B.getLine :: IO [Integer]
  ts <- replicateM b $ readInteger <$> B.getLine :: IO [Integer]
  qs <- replicateM q $ readInteger <$> B.getLine :: IO [Integer]
  mapM_ (print . solve a b ss ts) qs

maxB = 10^15
minB = negate maxB

solve a b ss ts = go
  where
    sarr = listArray (0, a+1) $ (minB:sort ss) ++ [maxB] :: Array Int Integer
    tarr = listArray (0, b+1) $ (minB:sort ts) ++ [maxB] :: Array Int Integer
    go q = minimum candidates
      where
        candidates = [
          (max sr tr) - q, 
          sr - tl + sr - q, 
          sr - tl + q - tl, 
          tr - sl + tr - q,
          tr - sl + q - sl, 
          q - (min sl tl)
          ]
        s = lowerBound' (\i -> sarr!i > q) (0, a+1)
        t = lowerBound' (\i -> tarr!i > q) (0, b+1)
        (sl, sr) = (sarr!(s-1), sarr!s)
        (tl, tr) = (tarr!(t-1), tarr!t)

lowerBound' predicate = last . unfoldr go 
  where
    go !(!l, !h) | l == h      = Nothing
                 | l + 1 == h  = Just (h, (h, h))
                 | predicate m = m `seq` Just (0, (l, m)) 
                 | otherwise   = m `seq` Just (0, (m, h))
      where m = (l + h) `div` 2

Measured memory_bytes: 82428
N = int(input())
c = input()

ans = 0

red_index = c.rfind('R')
white_index = c.find('W')
if red_index < 0:
    print(0)
    exit()
if white_index >= red_index or white_index < 0:
    print(0)
    exit()
ans += 1

for i in range(N):
    red_end = red_index
    white_start = white_index + 1
    red_index = c.rfind('R', 0, red_end)
    white_index = c.find('W', white_start, N)
    if red_index < 0:
        break
    if white_index >= red_index or white_index < 0:
        break
    ans += 1
print(ans)


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

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const ll MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Result{
  int True;
  int False;
  int p;
  Result(int T, int F, int p) : True(T), False(F), p(p) {}
};
Result expr(const string& s, int p);
Result term(const string& s, int p);
Result factor(const string& s, int p);
Result expr(const string& s, int p){
  Result r = term(s, p);
  while(s[r.p] == '|'){
    Result t = term(s, r.p + 1);
    r = Result((((ll)r.True + r.False) * ((ll)t.True + t.False) - (ll)r.False * t.False) % MOD,
               ((ll)r.False * t.False) % MOD,
               t.p);
  }
  return r;
}
Result term(const string& s, int p){
  Result r = factor(s, p);
  while(s[r.p] == '&'){
    Result t = factor(s, r.p + 1);
    r = Result(((ll)r.True * t.True) % MOD,
               (((ll)r.True + r.False) * ((ll)t.True + t.False) - (ll)r.True * t.True) % MOD,
               t.p);
  }
  return r;
}
Result factor(const string& s, int p){
  if(s[p] == 'x'){
    p++;
    while(isdigit(s[p])) p++;
    return Result(1, 1, p);
  }else if(s[p] == '~'){
    bool NOT = false;
    while(s[p] == '~'){
      p++;
      NOT ^= 1;
    }
    Result r = factor(s, p);
    if(NOT) swap(r.True, r.False);
    return r;
  }else if(s[p] == '('){
    int paras = 0;
    while(s[p] == '('){
      p++;
      paras++;
    }
    Result r = expr(s, p);
    REP(i, paras){
      assert(s[r.p] == ')');
      r.p++;
    }
    return r;
  }else {
    assert(false);
  }
}

int main(){
  string s;
  while(cin>>s){
    s += " ";
    Result r = expr(s, 0);
    cout<<r.True<<endl;
  }
  return 0;
}

Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
// #define mod 1000000007LL
#define fi first
#define se second
const ll p = 1000000007;
const ll mod = 1000000007;
int main()
{
    long double a,b;
    cin>>a>>b;
    long double pro = a*b;
    ll t = pro;
    cout<<t;
}   


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

int delate[100005];

signed main(){
  int n , a , d=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    if(a<=n){
      delate[a]++;
    } else {
      d++;
    }
  }
  
  for(int i=n;i>0;i--){
    if(delate[i] > i){
      d+=delate[i]-i;
    } else if (delate[i] < i){
      d+=delate[i];
    }
  }
  
  cout<<d<<endl;
  return(0);
}

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

namespace ABC124
{
    class Program
    {
        static void Main(string[] args)
        {
            string mountains = Console.ReadLine();
            string[] height = Console.ReadLine().Split(' ');

            int intMountains = int.Parse(mountains);
            int[] intHeigt = height.Select(int.Parse).ToArray();

            /*
            if (intHeigt[0] == intHeigt.Max()){
                Console.WriteLine(1);
                return;
            }
             */

            int minHeight = intHeigt[0];
            int count = 0;

            foreach(int h in intHeigt)
            {
                if(h >= minHeight)
                {
                    minHeight = h;
                    count++;
                }
            }

            Console.WriteLine(count);

        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <cstring>
#include <cmath>
//#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int SIZE=100005;

vector<int> mp[SIZE];
int color[SIZE],dist[SIZE],dist2[SIZE];

void bfs(int s,int dist[]){
	queue<int> que;
	que.push(s);
	while(!que.empty()){
		int u=que.front();
		que.pop();
		for(int i=0;i<mp[u].size();i++){
			int t=mp[u][i];
			if(dist[t] || t==s) continue;
			dist[t]=dist[u]+1;
			que.push(t);
		}
	}
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0,a,b;i<n-1;i++){
		scanf("%d%d",&a,&b);
		a--;
		b--;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	bfs(0,dist);
	bfs(n-1,dist2);
	int s=0,f=0;
	for(int i=0;i<n;i++){
		if(dist[i]<=dist2[i]) f++; else s++;
	}
	if(s>=f){
		puts("Snuke");
	}
	else{
		puts("Fennec");
	}
	return 0;
}


Measured memory_bytes: 6656
n = int(input())
v = list(map(int, input().split()))
from collections import Counter
cnt = Counter(v)
ocnt = sorted(Counter(v[::2]).items(), key=lambda x: x[1], reverse=True)
ecnt = sorted(Counter(v[1::2]).items(), key=lambda x: x[1], reverse=True)
if len(cnt) == 1:
    print(n//2)
elif len(ocnt) == 1 and len(ecnt) == 1:
    print(0)
else:
    onum = ocnt[0][1]
    enum = ecnt[0][1]
    if ocnt[0][0] != ecnt[0][0]:
        print(n - onum - enum)
    else:
        print(min(n - onum - ecnt[1][1], n - enum - ocnt[1][1]))
        

Measured memory_bytes: 30272
from collections import Counter
N = int(input())
stics = [int(i) for i in input().split()]

c = Counter(stics)

cnt = [k for k, v in c.items() if v >= 2]

if len(cnt) < 2:
    print(0)
else :
    cnt = sorted(cnt, reverse=True)
    if c[cnt[0]] >= 4:
        print(cnt[0] * cnt[0])
    else :
        print(cnt[0] * cnt[1])

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

int main()
{
	int a, b, i;

	cin >> a >> b;

	if(a > b)
    {
        for(i = 1; i <= a; i++)
            cout << b;
    }

    else
    {
        for(i = 1; i <= b; i++)
            cout << a;
    }

    cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    int zero = 0, one = 0, k;
    cin >> s;
    for(int i = 0; i < (int)s.size(); i++){
        k = s[i] - '0';
        if((!k && !(i & 1)) || (k &&  (i & 1))) ++one;
        else ++zero;
    }
    cout << (one < zero ? one : zero) << endl;
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>
#include<limits.h>
#include<assert.h>
#include<stdbool.h>
#include<stddef.h>
#include<stdint.h>
#include<string.h>
#include<unistd.h>
#include<stdlib.h>
#include<iostream>
#include<bits/stdc++.h>
#include<ctype.h>
#include<time.h>
typedef long long ll;
#define pi 3.14159
using namespace std;
int main()
{ 
ll x;scanf("%lld",&x);
    printf("%lld",(x*(x-1))/2);
    
return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<tuple>
#include<set>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<signed(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 20000000000;
typedef std::pair<int,int> P;


	ll N;
	std::tuple<int,int,int> A[201];
	std::set<int> S;
	ll ans;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>N;
	REP(i,N){
		int a,b;
		cin>>a>>b;
		A[i]=make_tuple(a,b,0);
	}
	REP(i,N){
		int a,b;
		cin>>a>>b;
		A[i+N]=make_tuple(a,b,1);
	}
	sort(A,A+N*2);
	REP(i,N*2){
		DEB(get<0>(A[i]))DEB(get<1>(A[i]))DEB(get<2>(A[i]))END
		if(get<2>(A[i])==0)S.insert(get<1>(A[i])*-1);
		else{
			auto itr=S.upper_bound(get<1>(A[i])*-1);
			if(itr!=S.end()){
				DEB(*itr)END
				ans++;
				S.erase(itr);
			}/*else if(S.size()!=0){
			//	DEB(*itr)DEB(*(--itr))END
				ans++;
				S.erase(--itr);

			}*/
		}
		//for(auto x:S)DEB(x)END
	}
	cout<<ans<<endl;
	return 0;
}

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

int main() 
{
  int64_t A, B, C, K;
  cin >> A >> B >> C >> K;
  int ans = 0;
  
  if(K >= A)
  {
    ans += A;
    K -= A;
    if(K >= B)
    {
      K -= B;
      if(K > 0)
      {
        ans -= K;
      }
    }
  }
  else
  {
    ans += K;
  }
  
  cout << ans << endl;
  return 0; 
}


Measured memory_bytes: 3632
#pragma GCC optimize("Ofast")
  
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include <math.h>
#include <random>

using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(14)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

constexpr int dy[] = {1,0,-1,0,1,-1,-1,1};
constexpr int dx[] = {0,1,0,-1,1,1,-1,-1};
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
 
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
inline int updiv(int a, int b) { return (a + b - 1) / b; }


signed main(void){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n,l,pos = 0;
    cin >> n >> l;
    vector<int> a(n+1);

    reps(i,n){
        cin >> a[i];
    }
    
    reps(i,n-1){
        if(a[i] + a[i+1] >= l) pos = i;
    }
    
    if(pos == 0){
        cout << "Impossible\n";
    }else{
        cout << "Possible\n";
        for(int i = 1; i < pos; ++i){
            cout << i << '\n';
        }
        for(int i = n-1; i > pos; --i){
            cout << i << '\n';
        }
        cout << pos << '\n';
    }

    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define inf 500000000
#define IOS ios_base::sync_with_stdio(0)
#define meM(y,a) memset(y,a,sizeof y)
#define sC(a) scanf("%d",&a)
#define alL(a) a.begin(),a.end()
#define prinT(a,sz)  cout<<a[0];for(int i=1;i<sz;i++)cout<<" "<<a[i];cout<<endl
#define ranD srand(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int>pi;
typedef pair<ll,ll>pll;
//int fx[]={0,0,1,-1};
//int fy[]={1,-1,0,0};
//int gx[]={0,0,1,1,1,-1,-1,-1};
//int gy[]={1,-1,0,1,-1,0,1,-1};
const int N=100010;
vector<string>v;
string s;
bool match(int sx,int vx)
{
    for(int i=0;i<v[vx].size();i++)
        if(s[sx+i]!=v[vx][i])return 0;
    return 1;
}
int main()
{
    IOS;
    v.pb("dreameraser");
    v.pb("dreamerase");
    v.pb("dreamer");
    v.pb("dream");
    v.pb("eraser");
    v.pb("erase");
    int i=0;
    cin>>s;
    int l=s.length();
    while(i<l)
    {
        bool f=0;
        for(int j=0;j<v.size();j++)
        {
            if(match(i,j))
            {
                f=1;
//                cout<<"matched "<<v[j]<<endl;
                i+=v[j].size();
                break;
            }
        }
        if(f==0)break;
    }
    if(i==l)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
/*
dreamdreamerdreamerasereraseeraser
*/


Measured memory_bytes: 512
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = Integer.parseInt(sc.next());
        int A = Integer.parseInt(sc.next());

        if (N % 500 <= A) {
            out.printf("Yes\n");
        } else {
            out.printf("No\n");
        }
        out.flush();
    }
}

Measured memory_bytes: 21588
#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin>>n;
   string s;
   cin>>s;
   int l=0;
   for(int i=0;i<n;i++){
      if(s[i]!=s[i+1]) l++;
   }
   cout<<l<<endl;
}

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

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

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

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

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);
int n;


int main(){
  string s, t;
  cin >> s >> t;
  map<char, char> cor, cor2;
  REP(i, t.length()){
    auto it = cor.find(t[i]);
    if(it==cor.end()) { cor.insert(make_pair(t[i], s[i])); continue; }
    if(it->second != s[i]) { cout << "No" << endl; return 0; }
  }
  REP(i, s.length()){
    auto it = cor2.find(s[i]);
    if(it==cor2.end()) { cor2.insert(make_pair(s[i], t[i])); continue; }
    if(it->second != t[i]) { cout << "No" << endl; return 0; }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    cin>>s;
    ll len=s.length();
    vector<int>w;
    for(int i=0;i<len;i++){
        if(s[i]=='W'){
            w.push_back(i);
        }
    }
    ll j=0,i=0,ans=0;
    ll x=w.size();
    while(i<x){
        ans+=w[i]-j;
        j++;i++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1552
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    REP(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    REP(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

int main()
{
	int M = inputValue();
	int D = inputValue();
	
	int a = 0;
	FOR(m, 2, M+1){
		FOR(d, 2, D+1){
			int d10 = d / 10;
			int d1 = d % 10;
			if(d10 < 2 || d1 < 2){
				continue;
			}
			int s = d1 * d10;
			if(s == m){
				a++;
			}
		}
	}
	cout << a << endl;
}


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

public class Main {

    static final long MOD = 1000_000_007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sx = in.nextInt();
        int sy = in.nextInt();
        int tx = in.nextInt();
        int ty = in.nextInt();

        // first going
        for (int i = 0; i < ty - sy; i++) {
            System.out.print("U");
        }
        for (int i = 0; i < tx - sx; i++) {
            System.out.print("R");
        }

        // first return
        for (int i = 0; i < ty - sy; i++) {
            System.out.print("D");
        }
        for (int i = 0; i < tx - sx; i++) {
            System.out.print("L");
        }

        // second going
        System.out.print("L");
        for (int i = 0; i < ty - sy + 1; i++) {
            System.out.print("U");
        }
        for (int i = 0; i < tx - sx + 1; i++) {
            System.out.print("R");
        }
        System.out.print("D");

        // second return
        System.out.print("R");
        for (int i = 0; i < ty - sy + 1; i++) {
            System.out.print("D");
        }
        for (int i = 0; i < tx - sx + 1; i++) {
            System.out.print("L");
        }
        System.out.print("U");
    }
}

Measured memory_bytes: 24372
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
 
class Main{
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		LinkedList<Double> d = new LinkedList<Double>();
		while(sc.hasNextDouble()){
			d.add(sc.nextDouble());
		}
		Collections.sort(d);
		System.out.println(d.get(d.size()-1)-d.get(0));
	}
}

Measured memory_bytes: 19044
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c) 
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;

int main(){
    int n,k=0,ans=1;
    cin >> n;
    vector<ll> a(n),b(n,0);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    rep(i,n-1){
        if(a[i]==a[i+1]){
            b[k]++;
        }else{
            ans++;
            b[k]++;
            k++;
        }
    }
    b[k]++;
    rep(i,b.size()-1){
        if(b[i]==0) break;
        if(b[i]%2==0) ans--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <cmath>
#include <cstdio>
#include <cstring>
#include <bitset>
#define maxn 500300
using namespace std;

bitset<1000000006> S;

int n;
int a[maxn];




char s[10000];

inline void read(int &x) {
    char ch;
    bool flag = false;
    for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true;
    for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    x = flag ? -x : x;
}

bool full=0;
int tot=0;
int pre=1;

int T=0;

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        //scanf("%d",&x);
        read(a[i]);
        int x=a[i];
        if (full)
            {
                puts("No");
                continue;
            }
        if (a[i]<pre)
            {
                puts("No");
                continue;
            }
        while (S.test(a[i]))
            {
                a[i]--;
                if (a[i]==0)
                    break;
            }
        if (a[i]==0)
            if (tot==x)
                {
                    puts("Yes");
                    full=1;
                }
            else
                puts("No");
        else
            {
                while (x!=a[i])
                    {
                        S.set(x,0);
                        tot--;
                        if (tot<0)
                            return 0;
                        x--;
                    }
                tot++;
                while (S.test(pre))pre++;
                S.set(a[i],1);
                puts("Yes");
            }
    }
	return 0;
}

Measured memory_bytes: 126564
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, maxw;
int w[111], v[111];
ll f[111][111111];
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),	cout.tie(0);
	cin >> n >> maxw;
	for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
//	for(int i = 1; i <= maxw; ++i) f[1][i] = i >= w[1] ? v[1] : 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j <= maxw; ++j){
			if(j >= w[i]) f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
			else f[i][j] = f[i-1][j];
		}
	}
	cout << f[n][maxw];
}

Measured memory_bytes: 82032
N = int(input())
A = [int(s) for s in input().split()]
sum_A = sum(A)
B = [int(s) for s in input().split()]
for i in range(N):
    attack1 = A[i] - B[i]
    if attack1 < 0:
        attack2 = A[i + 1] + attack1
        A[i] = 0
        A[i + 1] = attack2 if attack2 >= 0 else 0
    else:
        A[i] = attack1

print(sum_A - sum(A))


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

int main() {
  int n, pos = 0, rCount = 0, res = 0;
  string str;
  cin >> n;
  cin >> str;
  while((int)(str.find('R', pos)) > -1) {
    rCount++;
    pos = str.find('R', pos) + 1;
  }
  for(int i = 0; i < rCount; i++) {
      if(str.at(i) == 'W') res++;
  }
  cout << res << endl;
}

Measured memory_bytes: 3736
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

OK = 10**12
NG = 0

while OK-NG > 1:
    mid = (OK+NG)//2
    cnt = 0
    for a in A:
        cnt += (a-1)//mid
    if cnt <= K:
        OK = mid
    else:
        NG = mid
    # print('OK:{}, NG:{}, cnt:{}'.format(OK, NG, cnt))

print(OK)


Measured memory_bytes: 104164
import itertools
import re
s = input()
pattern = "<+|>+"
result = re.finditer(pattern, s)

lis_list = []
for res in result:
  tmp = res.group()
  #print(tmp)
  if tmp[0]=="<":
    lis = list(range(len(res.group())+1))
  else:
    lis = list(reversed(list(range(len(res.group())+1))))

  lis_list.append(lis)

#print(lis_list)

for i in range(len(lis_list)-1):
  if lis_list[i][-1]<lis_list[i+1][0]:
    lis_list[i] = lis_list[i][:-1]
  else:
    lis_list[i+1] = lis_list[i+1][1:]
#print(lis_list)
all = list(itertools.chain.from_iterable(lis_list))
print(sum(all))

Measured memory_bytes: 41372
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;
struct Edge {
    int to,next,w;
    bool operator < (const Edge& rhs)const{
        return w>rhs.w;
    }
} e[N*2];
int cnt, head[N];
void addEdge(int u, int v, int w) {
    e[cnt] = Edge{v, head[u], w};
    head[u] = cnt++;
}
bool vis[N];
int dis[N];
void SPFA(int st, int ed) {
    priority_queue<Edge> q;
    memset(dis,INF,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[st] = 0;
    q.push(Edge{st, 0, 0});
    while (!q.empty()) {
        Edge u = q.top();
        q.pop();
        if(vis[u.to]) continue;
        vis[u.to] = 1;

        for (int i = head[u.to]; ~i; i = e[i].next) {
            int to = e[i].to;
            if (dis[to] > dis[u.to] + e[i].w) {
                dis[to] = dis[u.to] + e[i].w;
                q.push(Edge{to, 0, dis[to]});
            }
        }
    }
    printf("%d\n", dis[ed] == INF?-1:dis[ed]/2);
}
map<int, int>mp[N];
int allPoint;
int getPoint(int x,int y) {
    if (!mp[x][y])
        mp[x][y]=++allPoint;
    return mp[x][y];
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    allPoint=n;
    for (int i=1; i<=m; i++) {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        
        int newX=getPoint(x,w);
        int newY=getPoint(y,w);
        addEdge(x,newX,1);
        addEdge(newX,x,1);
        addEdge(newX,newY,0);
        addEdge(newY,newX,0);
        addEdge(y,newY,1);
        addEdge(newY,y,1);
    }
    SPFA(1,n);

    return 0;
}


Measured memory_bytes: 94068
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N), F(N);
    rep(i,N){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    rep(i,N){
        cin >> F[i];
    }
    sort(F.rbegin(), F.rend());
    ll L = 0;
    ll R = 1e12+1;
    rep(aa,500){
        ll X = (L+R)/2;
        ll cnt = 0;
        rep(i,N){
            ll tmp = A[i]*F[i] - X;
            if(tmp <= 0){
                continue;
            }else{
                cnt += (tmp+F[i]-1)/F[i];
            }
        }
        if(cnt <= K){
            R = X;
        }else{
            L = X;
        }
    }
    cout << R << endl;
}

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

using namespace std;
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> like(M,0);
    for(int i = 0; i < N; i++) {
        int K;
        cin >> K;
        for(int j = 0; j < K; j++) {
            int a;
            cin >> a;
            like.at(a-1)++;
        }
    }
    int ans = 0;
    for(int i = 0; i < M; i++) {
        if(like.at(i) == N) {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#include<stdlib.h>

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>

#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
const int mod=1e9+7;
int n,a[maxn],b[maxn];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>=1;i--)
		cin>>b[i];
	for(int i=1;i<=n;i++){
		if(a[i]==b[i]){
			bool flag=0;
			for(int j=1;j<=n;j++){
				if(b[j]!=a[i]&&b[i]!=a[j]){
					swap(b[i],b[j]);
					flag=1;
					break;
				}
			}
			if(!flag){
				cout<<"No";
				return 0;
			}
		}
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++) cout<<b[i]<<" ";
	system("pause");
    return 0;
}

Measured memory_bytes: 5264
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define vec vector<int>
#define fo(i, n) for (int i = 0; i < n; i++)
#define foo(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define deb(x) cout << #x << " --> " << x << endl;

#define deb1a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
    {                             \
        cout << it << " ";        \
    }                             \
    cout << endl;
#define deb2a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
    {                             \
        for (auto it1 : it)       \
        {                         \
            cout << it1 << " ";   \
        }                         \
        cout << endl;             \
    }
#define mod 1000000007
#define so(v) sort(v.begin(),v.end())
#define fi first
#define se second

int power(int x, unsigned int y, int p){ int res = 1;x = x % p;while (y > 0)  { if (y & 1)res = (res*x) % p;y = y>>1;  x = (x*x)% p;} return res;}
vector<vec> ans(1e6 + 5);
//vec val1;
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    n = n % k;
    cout << min(n, abs(n - k));
}


Measured memory_bytes: 23680
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 131072
int n,l[MN+5],r[MN+5];
ll d[MN+5];
vector< pair<ll,ll> > v[MN+5],V;
bool check(ll x)
{
	for(int i=n;i;--i)
	{
		v[i].clear();V.clear();
		if(!l[i]){v[i].push_back(make_pair(d[i],d[i]));continue;}
		if(v[l[i]].size()>v[r[i]].size())swap(l[i],r[i]);
		for(int j=0,k=0;j<v[l[i]].size();++j)
		{
			for(;k<v[r[i]].size()&&v[l[i]][j].first+v[r[i]][k].second-d[i]*2>x;++k);
			if(k==v[r[i]].size())break;
			V.push_back(make_pair(v[l[i]][j].second,v[r[i]][k].first));
			V.push_back(make_pair(v[r[i]][k].first,v[l[i]][j].second));
		}
		sort(V.begin(),V.end());
		for(int j=0;j<V.size();++j)if(!j||V[j].second<V[j-1].second)v[i].push_back(V[j]);
		if(!v[i].size())return false;
	}
	return true;
}
int main()
{
	int i,x;ll mid,ans;
	for(n=read(),i=2;i<=n;++i)x=read(),(l[x]?r[x]:l[x])=i,d[i]=d[x]+read();
	for(ll l=0,r=1LL<<34;l<=r;)if(check(mid=l+r>>1))ans=mid,r=mid-1;else l=mid+1;
	printf("%lld",ans);
}

Measured memory_bytes: 30196
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let mut x = vec![0; n];
    let mut ans:i64 = 0;
    for i in 0..n {
        if i+a[i]<n {
            x[i+a[i]] += 1;
        }
        if i>=a[i] {
            ans += x[i-a[i]];
        }
    }
    println!("{}", ans);
}

Measured memory_bytes: 6652
#include <bits/stdc++.h>
#define rep(c1,n) for(int (c1)=0;(c1)<(n);(c1)++)
#define all(x) (x).begin(),(x).end()

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};

void chmin(int &c0, int b) { if (c0 > b) c0 = b; }

ll GCD(ll c0, ll b) {
    if (b == 0) return c0;
    else return GCD(b, c0 % b);
}
ll LCM(ll c0, ll b) { return c0 * b / GCD(c0, b); }

int MOD = 1000000007;

int dp[101][4][4][4]; // 

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

    // A: 0
    // G: 1
    // C: 2
    // T: 3

    // 長さ0の文字列は1である。
    // 0,1,2に関する制約しかないので、
    // Sは333Sと考えても問題ない。
    dp[0][3][3][3] = 1;

    // 文字列の文字数
    for (int len=0;len<N;++len) {
        rep(c1, 4)rep(c2, 4)rep(c3, 4) {
            // 条件に当てはまるものはない。計算量を削減できる。
            if (dp[len][c1][c2][c3] == 0) continue;

            for (int c0=0;c0<4;++c0) {
                // だめな5つの条件をカットする。
                if (c0 == 2 && c1 == 1 && c2 == 0) continue;
                if (c0 == 2 && c1 == 0 && c2 == 1) continue;
                if (c0 == 1 && c1 == 2 && c2 == 0) continue;
                if (c0 == 2 && c1 == 1 && c3 == 0) continue;
                if (c0 == 2 && c2 == 1 && c3 == 0) continue;

                // S = ...... c3 c2 c1
                // nextS = ...... c2 c1 c0
                dp[len + 1][c0][c1][c2] += dp[len][c1][c2][c3];
                dp[len + 1][c0][c1][c2] %= MOD;
            }
        }
    }

    int ans = 0;
    rep(c1, 4)rep(c2, 4)rep(c3, 4) {
        ans += dp[N][c1][c2][c3];
        ans %= MOD;
    }

    cout << ans  << endl;
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define nrep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;


int main(){
	vi od,ev;
	int n;
	cin>>n;
	rep(i,n){
		int a;cin>>a;
		if(i%2==0)od.push_back(a);
		else ev.push_back(a);
	}
	if(n%2==0)reverse(ev.begin(),ev.end());
	else reverse(od.begin(),od.end());
	if(n%2==0){
		rep(i,ev.size())cout<<ev[i]<<" ";
		rep(i,od.size())cout<<od[i]<<" ";
		cout<<endl;
	}else{
		rep(i,od.size())cout<<od[i]<<" ";
		rep(i,ev.size())cout<<ev[i]<<" ";
		cout<<endl;
	}
	return 0;
}



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

using namespace std;

const int N = 2e5 + 10;

struct SegTree {
  int mx[N << 2];
  
  void pushup(int x) { mx[x] = max(mx[x<<1], mx[x<<1|1]); }

  void mdf(int x, int l, int r, int p, int v) {
    if (l == r) {
      mx[x] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) mdf(x<<1, l, mid, p, v);
    else mdf(x<<1|1, mid + 1, r, p, v);
    pushup(x);
  }
  
  int qry(int x, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return mx[x];
    int mid = (l + r) >> 1, ans = 0;
    if (ql <= mid) ans = max(ans, qry(x<<1, l, mid, ql, qr));
    if (mid < qr) ans = max(ans, qry(x<<1|1, mid + 1, r, ql, qr));
    return ans;
  }
  
  void build(int x, int l, int r) {
    mx[x] = 0;
    if (l == r) return;
    int mid = (l+r) >> 1;
    build(x<<1, l, mid);
    build(x<<1|1, mid + 1, r);
  }
} T;

int a[N], val[N], tot, n;
vector<int> e[N];

int ans[N];

void dfs(int u, int ff) {
  ans[u] = T.qry(1, 1, tot, 1, a[u]-1) + 1;
  int lst = T.qry(1, 1, tot, a[u], a[u]);
  if (ans[u] > lst) T.mdf(1, 1, tot, a[u], ans[u]);
  ans[u] = max(ans[u], ans[ff]);
  for (auto v : e[u]) if (v != ff) dfs(v, u);
  T.mdf(1, 1, tot, a[u], lst);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), val[++tot] = a[i];
  for (int i = 1; i < n; i++) {
    int u, v; scanf("%d%d", &u, &v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  sort(val + 1, val + n + 1);
  tot = unique(val + 1, val + n + 1) - val - 1;
//  cerr << tot << endl;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(val + 1, val + tot + 1, a[i]) - val;
  T.build(1, 0, tot), dfs(1, 0);
  for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
  return 0;
} 


Measured memory_bytes: 31372
#include<bits/stdc++.h>
using namespace std;
template<typename V>
bool tomin(V&x,V y){if(y<x){x=y;return true;}return false;}
template<typename V>
bool tomax(V&x,V y){if(x<y){x=y;return true;}return false;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define lowbit(x) ((x)&-(x))
int X[20][20];
    int n,D;
bool Check(int A,int B){
    double C=0.0;
    for(int i=1;i<=D;i++){
        C+=(X[A][i]-X[B][i])*(X[A][i]-X[B][i]);
    }
    C=sqrt(C);
    double D=floor(C);
    if(C-D<1e-8)return true;
    if(D+1-C<1e-8)return true;
    return false;
}
int main(){
    scanf("%d%d",&n,&D);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=D;j++){
            scanf("%d",&X[i][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(Check(i,j))ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define fi                      first
#define se                      second
#define pb                      push_back
#define endl                    '\n'
#define all(x)                  x.begin(),x.end()
#define pii                     pair<int,int>
#define fast                    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZ(x)                   ((int)x.size())

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

void solve();

int32_t main()
{
        fast;
        int t = 1;
        // cin >> t;
        for(int i = 1; i <= t; ++i)
                solve();
        cerr << "Time taken: " << ((clock() * 1000) / CLOCKS_PER_SEC) << "ms\n";
}

void solve() {
	int a,b;
	cin >> a >> b;
	for(int i = 1; i <= 3; ++i) {
		if(i != a and i != b) {
			cout << i << endl;
			return;
		}
	}
}

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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  ll mx = 0, cnt;
  rep(i,k) mx += p[i];
  cnt = mx;
  int ansi = 0;
  rep(i,n-k){
    cnt = cnt - p[i] + p[k+i];
    if(mx < cnt) {
      mx = cnt;
      ansi = i+1;
    }
  }
  ll dbans = 0;
  rep(i,k) dbans += p[ansi + i] + 1;
  double ans = dbans;
  ans /= 2;
  printf("%.10f\n", ans);
}


Measured memory_bytes: 4032
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cctype>
#define INF 1000000000
using namespace std;
bool debug=false;

int main(){
  long long x,y;
  long long n,t,a;
  cin>>n>>x>>y;
  for(int i=1;i<n;i++){
    cin>>t>>a;
    if(t==1&&a==1){
      x=max(x,y);
      y=x;
    }else if(t>=x&&a>=y){
      x=t;
      y=a;
    }else{
      
	long long tmp1=(x+t-1)/t;
	long long x1=tmp1*t;
	long long y1=tmp1*a;
      
	long long tmp2=(y+a-1)/a;
	long long x2=tmp2*t;
	long long y2=tmp2*a;
	//cout<<x1<<" "<<y1<<"   "<<x2<<" "<<y2<<endl;

	if(x1>=x&&y1>=y&&x2>=x&&y2>=y){
	  if(x1+y1>x2+y2){
	    x=x2;y=y2;
	  }else{
	    x=x1;y=y1;
	  }
	}else if(x1>=x&&y1>=y){
	  x=x1;y=y1;
	}else{
	   x=x2;y=y2;
	}
    }
    //cout<<x<<" "<<y<<endl;
  }
  cout<<x+y<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

int N;
vector<int> h;

int main() {
    while (cin >> N) {
        h.resize(N);
        for (int i = 0; i < N; ++i) cin >> h[i];

        int res = 0;
        for (int hh = 1;hh <= 100; ++hh) {
            int num = 0;
            bool flag = false;
            for (int i = 0; i < N; ++i) {
                if (h[i] >= hh) {
                    if (!flag) ++num;
                    flag = true;
                }
                else flag = false;
            }
            res += num;
        }
        cout << res << endl;
    }
}
















Measured memory_bytes: 256
'use strict'

function main(s) {

  s = s.split('\n');

  const W = Number(s[0]);
  const H = 2;

  const table = s.slice(1, -1).map(l => l.split(' ').map(n => Number(n)));
  const max   = [...Array(H)].map(l => [...Array(W)].fill('#'));

  const que = [];
  const dh = [0, 1];
  const dw = [1, 0];

  que.push([0, 0]);
  max[0][0] = table[0][0];

  while (que.length > 0) {
    const p = que.shift();

    for (let i = 0; i < 2; i++) {
      const nh = p[0] + dh[i];
      const nw = p[1] + dw[i];
      if (nh < 0 || H <= nh) continue;
      if (nw < 0 || W <= nw) continue;

      que.push([nh, nw]);

      const prev = max[nh][nw];
      const next = max[p[0]][p[1]] + table[nh][nw];

      max[nh][nw] = (prev === '#') ? next : Math.max(prev, next);
    }
  }

  const ans = max[1][W - 1];
  console.log(ans);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7628