akhauriyash/Code-Regression huggingface dataset:
n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)


Measured memory_bytes: 35220
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const [N, Q] = nextIntArray()
    const s = next()
    let l = []
    let r = []
    let agg = new Array(N).fill(0)
    let sum = 0
    agg[0] = 0
    for(let i = 1; i<N; i++){
        if(s[i] == "C" && s[i-1] == "A"){
            sum++
        }
        agg[i] = sum
    }
    while(hasNext()){
        let tmp = nextIntArray()
        l.push(tmp[0]-1)
        r.push(tmp[1]-1)
    }
    let ans = []
    for(let i = 0; i<l.length;i++){
        ans.push(agg[r[i]]-agg[l[i]])
    }
    console.log(ans.join("\n"))
}
Main()


Measured memory_bytes: 62168
N = int(input())
t = [0] * N
x = [0] * N
y = [0] * N

for i in range(N):
    t[i], x[i] ,y[i]=map (int, input().split(' '))



ox = 0 
oy = 0
ot =0

for i in range(N):
    dt=t[i] - ot 

    d = abs(ox - x[i]) + abs(oy - y[i])
    if dt - d < 0:
        print('No')
        exit()

    if (dt-d)%2 > 0:
        print('No')
        exit()

    ox=x[i]
    oy=y[i]
    ot=t[i]

print('Yes')

Measured memory_bytes: 11636
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
int main(void){
  char s[100][100];
  int t[101]={},y[101]={};
  int h,w,i,j;
  scanf("%d%d",&h,&w);
  for(i=0;i<h;i++)scanf("%s",s[i]);
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s[i][j]=='#'){t[i]=1;y[j]=1;}
    }
  }
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(t[i]==1&&y[j]==1) printf("%c",s[i][j]);
    }
    if(t[i]==1)putchar('\n');
  }
  return 0;
}

Measured memory_bytes: 128
h,w = map(int,input().split())
s = [input() for i in range(h)]
reach = [[0]*w for i in range(h)]
reach[0][0]=1
from collections import deque
q = deque([(0,0)])

goal = False
while q:
    x,y = q.popleft()
    for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+i<h and 0<=y+j<w:
            if reach[x+i][y+j]==0 and s[x+i][y+j]=='.':
                reach[x+i][y+j] = reach[x][y]+1
                if x+i==h-1 and y+j==w-1:
                    goal = True
                    break
                q.append([x+i,y+j])

c = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            c += 1

if goal:
    print(c-reach[h-1][w-1])
else:
    print(-1)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define _for(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define FOR(...)    _for (__VA_ARGS__)
#define rep(i,n)    FOR(i, size_t{}, n)
#define ALL(x)      begin (x), end (x)
using namespace std;
using ll = int64_t;
constexpr int64_t inf = 2e18;
constexpr size_t invalid = ~0ull;
constexpr size_t dy [] = {-1ull, 0, 1, 0};
constexpr size_t dx [] = {0, -1ull, 0, 1};

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

  size_t H, W;
  cin >> H >> W;
  vector <vector <char>> s (H, vector <char> (W));
  rep (i, H) rep (j, W) cin >> s[i][j];

  using P = pair <size_t, size_t>;
  vector <P> valid_paths;

  rep (i, H) rep (j, W)
  {
    if (s [i][j] == '.') valid_paths.emplace_back (i, j);
  }

  auto is_path = [&] (size_t y, size_t x)
  {
    return 0 <= y && y < H && 0 <= x && x < W && s[y][x] == '.';
  };

  auto bfs = [&] (const P & start)
  {
    vector <vector <bool>> visited (H, vector <bool> (W, false));
    queue <pair <P, ll>> q;
    auto update = [&] (const P & p, ll cost)
    {
      size_t y, x;
      tie (y, x) = p;
      visited [y][x] = true;
      q.emplace (p, cost);
    };
    update (start, 0);
    ll maxcost = 0;
    while (not q.empty ())
    {
      auto now = q.front (); q.pop ();
      P pos;
      ll cost;
      size_t y, x;
      tie (pos, cost) = now;
      tie (y, x) = pos;

      maxcost = max (maxcost, cost);

      rep (direction, 4)
      {
        size_t ny = y + dy [direction];
        size_t nx = x + dx [direction];
        if (is_path (ny, nx) && not visited [ny][nx])
        {
          update (P {ny, nx}, cost + 1);
        }
      }
    }
    return maxcost;
  };

  ll ans = 0;
  for (auto && elem : valid_paths)
  {
    ans = max (ans, bfs (elem));
  }
  cout << ans << endl;
}


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

int main(){
  string s; cin >> s;
  ll n = s.size();
  string t = s;
  reverse(t.begin() , t.end());
  ll ans = 0;
  rep(i,n/2){
    if(s[i] != t[i])ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
int main() {
    int x;
    cin >> x;
    int count = 0;
    int counta = 9;
    count = x / 500;
    x -= count * 500;
    counta = x / 5;
    cout << count * 1000 + counta * 5 << endl;
}

Measured memory_bytes: 3628
n = int(input())
v = list(map(int,input().split()))
v.sort(reverse=False)
#print(v)
ave = (v[0]+v[1])/2

for i in range(1,n-1):
    #print(ave)
    ave = (ave+v[i+1])/2
    #print(ave)
print(ave)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define pii pair<long long,long long>
#define endl '\n'
void solve()
{
    int n; cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(i%3==0 || i%5==0)
        continue;
        sum+=i;
    }
    
    cout<<sum;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test;test=1;
    while(test--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
using namespace std;
int main(){
    int n,h,m,s;
    cin>>n;
    h=n/3600;
    m=(n%3600)/60;
    s=n%3600-(n%3600)/60*60;
    cout<<h<<":"<<m<<":"<<s<<endl;
    return 0;
}


Measured memory_bytes: 3112
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		String s = sc.nextLine();
		
		int max = 0, curLength = 0;
		
		
		for (int i=0; i<s.length(); i++) {
			char k = s.charAt(i);
			
			if (k == 'A' || k == 'T' || k == 'G' || k == 'C') {
				curLength++;
				max = Math.max(curLength, max);
			} else {
				curLength = 0;
			}
		}
		
		System.out.println(max);
		
	}
}


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

static const int MAX = 100;
static const int INFTY = (1<<21);

int n, M[MAX][MAX];
int d[MAX];
int color[MAX];

void dijkstra(){
  int minv;

  for(int i = 0; i < n; i++){
    d[i] = INFTY;
    color[i] = 0;
  }

  d[0] = 0;
  color[0] = 1;
  while(1){
    minv = INFTY;
    int u = -1;
    for(int i = 0; i < n; i++){
      if(minv > d[i] && color[i] != 2){
        u = i;
        minv = d[i];
      }
    }

    if(u == -1){
      break;
    }
    color[u] = 2;

    for(int v = 0; v < n; v++){
      if(M[u][v] != INFTY && color[v] != 2){
        if(d[u] + M[u][v] < d[v]){
          d[v] = d[u] + M[u][v];
          color[v] = 1;
        }
      } 
    }
  }
}

int main(){
  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      M[i][j] = INFTY;
    }
  }

  int u, k;
  for(int i = 0; i < n; i++){
    cin >> u >> k;
    for(int j = 0; j < k; j++){
      int v, c;
      cin >> v >> c;
      M[i][v] = c;
    }
  }

  dijkstra();
  for(int i  = 0; i < n; i++){
    cout << i << " " << d[i] << endl;
  }

  return 0;
}



Measured memory_bytes: 3104
#include <cstdlib>
#include <iostream>
#include <typeinfo>
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  vector<int> a(5);
  for(int &i:a){
    cin >> i;
  }
  int k;
  cin >> k;
  bool ok = true;
  if(a.at(4)-a.at(0)>k){
    ok = false;
  }
  if(ok){
    cout << "Yay!" << endl;
  }else{
    cout << ":(" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;

int main(void) {

    string S; cin>>S;

    if(regex_match(S, regex("(dream|dreamer|erase|eraser)*"))){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }

    return 0;
}


Measured memory_bytes: 39808
#include<stdio.h>

int main() {
	
	int W,H,x,y,r;
	scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
	if((x+r<=W)&&(0<=x-r)){
		if((y+r<=H)&&(0<=y-r)){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}else{
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 2604
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>
#include <new>
#include <vector>
#include <cstdlib>
#include <string>
#include <set>
#include <tuple>
#include<map>

using namespace std;
int main() {
	string s1,s2,s3;
	cin >> s1 >> s2 >> s3;

	cout << "A" << s2.at(0) << "C" << endl;
	
}

Measured memory_bytes: 3604
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-10**10] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        # 
        # X[a1], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        # X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        #
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(MA[j], X[a1][j], X[a2][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][a1])
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1)
        X[a] = [max(X[a][j], MA[j]) for j in range(N+1)]
        X[b] = [max(X[b][j], MA[j]) for j in range(N+1)]
        X[c] = [max(X[c][j], MA[j]) for j in range(N+1)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(MA[j], X[a][j], X[b][j], X[c][j]) for j in range(N+1)]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

Measured memory_bytes: 218280
#include <cstdio>
using namespace std;

int main(){
	int n, m;
	int a[100];
	int x[100] = {};

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

	int t;
	int u;
	for (int i=0; i<m; i++){
		for (int j=0; j<n; j++){
			scanf("%d", &t);
			if(t == a[i]){
				x[j]++;
			}else{
				u = a[i] - 1;
				x[u]++;
			}
		}
	}

	for (int i=0; i<n; i++){
		printf("%d\n", x[i]);
	}

	return 0;
}

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

int main(){ 
  int n;
  cin >> n;
  vector<int>  d(n);
  for(int i = 0; i< n; i++){
     cin >> d[i];
  }
 int ans = 0;
  for(int i = 0; i< n-1; i++){
       for(int j = i+1; j< n; j++){
              ans += d[i]*d[j];
           }
       }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		ALDS1_5_A();
	}
	public static void ALDS1_5_A() {
		class search{
			int[] A;
			boolean result = false;
			search(int[] A){
				this.A = A;
			}
			public boolean es(int a, int b) {
				if(b == 0) {
					return true;
				}else if(a < 0 || b < 0) {
					return false;
				}
				result = es(a - 1, b - A[a]) || es(a - 1, b);
				return result;
				
			}
		}
		Scanner sc = new Scanner(System.in);
		StringBuilder ans = new StringBuilder();
		int n = sc.nextInt();
		int[] A = new int[n];
		for(int i = 0; i < n; i++)
			A[i] = sc.nextInt();
		int q = sc.nextInt();
		int[] m = new int[q];
		for(int i = 0; i < q; i++) {
			m[i] = sc.nextInt();
			search sh = new search(A);
			if(sh.es(n - 1, m[i])) {
				System.out.println("yes");
			}else {
				System.out.println("no");
			}
		}
	}
}



Measured memory_bytes: 27148
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var n = int.Parse(spl[0]);
        var k = int.Parse(spl[1]);

        var sum = 0L;

        for(int i=k; i<=n; i++) {
            var y = Total(n - (i - 1), n)+1;
            var y2 = Total(0, (i-1));
            y -= y2;
            if (y < 0) y += Mod;

            sum += y % Mod;
            sum %= Mod;
        }

        return sum+1;
    }
    static long Total(long n, long m) {
        var c = (n > m) ? n - m : m - n;
        return (n + m) * (c + 1) / 2;
    }
}


Measured memory_bytes: 27384
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

    if(s == "Sunny") {
        cout << "Cloudy";
    }
    else if(s == "Cloudy") {
        cout << "Rainy";
    }
    else {
        cout << "Sunny";
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n, array[100], i, j, tmp, min, count=0;
  scanf("%d", &n);
  for(i=0;i<=n-1;i++)scanf("%d",&array[i]);
  for(i=0;i<=n-1;i++){
    min = i;
    for(j=i;j<=n-1;j++)if(array[j]<array[min])min=j;
    if(min!=i){
      tmp = array[i];
      array[i] = array[min];
      array[min] = tmp;
      count++;
    }
  }
  for(i=0;i<=n-1;i++){
    if(i>=1)printf(" ");
    printf("%d", array[i]);
  }
  printf("\n");
  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 604
#include <stdio.h>

int main(void) {
    int n;

    scanf("%d", &n);
    while (1) {
        if (n % 4 == 0) {
            printf("Yes\n");
            return 0;
        }
        else if (n < 4) {
            printf("No\n");
            return 0;
        }
        n -= 7;
    }
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
using namespace std;
bool checkOverFlow(string& p) {
  //80行超えているかを判定
  if(p.size() > 80) {
    return false;
  } else return true;
}

void addZero(string& p, int num) {
  //addZero(string型, 0を先頭に付け加える個数)
  for(int i=0; i<num; i++) {
    p = '0' + p;
  }
  return;
}

int main() {
  int N;//データセットの個数
  cin >> N;
  //データを配列にセット
  string* value1 = new string[N];
  string* value2 = new string[N];
  for(int i=0; i<N; i++) {
    cin >> value1[i] >> value2[i];
    //80行超えていたらoverflow
    if(value1[i].size() > 80 or value2[i].size() > 80) {
      value1[i] = "overflow";
    } else {
      //桁数を先頭に0をつけて揃える
      if(value1[i].size() > value2[i].size()) {
        addZero(value2[i], value1[i].size() - value2[i].size());
      } else {
        addZero(value1[i], value2[i].size() - value1[i].size());
      }
    }
  }
  
  ////////////////
  //足し算をする//
  ////////////////
  for(int i=0; i<N; i++) {
    if(value1[i] == "overflow") {
      cout << "overflow" << endl;
      continue;
    }
    //最大の桁数
    int length = max(value1[i].size(), value2[i].size());
    //繰り上がりの保存配列
    int* carryUp = new int[length +1];
    for(int i=0; i<length +1; i++) {
      carryUp[i] = 0;
    } 
    //答えの保存配列
    int* ans = new int[length +1];
   
    for(int j=0; j<length; j++) {
      int sum;
      sum = (value1[i][value1[i].size()-j-1] - '0')
        + (value2[i][value2[i].size()-j-1] - '0')
        + carryUp[j];
      if(sum>9) carryUp[j+1] = 1;
      ans[j] = sum % 10;

      /*
        cout << "value1:  " << value1[i][value1[i].size()-j-1] - '0' << endl;
        cout << "value2:  " << value2[i][value2[i].size()-j-1] - '0' << endl;
        cout << "carryUp: " << carryUp[j] << endl;
        cout << "ans      " << ans[j] << endl;
        cout << "===========" << endl;
      */
    }

    //出力
    int start;//桁数(1:length桁 0:length+1桁)
    if(carryUp[length] == 1){
      ans[length] = 1;
      start = 0;
    } else start = 1;

    string output = "";
    for(int i=start; i<=length; i++) {
      output += ans[length -i];
    }

    if(output.size() > 80) {
      cout << "overflow" << endl;
    } else {
      for(int i=start; i<=length; i++) {
        cout << ans[length -i];
      }
      cout << endl;
    }
    
    delete[] carryUp;
    delete[] ans;
  }
  delete[] value1;
  delete[] value2;
}



Measured memory_bytes: 3052
#include<bits/stdc++.h>
//macros
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
const long long int mod = 1e9 + 7;
int main()
{
    int X, res=0, temp=0;
    cin >> X;
    rep(i,1,X+1){
        rep(j,2,X+2){
            temp = pow(i,j);
            if(temp>X) break;
            res = max(temp, res);
        }
    }
    cout << res << endl;
}

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

using namespace std;

const int MAX_N = 2e5 + 5;

int cnt [MAX_N];

int main () {
  ios::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;

  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;

    cnt[x]++;
  }

  vector<pair<int, int>> blocks;
  for (int i = 1; i <= n; i++) {
    if (cnt[i] != 0) {
      blocks.push_back(make_pair(cnt[i], i));
    }
  }

  sort(blocks.begin(), blocks.end());
  int ans = 0;
  for (int i = 0; i < (int) blocks.size() - k; i++) {
    ans += blocks[i].first;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int block_size;
struct Query {
    int l, r, idx;
    bool operator<(Query other) const {
        return make_pair(l / block_size, r) < make_pair(other.l / block_size, other.r);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    block_size = sqrt(n);
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    vector<Query> vq;
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        vq.push_back((Query){l, r, i});
    }
    vector<int> answers(q);
    int ans = 0;
    vector<int> mp(n+1, 0);
    auto add = [&](int idx) {
        if(mp[v[idx]]==0) {
            ans++;
        }
        mp[v[idx]]++;
    };
    auto remove = [&](int idx) {
        if(mp[v[idx]]==1) {
            ans--;
        }
        mp[v[idx]]--;
    };
    sort(vq.begin(), vq.end());
    int cur_l = 0;
    int cur_r = -1;
    for (Query qu : vq) {
        while (cur_l > qu.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < qu.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < qu.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > qu.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[qu.idx] = ans;
    }
    for(int x : answers) {
        cout << x << "\n";
    }
    return 0;
}

Measured memory_bytes: 15448
#ACしてないときはWAは加算されないようにする必要あり．
N, M = map(int, input().split())

AC = 0
WA = 0
A = [[0]*2 for _ in range(N)] #flag管理,n番目の問題がACになったらn-1番目の配列に1を入れる
for _ in range(M):
	p, S = input().split() #注意!ここのpはstrで入っている
	ip = int(p)
	if A[ip-1][1] == 0:
		if S == "WA":
			A[ip-1][0] += 1
		else:
			A[ip-1][1] = 1
			AC += 1
	else:
		continue

for i in range(N): #WAのカウント
	if A[i][1] == 1:
		WA += A[i][0]

print(AC,WA)

Measured memory_bytes: 13172
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;

int main(){
  int A,B,C; cin >> A >> B >> C;
  int X,Y; cin >> X >> Y;
  map<int,int> m;
  m.insert(make_pair(X,A));
  m.insert(make_pair(Y,B));
  
  cout << min(X,Y)*min(A+B,2*C) + (max(X,Y)-min(X,Y))*(min(m.at(max(X,Y)),2*C));
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <random>
#include <utility>
#include <map>
#include <vector>
#include <queue>
#include <bitset>
#include <sstream>
#define REP(i,x) for(int i=0; i<(x); i++)
typedef long long ll;

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin>>n;
    int a[n+2];
    a[0]=0;
    a[n+1]=0;
    REP(i, n){
        cin>>a[i+1];
    }
    int cost=abs(a[1])+abs(a[n+1]);
    int ans[n];
    REP(i, n){
        cost += abs(a[i+1]-a[i+2]);
        if ((a[i+1]-a[i])*(a[i+2]-a[i+1])<0) {
            ans[i]=abs(a[i+1]-a[i])+abs(a[i+2]-a[i+1])-abs(a[i]-a[i+2]);
        } else {
            ans[i]=0;
        }
    }
    REP(i, n){
        cout << cost-ans[i]<<endl;
    }
    
    
    return 0;
}



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

#define MAX 100005

using namespace std;

int x, y, N;
int total;
vector< pair<int, pair<int, int> > > V;
vector< pair<int, int> > X, Y;
int T[MAX];

int find(int x)
{
	if (T[x]<0) return x;
	return T[x] = find(T[x]);
}

void unite(int cost, int x, int y) {		//T木に要素を追加
	x = find(x);
	y = find(y);
	if (x == y) return;
	total += cost;
	if (T[x] < T[y])  T[y] = x;
	else  T[x] = y;
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		T[i] = -1;
		cin >> x >> y;
		X.push_back(make_pair(x, i));
		Y.push_back(make_pair(y, i));
	}
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	for (int i = 0; i< N - 1; i++)
	{
		V.push_back(make_pair(X[i + 1].first - X[i].first, make_pair(X[i].second, X[i + 1].second))); //(距離, i, i+1)
		V.push_back(make_pair(Y[i + 1].first - Y[i].first, make_pair(Y[i].second, Y[i + 1].second)));
	}
	sort(V.begin(), V.end());

	total = 0;

	for (int i = 0; i < V.size(); i++) {
		unite(V[i].first, V[i].second.first, V[i].second.second);

	}
	cout << total << endl;

	return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll L, R, d;
    cin >> L >> R >> d;
    ll ans = 0;
    repi2(i, L, R) {
        if(i % d == 0) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3672
S = input()
T = input()
N = len(S)

start = [-1 for i in range(26)]
goal = [-1 for i in range(26)]
a = ord('a')
ans = 'Yes'
for i in range(N):
    s = ord(S[i])-a
    t = ord(T[i])-a
    if start[s] != -1 or goal[t] != -1:
        if start[s] != t or goal[t] != s:
            ans = 'No'
    start[s] = t
    goal[t] = s


print(ans)


Measured memory_bytes: 3632
using System;

class Program
{
  static void Main(string[] args)
  {
    string[] input = Console.ReadLine().Split('/');
    int year = int.Parse(input[0]);
    int month = int.Parse(input[1]);
    int day = int.Parse(input[2]);
    
    if(year == 2019)
    {
      if(month <= 4) Console.WriteLine("Heisei");
      else Console.WriteLine("TBD");
    }
    else if(year >= 2020) Console.WriteLine("TBD");
    else if(year <= 2018) Console.WriteLine("Heisei");
  }
}

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


int main(){
    string s;
    cin >> s;
    ll n = s.size();

    ll res = 2;

    map<char, int> m;
    rep(i, n)   m[s[i]]++;

    rep(i, n)   res += n-m[s[i]];

    cout << res/2 << endl;

    return 0;
}


Measured memory_bytes: 640
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {in_n: usize, in_m: usize};

    if in_n % 2 == 0 {
        for i in 0..in_m / 2 {
            println!("{} {}", i + 1, in_m * 2 + 1 - i);
        }

        for i in in_m / 2..in_m {
            println!("{} {}", i + 2, in_m * 2 + 1 - i);
        }
    } else {
        for i in 0..in_m {
            println!("{} {}", i + 1, in_m * 2 - i);
        }
    }
}


Measured memory_bytes: 2136
#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


typedef  long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;


#define endl "\n"
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N=5e5+5;
int mod=1e9+7;

ll mul (ll a, ll b)
{
    a%=mod;
    b%=mod;
    return (a*b)%mod;
}
ll add (ll a, ll b)
{
    a%=mod;
    b%=mod;
    return (a+b+mod)%mod;
}
ll fastpow(ll b, ll p)
{
    if(p==0)
        return 1;
    ll ans=fastpow(b,p/2);
    ans=mul(ans,ans);
    if(p%2)ans=mul(ans,b);
    return ans;
}


int main()
{
    FIO
    int n;
    cin>>n;
    int co=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x!=i)
        co++;
    }
    if(co<=2)
        cout<<"YES";
    else
        cout<<"NO";



    return 0;
}


Measured memory_bytes: 3644
let ans = ref 0
let _ = Scanf.scanf "%d %d %d %d" @@ fun a b c x -> for i = 0 to a do for j = 0 to b do for k = 0 to c do if 500 * i + 100 * j + 50 * k = x then incr ans done done done; Printf.printf "%d\n" !ans

Measured memory_bytes: 384
using System;

public class Hello
{
    public const long E7 = 1000000007;
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var m = long.Parse(line[0]);
        var n = long.Parse(line[1]);
        Console.WriteLine(power(m, n) % E7);
    }
    public static long power(long x, long n)
    {
        if (n == 0) return 1;
        return n % 2 == 0 ? power((x * x) % E7, n / 2) % E7 : x * (power(x, n - 1) % E7);
    }
}


Measured memory_bytes: 9212
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long long int64;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
template<class T,class U>bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T,class U>void vcin(T &v, U n){rep(i, n){typename T::value_type a;cin >> a;v.pb(a);}}
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

const double PI=3.14159265358979323846;
int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cill(n);
    double ans = n * 2 * PI;


    co(ans);

    return 0;
}

Measured memory_bytes: 3792
import math
 
a,b,c,d=map(int,input().split())
 
n=b-a+1
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
  
x=lcm(c,d)
 
cc=b//c-(a-1)//c
dc=b//d-(a-1)//d
xc=b//x-(a-1)//x
 
print(n-cc-dc+xc)

Measured memory_bytes: 9192
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int s,t;
    cin>>s>>t;
    s--;
    t--;
   int y = t/s;
    if(t%s!=0)y++;
    
    cout<<y<<endl;
    //vector<int> a(n,0);
    // vector<vector<int>> a(n,vector<int>(m,0));
}

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

typedef pair<int,int> P;
const int INF = 500000000;

int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    ll ans = (a*(min(n,b-1)))/b;
    cout << ans << "\n";
}

Measured memory_bytes: 3632
/*
Written By mafailure
*/
//In the name of God
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less
using namespace std;
using namespace __gnu_pbds;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long 
// int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1};
// int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};
const long long mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector< pair< int, int > > vii;
typedef map<int, int> mii;
typedef pair<int, ii> pip;
typedef pair<ii, int> ppi;
#define arrinp(arr,init,final,size,type) type* arr=new type[size];for(int i=init;i<final;i++)cin>>arr[i];
#define cr2d(arr,n,m,t) t**arr=new t*[n];for(int i=0;i<n;i++)arr[i]=new t[m];
#define w(t) int t;cin>>t; while(t--)
#define takeInp(n) int n;cin>>n;
#define fr(i,init,final) for(int i=init;i<final;i++)
#define frr(i,init,final) for(int i=init;i>=final;i--)
#define Fr(i,final) for(int i=0;i<final;i++)
#define Frr(i,first) for(int i=first;i>=0;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define debug(x) cerr<<">value ("<<#x<<") : "<<x<<endl;
#define setb __builtin_popcount
#define lsone(n) (n&(-n))
#define rlsone(n) (n&(n-1))
#define clr(a,b) memset(a,b,sizeof(a))
const int inf= INT_MAX;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set; 
vi init(string s)
{
	istringstream sin(s);
	int n;
	vi arr;
	while(sin>>n)arr.push_back(n);
	return arr;
}
int power(int x, int y)
{ 
	if(y==0)return 1;
	int u=power(x,y/2);
	u=(u*u)%mod;
	if(y%2)u=(x*u)%mod;
	return u;
    
}
int gcd(int a,int b)
{
	if(a<b)return gcd(b,a);
	return (b==0?a:(a%b?gcd(b,a%b):b));
}
int gcd_e(int a,int b,int &x,int &y)
{
	
	if(b==0){x=1; y=0; return a;}
	int x1,y1;
	int p=gcd_e(b,a%b,x1,y1);
	x=y1;
	y=x1-(a/b)*y1;
	return p;
}
signed main()
{
	IOS
	int n;
	cin>>n;
	cout<<(n>=30?"Yes\n": "No\n");
	
	
}



Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <queue>
using namespace std;

int main(){
	string s;
	cin >> s;
	long long x = 0;
	for(int i = 0; i < s.size(); i++){
		x += s[i] - '0';
	}
	cout << (x % 9 == 0 ? "Yes" : "No") << '\n';
}


Measured memory_bytes: 3748
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <ext/random>
#include <ext/rope>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using ull = unsigned long long;
using vi = std::vector<int>;
using vl = std::vector<int64>;
using pii = std::pair<int, int>;
using pll = std::pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(_) (_).begin(), (_).end()
#define rall(_) (_).rbegin(), (_).rend()
#define print(_) std::cout << (_) << '\n'
#define debug(_) std::cerr << #_ << ": " << (_) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  os << '{';
  for (size_t i = 0; i < vec.size(); ++i) {
    os << vec[i];
    if (i != vec.size() - 1) os << ',';
  }
  os << '}';
  return os;
}
template<typename T, typename U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '{' << p.first << " " << p.second << '}';
}
// constant
constexpr int INF = std::numeric_limits<int>::max() / 2;  // 1.073741823e9
constexpr int64 INF64 = std::numeric_limits<int64>::max() / 2;  // 4.611686018427387903e18
constexpr int MOD = 1000000007;

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

  //std::ifstream in("input.txt");
  //std::cin.rdbuf(in.rdbuf());

  int n, m; cin >> n >> m;
  int cnt[202020] = {};

  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    ++cnt[a]; --cnt[b];
  }

  for (int i = 1; i < 200000; ++i) {
    cnt[i] += cnt[i - 1];
  }

  for (int i = 1; i <= n - 1; ++i) {
    if (cnt[i] & 1) {
      cout << "NO" << endl;
      return 0;
    }
  }

  cout << "YES" << endl;

  return 0;
}

Measured memory_bytes: 1024
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 1e-8;

long long int N, M, K, H, W, L, R;

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

	cin >> N;
	vector<int>v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	int ans = 0;
	for (int i = 1; i < N; i++) {
		v[i] = v[i] * v[i - 1] + v[i];
		ans = max(ans, v[i]);
	}
	cout << ans + 1 << endl;
	return 0;
}


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

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

	char c = s[s.size()-1];
	if (c == '3') cout << "bon\n";
	else if (c == '0' || c == '1' || c == '6' || c == '8') cout << "pon\n";
	else cout << "hon\n";
	return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin >> s >> t;
  int num=s.size();
  int count=0;
  for(int i=0;i<num;i++){
    if(s.at(i)!=t.at(i)){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3864
#include <iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    string s[55];
    int t[55];
    int result = 0;
    for(int i = 0; i < n; i++){
        cin >> s[i] >> t[i];
    }
    string x;
    cin >> x;
    for(int i = n - 1; i >= 0; i--){
        if(s[i] == x)
          break;
            result += t[i];
    }
    cout << result << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
double PI = 3.1415926535897932;
lint MOD;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

void dfs1(int cur, int par, vector<vector<int>> &g, vector<lint> &dp) {
    lint ret = 1;
    for (auto nxt : g[cur]) {
        if (nxt == par) continue;
        dfs1(nxt, cur, g, dp);
        ret *= (dp[nxt] + 1);
        ret %= MOD;
    }
    dp[cur] = ret;
}

void dfs2(int cur, int par, vector<vector<int>> &g, vector<lint> &dp, vector<lint> &ans, lint Dpar) {
    lint ret = Dpar + 1;
    if (Dpar == -1) ret = 1;
    vector<int> chs;
    for (auto nxt : g[cur]) {
        if (nxt == par) continue;
        ret *= (dp[nxt] + 1);
        ret %= MOD;
        chs.push_back(nxt);
    }
    ans[cur] = ret%MOD;

    // 左右から累積
    size_t sz = chs.size();
    vector<lint> accLeft(sz + 2, 1);
    vector<lint> accRight(sz + 2, 1);
    for (int i = 1; i <= sz; i++) {
        accLeft[i] = (dp[chs[i - 1]] + 1);
        accRight[i] = (dp[chs[i - 1]] + 1);
    }

    for (int i = 1; i <= sz; i++) {
        accLeft[i] *= accLeft[i - 1];
        accLeft[i] %= MOD;
    }

    for (int i = sz; i >= 1; i--) {
        accRight[i] *= accRight[i + 1];
        accRight[i] %= MOD;
    }

    for (int i = 1; i <= sz; i++) {
        lint nxtDpar = accLeft[i - 1] % MOD * accRight[i + 1] % MOD;
        int nxt = chs[i - 1];
        if (Dpar != -1) {
        nxtDpar *= (Dpar + 1);
        nxtDpar %= MOD;
        }
        if (nxt == par) continue;
        dfs2(nxt, cur, g, dp, ans, nxtDpar);
    }
}

int main() {

    int n; cin >> n;
    cin >> MOD;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<lint> dp(n);
    vector<lint> ans(n);
    dfs1(0, -1, g, dp);
    dfs2(0, -1, g, dp, ans, -1);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 27648
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector <int> p(n), q(n);
    for(int i=0;i<n;++i) cin >> p[i];
    for(int i=0;i<n;++i) cin >> q[i];
    int a=0, b=0, ac=0, bc=0;
    vector <int> s(n);
    int sum=0;
    for(int i=0;i<n;++i) {
        s[i]=i+1;
        sum+=s[i];
    }
    int res=1;
    do{
        for(int i=0;i<n;++i) {
            if(s[i]==p[i]) ++a;
            else a=0;
            if(a==n) ac=res;
            if(s[i]==q[i]) ++b;
            else b=0;
            if(b==n) bc=res;
       }
        ++res;
    }while(next_permutation(s.begin(),s.end()));
    cout << abs(ac-bc) << endl;
}

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;


int gcd(int a, int b) {
  if (b == 0) return a;
  else return gcd(b, a % b);
}

int main() {
  int n; cin >> n;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  int g = gcd(a[0], a[1]);
  FOR(i, 2, n) {
    if (g > a[i]) g = gcd(g, a[i]);
    else g = gcd(a[i], g);
  }
  cout << g << endl;
}


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

using namespace std;

int main (void) {
    int N, M, X;
    cin >> N >> M >> X;
    vector<int> A(M);
    for ( int i = 0; i < M; i++ ) {
        cin >> A.at(i);
    }

    vector<int> a(N+1, 0);
    for ( int i = 0; i < M; i++ ) {
        a.at(A.at(i)) = 1;
    }

    int ans1 = 0;
    for ( int i = X; i <= N; i++ ) {
        ans1 += a.at(i);
    }
    int ans2 = 0;
    for ( int i = X; i >= 0; i-- ) {
        ans2 += a.at(i);
    }
    int ans = min(ans1, ans2);

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


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

#define P pair<lli,lli>

signed main(){

	lli n;
	cin>>n;
	vector<lli> l(n);
	REP(i,0,n)cin>>l[i];

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

	lli cnt=0;
	for(lli i=0;i<n;i++){
		lli a = l[i];
		for(lli j=i+1;j<n;j++){
			lli b = l[j];
			for(lli k=j+1;k<n;k++){
				lli c = l[k];
				if(c>a+b)break;
				if(a<b+c && b<c+a && c<a+b)cnt++;
			}
		}
	}
	cout<<cnt<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define inputv(arr,n) for(ll i=0;i<n;i++){ll value;cin>>value;arr.pb(value);}
#define sz(a) ((ll)(a).size())
#define len(a) ((ll)(a).length())
#define precise cout<<fixed<<setprecision(0); 
#define F first
#define S second
#define vi vector <int> 
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define YES cout<<"Yes\n"
#define NO cout<<"No\n"
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
inline ll max(ll a,ll b)
{return ((a>b)?a:b);}
inline ll min(ll a,ll b)
{return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b)
{if(b==0) return a;a%=b;return gcd(b,a);}
#define nl cout<<"\n"
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
// hashing for pairs
struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};
//sort in reverse order
bool compare(ll x, ll y){
    return x>y;
}
void solve()
{
  ll x;
  cin>>x;
  if(x>=30)
  {
    YES;
  }
  else
  {
    NO;
  }
  
  return;
}
int main()
{
    IOS;
    int T=1;
   // cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    if ((a + b) % 2 == 0) cout << ((a + b) / 2);
    else cout << "IMPOSSIBLE";
    cout << endl;

    return 0;
}


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

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

    int Sn = 0;
    int d = N;
    while(N>0){
        if(N==0) break;
        Sn += N % (10);
        N = N/10;
    }

    if(d%Sn == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int array[][] = new int [3][3];

        array[0][0] = sc.nextInt();
        array[0][1] = sc.nextInt();
        array[0][2] = sc.nextInt();
        array[1][0] = sc.nextInt();
        array[1][1] = sc.nextInt();
        array[1][2] = sc.nextInt();
        array[2][0] = sc.nextInt();
        array[2][1] = sc.nextInt();
        array[2][2] = sc.nextInt();

        int n = sc.nextInt();

        int num[] = new int [n];

        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < 3; i++) {
                for (int k = 0; k < 3; k++) {
                    if (array[i][k] == num[j]) {
                        array[i][k] = 1000;
                    }
                }
            }
         }

        for (int i = 0; i < 3; i++) {
           if (array[i][0] == 1000 && array[i][1] == 1000 && array[i][2] == 1000) {
               System.out.println("Yes");
               return;
           }

            if (array[0][i] == 1000 && array[1][i] == 1000 && array[2][i] == 1000) {
                System.out.println("Yes");
                return;
            }
        }

        if (array[0][0] == 1000 && array[1][1] == 1000 && array[2][2] == 1000) {
            System.out.println("Yes");
            return;
        }

        if (array[0][2] == 1000 && array[1][1] == 1000 && array[2][0] == 1000) {
            System.out.println("Yes");
            return;
        }

        System.out.println("No");

    }

}


Measured memory_bytes: 23764