akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

ll numh[300010];
ll numw[300010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, W, M;
    cin >> H >> W >> M;
    set<plglg> st;
    REP(i, 0, M) {
        ll h, w;
        cin >> h >> w;
        h--;
        w--;
        numh[h]++;
        numw[w]++;
        st.insert(plglg(h, w));
    }
    ll hmax = 0;
    REP(i, 0, H) {
        hmax = max(hmax, numh[i]);
    }
    ll wmax = 0;
    REP(j, 0, W) {
        wmax = max(wmax, numw[j]);
    }
    vll hnum, wnum;
    REP(i, 0, H) {
        if (numh[i] == hmax) {
            hnum.push_back(i);
        }
    }
    REP(j, 0, W) {
        if (numw[j] == wmax) {
            wnum.push_back(j);
        }
    }
    bool emp = false;
    REP(i, 0, hnum.size()) {
        REP(j, 0, wnum.size()) {
            if (!st.count(plglg(hnum[i], wnum[j]))) {
                emp = true;
                break;
            }
        }
        if (emp) {
            break;
        }
    }
    ll ans = hmax + wmax;
    if (!emp) {
        ans--;
    }
    cout << ans << endl;
}


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

import sys
import os
import math
from datetime import date

for s in sys.stdin:
    y1, m1, d1, y2, m2, d2 = map(int, s.split())

    if y1 == m1 == d1 == y2 == m2 == d2 == -1:
        break

    day1 = date(y1, m1, d1)
    day2 = date(y2, m2, d2)

    delta = day2 - day1
    print(delta.days)

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

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

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

template<class T>bool chmax( T& a, const T& b ) { if( a < b ) { a = b; return 1; } return 0; }
template<class T>bool chmin( T& a, const T& b ) { if( a > b ) { a = b; return 1; } return 0; }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main(){
    ll N, a, b, c, d, e; cin >> N >> a >> b >> c >> d >> e;
    cout << 5 + ( N + min( { a, b, c, d, e } ) - 1 ) / min( { a, b, c, d, e } ) - 1 << endl;

}

/*

*/

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}
 
int main() {
    ll n;
    cin >> n;
 
    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
 
    vl L(n-1);  // L[i] : a[0]からa[i]までのGCD
    L[0] = a[0];
    exrep(i, 1, n-2) {
        L[i] = gcd(L[i-1], a[i]);
    }
 
    vl R(n-1);  // R[i] : a[n-1]からa[(n-1) - i]までのGCD
    R[0] = a[n-1];
    exrep(i, 1, n-2) {
        R[i] = gcd(R[i-1], a[(n-1) - i]);
    }
 
    ll ans = max(L[n-2], R[n-2]);
    exrep(i, 1, n-2) {
        chmax(ans, gcd(L[i-1], R[(n-2) - i]));
    }
 
    out(ans);
    re0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define mp make_pair
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 30) - 1;
const ll LINF = (1LL << 60) - 1;
const double eps = 1e-9;
const ll MOD = 998244353LL;
template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
};
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
};
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
ll n;
vector<vector<P>> G, nG;
vector<ll> s, siz, ans;
int v, ss, id;
void dfs(int i, int p) {
    for(auto e : G[i]) {
        if(e.first == p) {
            continue;
        }
        dfs(e.first, i);
        if(siz[e.first] == n - siz[e.first]) {
            v = i;
            ss = siz[e.first];
            id = e.second;
        } else {
            ans[e.second] =
                (s[i] - s[e.first]) / (siz[e.first] - (n - siz[e.first]));
        }
        nG[i].push_back(P(e.first, ans[e.second]));
        nG[e.first].push_back(P(i, ans[e.second]));
        siz[i] += siz[e.first];
    }
}
ll sum;
void dfs2(int i, int p, ll d) {
    sum += d;
    for(auto e : nG[i]) {
        if(e.first == p) {
            continue;
        }
        dfs2(e.first, i, d + e.second);
    }
}
int main() {
    cin >> n;
    G.resize(n);
    s.resize(n);
    siz.resize(n, 1);
    ans.resize(n);
    nG.resize(n);
    v = -1;
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].push_back(P(b, i));
        G[b].push_back(P(a, i));
    }
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }
    dfs(0, -1);
    if(v != -1) {
        sum = 0;
        dfs2(v, -1, 0);
        ans[id] = (s[v] - sum) / ss;
    }
    for(int i = 0; i < n - 1; i++) {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 28160
S = str(input())
N = len(S)

p1 = ""
p2 = ""
for i in range(N):
    if i % 2 == 0:
        p1+=str(0)
        p2+=str(1)
    else:
        p1+=str(1)
        p2+=str(0)
#print(p1)
#print(p2)

a1 = 0
a2 = 0
for i in range(N):
    if p1[i] != S[i]:
        a1 += 1
    if p2[i] != S[i]:
        a2 += 1
#print(a1,a2)
print(min(a1,a2))


Measured memory_bytes: 3316
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

const int maxn = 1E5 + 10;

int N,L,T,d,A[maxn];

int pre(int x) {return x == 1 ? N : x - 1;}
int nex(int x) {return x == N ? 1 : x + 1;}

int main()
{
    #ifdef DMC
        freopen("DMC.txt","r",stdin);
    #endif

    cin >> N >> L >> T;
    for (int i = 1; i <= N; i++)
    {
        int x,w; scanf("%d%d",&x,&w);
        if (w == 1)
        {
            int dt = T;
            if (L - x <= dt)
                dt -= (L - x),++d,x = 0;
            x += dt; d += dt / L; x %= L;
        }
        else
        {
            int dt = T;
            if (x + 1 <= dt)
                dt -= (x + 1),--d,x = L - 1;
            x -= dt; d -= dt / L; x %= L;
            if (x < 0) x += L;
        }
        A[i] = x; d %= N;
    }
    int pos = 1; d %= N;
    while (d < 0) pos = pre(pos),++d;
    while (d > 0) pos = nex(pos),--d;
    sort(A + 1,A + N + 1);
    for (int i = pos; i <= N; i++) printf("%d\n",A[i]);
    for (int i = 1; i < pos; i++) printf("%d\n",A[i]);
    return 0;
}

Measured memory_bytes: 1536
use std::io;

fn get_line() -> String {
  let mut line = String::new();
  io::stdin()
    .read_line(&mut line)
    .unwrap();
  line
}

fn line_to_vec_i64(line: &str) -> Vec<i64> {
  line
    .trim()
    .split_whitespace()
    .map(|val| { val.parse::<i64>().unwrap() })
    .collect()
}

fn main() {
  loop {
    let v = line_to_vec_i64(&get_line());
    let (h, w) = (v[0], v[1]);
    if h == 0 && w == 0 {
      break;
    }
    else {
      for i in 0..h {
        if i == 0 || i == h - 1 {
          println!("{}", "#".repeat(w as usize));
        }
        else {
          println!("#{}#", ".".repeat((w - 2) as usize));
        }
      }
      println!();
    }
  }
}



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

using namespace std;

int main(int argc, const char *argv[]) {
  //
  int x;
  cin >> x;
  if (x >= 30) {
    cout << "Yes" << '\n';
  } else {
    cout << "No" << '\n';
  }
  return 0;
}

Measured memory_bytes: 3620
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


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

  vector<vector<int>> F(N, vector<int>(10));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> F[i][j];
    }
  }


  vector<vector<int>> P(N, vector<int>(11));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 11; j++) {
      cin >> P[i][j];
    }
  }

  int ans = -(1 << 30);
  for(int i = 1; i < 1 << 10; i++) {
    int p = 0;
    for(int j = 0; j < N; j++) {
      int c = 0;
      for(int k = 0; k < 10; k++) {
        if (i >> k & 1 && F[j][k]) {
          c++;
        }
      }
      p += P[j][c];
    }
    ans = max(ans, p);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
num_val = str(input())

if num_val[len(num_val) - 1] in ['2', '4', '5', '7', '9']:
    print('hon')
elif num_val[len(num_val) - 1] in ['0', '1', '6', '8']:
    print('pon')
elif num_val[len(num_val) - 1] in ['3']:
    print('bon')


Measured memory_bytes: 61800
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k,a,b,x,y,ans;
int main(){
	scanf("%lld%lld%lld",&k,&a,&b);
	if (b-a<=1) return printf("%lld\n",1+k),0;
	y=a-1;
	if ((k-y)>=0){
		x=(k-y)/2;
		ans=1+y+(b-a)*x;
		if ((k-y)&1) ans++;
		printf("%lld\n",ans);
	} else return printf("%lld\n",1+k),0;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <bitset>

#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define debugV(vec) rep(i,vec.size()) cout << vec[i] << " "; cout << endl;
typedef long long int llint;

using namespace std;

const llint inf = pow(10, 12);

int main(void) {
	int n;
	cin >> n;

	vector<int> a(n);
	rep(i,n) cin >> a[i];

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

	int even = 0, size = 1, group = 1;
	rep(i,n-1) {
		if (a[i] == a[i+1]) {
			size++;
		}
		else {
			group++;
			if (size % 2 == 0) even++;
			size = 1;
		}
	}
	if (size % 2 == 0) even++;
	if (even % 2 == 0) cout << group << endl;
	else cout << group - 1 << endl;
}



Measured memory_bytes: 640
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
//    var pre = 2
//    var aaaaaa = 0
////    out.println("1:" +pre)
//    out.println(pre)
//    for (i in 1..12) {
//        aaaaaa += pre
//        val tmp = pre * pre % 1001
//
//
//        out.println("${i}:" + aaaaaa)
//        out.println(tmp)
//        pre = tmp
//    }
////    out.println(aaaaaa)
//    out.println()

    val (n, x, m) = readLongList()

//    val set = mutableSetOf<Long>()
    val indexMap = mutableMapOf<Long, Int>()
    var cur = x
    var curIndex = 0
    while (indexMap.containsKey(cur) == false) {
        indexMap[cur] = curIndex
        curIndex++
        cur = (cur % m) * (cur % m) % m
    }

    val loopFrom = indexMap[cur]!!

    if (n <= loopFrom) {
        var ans = 0L
        var pre = x
        repeat(n.toInt()) {
            ans += pre
            pre = (pre % m) * (pre % m) % m
        }
        out.println(ans)
        return
    } else {
        val firstSum = indexMap.filter { it.value < loopFrom }.keys.sum()
        val loopSum = indexMap.filter { it.value >= loopFrom }.keys.sum()
        val loopCount = indexMap.count() - loopFrom

        var ans = firstSum

        val remain = max(0, n - loopFrom)
        val aaa = remain / loopCount
        val modRemain = remain % loopCount

        ans += aaa * loopSum

        var pre = cur
        repeat(modRemain.toInt()) {
            ans += pre
            pre = (pre%m) * (pre%m) % m
        }
        out.println(ans)
        return
    }
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 48144
// by newbiechd
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

// Delete the debugging information!
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

const int N_MAX = 100003, M_MAX = 200003;
int h[N_MAX], cntEdge;
struct Edge {
  int tar, nxt;
  Edge() {}
  Edge(int tar, int nxt) : tar(tar), nxt(nxt) {}
}ed[M_MAX];

int col[N_MAX], cntNode, tub[3];
int dfs(int x) {
  ++cntNode, ++tub[col[x]];
  bool ext[2];
  int state = 0;
  for (int i = h[x]; i; i = ed[i].nxt) {
    ++cntEdge, ext[i & 1] = 1;
    int y = ed[i].tar, temp = col[x] - 1 - (i & 1);
    temp += (temp >> 31) & 3;
    if (col[y] > 2)
      col[y] = temp, state |= dfs(y);
    else
      if (col[y] != temp)
        state |= 2;
  }
  return state | (ext[0] & ext[1]);
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    ed[++cntEdge] = Edge(y, h[x]), h[x] = cntEdge;
    ed[++cntEdge] = Edge(x, h[y]), h[y] = cntEdge;
  }
  
  long long ans = 0;
  memset(col + 1, 0x3f, sizeof(int) * n);
  for (int i = n; i; --i)
    if (col[i] > 2) {
      cntNode = cntEdge = tub[0] = tub[1] = tub[2] = 0, col[i] = 2;
      int state = dfs(i);
      if (state & 2)
        ans += 1ll * cntNode * cntNode;
      else
        if (tub[0] && tub[1] && tub[2])
          ans += 1ll * tub[0] * tub[1] + 1ll * tub[1] * tub[2] +
            1ll * tub[2] * tub[0];
        else
          ans += cntEdge >> 1;
    }
  for (int i = 1; i <= n; ++i)
    assert(col[i] >= 0 && col[i] < 3);
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 7296
from collections import defaultdict
import math
def main():
    def factorization(num):
        nonlocal d
        if num in primes:
            d[num] += 1
            return
        for prime in primes:
            if num % prime == 0:
                count = 0
                while num % prime == 0:
                    count += 1
                    num //= prime
                d[prime] += count

    def generate_primes(num):
        if num == 1: return []
        primes = list(range(2, num + 1))
        i, p = 0, 1
        while p <= math.sqrt(num):
            if primes[i] != 0:
                p = primes[i]
                primes = [prime if (prime % p != 0 or prime == p) else 0 for prime in primes]
            i += 1
        return set(p for p in primes if p != 0)

    n = int(input())
    d = defaultdict(lambda :1)
    primes = generate_primes(100)
    for i in range(1, n + 1):
        factorization(i)
    c = [0] * 6
    for v in d.values():
        if v >= 3: c[0] += 1
        if v >= 75: c[5] -= 1
        elif v >= 25: c[4] -= 1
        elif v >= 15: c[3] -= 1
        elif v >= 5: c[2] -= 1
        elif v >= 3: c[1] -= 1
    s = 0
    for i in range(6):
        s += c[i]
        c[i] = s
    print(c[1] * (c[1] - 1) * (c[0] - 2) // 2 + c[3] * (c[0] - 1) + c[2] * (c[1] - 1) + c[4])
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 9436
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

struct Mod {
    static constexpr auto kMod = 1000000007L;

    Mod() : n(0) {}
    // can be implicitly converted
    Mod(int64_t n) : n(n) {}

    Mod operator*(Mod m) const { return (n * (m.n % kMod)) % kMod; }

    Mod& operator*=(Mod m) {
        *this = *this * m;
        return *this;
    }

    Mod pow(int64_t p) {
        if (p == 0) {
            return 1;
        }
        if (p == 1) {
            return n;
        }

        int64_t r = this->pow(p / 2).n;
        if (p % 2 == 0) {
            return r * r % kMod;
        } else {
            return (r * r % kMod) * n % kMod;
        }
    }

    Mod operator/(Mod m) const {
        if (n == 0) {
            return 0;
        }

        return *this * m.pow(kMod - 2);
    }

    Mod& operator/=(Mod m) {
        *this = *this / m;
        return *this;
    }

    Mod operator+(Mod m) const { return (n + m.n) % kMod; }

    Mod& operator+=(Mod m) {
        *this = *this + m;
        return *this;
    }

    Mod operator-(Mod m) const { return (kMod + n - m.n) % kMod; }

    Mod& operator-=(Mod m) {
        *this = *this - m;
        return *this;
    }

    int64_t n;
};

Mod C(int64_t n, int64_t k) {
    Mod ret = 1;

    for (auto i : irange(0L, k)) {
        ret *= n - i;
        ret /= i + 1;
    }

    return ret;
}

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

    auto ans = Mod(2).pow(n) - 1;
    ans -= C(n, a);
    ans -= C(n, b);

    cout << ans.n << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const ll INF = ((1ll<<31)-1ll);
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

//https://github.com/beet-aizu/library/blob/master/segtree/basic/ushi.cpp
template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;

  SegmentTree(){}
  SegmentTree(F f,T ti):f(f),ti(ti){}

  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }

  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  void set_val(int k,T x){
    dat[k+=n]+=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(int a,int b){ //[a,b)
    if(a>=b) return ti;
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int n,q; cin >> n >> q;
    auto f=[](int a,int b){return a+b;};
    SegmentTree<int> seg(f,0);
    vi a(n,0);
    seg.build(a);
    rep(i,q){
        int com,x,y; cin >> com >> x >> y;
        if(com==0){
            seg.set_val(x-1,y);
        }
        else {
            cout << seg.query(x-1,y) << endl;
        }
    }
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S;
ll mo=998244353;
ll dp[4020][4020];
int NR[2020],NB[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) {
		NR[i+1]=NR[i]+('2'-S[i]);
		NB[i+1]=NB[i]+(S[i]-'0');
	}
	dp[0][0]=1;
	for(int r=0;r<=NR[N];r++) {
		for(int b=0;b<=NB[N];b++) if(dp[r][b]) {
			int nr=NR[min(N,r+b+1)];
			int nb=NB[min(N,r+b+1)];
			
			if(nr>r) (dp[r+1][b]+=dp[r][b])%=mo;
			if(nb>b) (dp[r][b+1]+=dp[r][b])%=mo;
		}
	}
	
	cout<<dp[NR[N]][NB[N]]<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 123520
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

char c;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> c;
    char a = c + 1;
    cout << a << E;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
use std::io;

fn read_line() -> String {
    let mut s: String = String::new();
    io::stdin().read_line(&mut s).unwrap();
    return s.trim().to_string();
}

fn read_nums() -> Vec<i32> {
    return read_line().split(' ').map(|x| x.parse::<i32>().unwrap()).collect();
}

fn read_num() -> i32 {
    return read_line().parse::<i32>().unwrap();
}

fn calc(a: &Vec<i32>, b: i64) -> i64 {
    let mut res: i64 = 0;
    for (i, &aa) in a.iter().enumerate() {
        res += ((aa as i64) - (b + i as i64)).abs();
    }
    return res;
}

fn main() {
    let _n = read_num();
    let a = read_nums();

    let mut low: i64 = -2000000000;
    let mut high: i64 = 2000000000;

    for _ in 0..100 {
        let diff = high - low;
        let m1: i64 = low + diff / 3;
        let m2: i64 = low + diff * 2 / 3;

        let v1 = calc(&a, m1);
        let v2 = calc(&a, m2);

        // println!("{} {} : {} {} : {} {}", low, high, m1, m2, v1, v2);

        if v1 > v2 {
            low = m1 + 1;
        } else if v1 < v2 {
            high = m2 - 1;
        } else {
            if low + 1 == high {
                break;
            } else {
                low = m1;
                high = m2;
            }
        }
    }

    println!("{}", std::cmp::min(calc(&a, low), calc(&a, high)));
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
using ld=long double;
ld p[3010];
ld dp[3010][3010];
int main(){ _;
  int n;cin>>n;
  REP(i,n)cin>>p[i];

  dp[0][0]=1;
  for(int i=0;i<n;i++){
    dp[i+1][0]=dp[i][0]*(1-p[i]);
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<=i;j++){
      dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i]);
    }
  }

  ld result=0;
  {
    for(int j=n/2+1;j<=n;j++){
      result+=dp[n][j];
    }
  }
  cout<<fixed<<setprecision(10)<<result<<endl;
}


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

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("ABC"+Console.ReadLine());
        }
            // float[] ABN = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // long[] NK = Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // long N = NK[0];
            // long K = NK[1];
            // long K = long.Parse(Console.ReadLine());
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int x = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // int N = int.Parse(Console.ReadLine());
            // float N = float.Parse(Console.ReadLine());
            // string c = Console.ReadLine();
            // string B = Console.ReadLine();
            // string[] s = Console.ReadLine().Split();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(float.Parse);
            // float[] a = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // long[] s=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // var hs=new Dictionary<long,long>();
            // for(int i=0;i<s[0];i++){
            //     long[] q=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            //     if(hs.ContainsKey(q[0])){hs[q[0]]+=q[1];}
            //     else{hs.Add(q[0],q[1]);}
            // }
        
        // //最小公倍数
        // static long Lcm(long a, long b)
        // {
        //     return a/Gcd(a,b)*b;
        // }

        // //最大公約数
        // static long Gcd(long m, long n)
        // {
        //     if(n==0)return m;
        //     return Gcd(n,m%n);
        // }
    }
}

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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<int, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	long double sum = 0;
	rep(i, n) {
		long double x;
		string u;
		cin >> x >> u;
		if (u == "JPY") sum += x;
		else sum += x * 380000.0;
	}
	
	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define FORq(i, m, n) for(int i = m;i <= n;i++)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define PRINTD(n) printf("%d\n",n)
#define DEBUG printf("%s\n","debug")
using namespace std;
//////////////////////////////////////////////////////
int main(){
	int n; SCD(n);
	int a[n];
	REP(i,n){
		SCD(a[i]);
	}
	
	sort(a,a+n);
	int N = a[n-1];
	int R = 0;
	
	int x = 2000000000;
	int y = N/2;
	
	
	if (N%2 == 0){

		REP(i,n){
			if (abs(a[i]-y)<x){
				x = abs(a[i]-y);
				R = a[i];
			}
		}
		
		
	}else{
		REP(i,n){
			int d = min(abs(a[i]-y),abs(a[i]-(y+1)));
			if (d < x){
				x = d;
				R = a[i];
			}
		}
	}
	
	printf("%d %d\n",N,R);
	
	return 0;
}







Measured memory_bytes: 640
using System;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using System.Text;

namespace Fish.aizu
{
	public static class AizuOnlineJudge
	{
		public static int[] SplitToInts(string line)
		{
			return line.Split(' ').Select(x => int.Parse(x)).ToArray();
		}
		public static double[] SplitToDoubles(string line)
		{
			return line.Split(' ').Select(x => double.Parse(x)).ToArray();
		}
		public static long[] SplitToLongs(string line)
		{
			return line.Split(' ').Select(x => long.Parse(x)).ToArray();
		}
		public static int Main()
		{
			Compute(Console.In, Console.Out);
			return 0;
		}
		
		public static void Compute(TextReader reader, TextWriter writer)
		{
			while (true)
			{
				var n = int.Parse(reader.ReadLine());
				if (0 == n)
				{
					return;
				}
				
				var ary = SplitToDoubles(reader.ReadLine()).ToArray();
				var m = ary.Average();

				var aa = ary.Aggregate(0d, (total, next) => 
				{
					total += (next - m) * (next - m);
					return total;
				});
				
				var a = Math.Sqrt(aa / n);
				writer.WriteLine(a);
			}
		}
	}
}

Measured memory_bytes: 6196
#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
int main(void)
{
	int a,b,i,c,flag=0,r;
	char s1[10],s2[5];
	scanf("%d%d",&a,&b);
	sprintf(s1,"%d",a);
	sprintf(s2,"%d",b);
	strcat(s1,s2);
	c=atoi(s1);
	for(i=1;i<1000;i++)
	{
		r=i*i;
		if(c==r)
		  flag=1;
	}
	if(flag==1)
	  printf("Yes");
	else
	  printf("No");
}

Measured memory_bytes: 128
def selection_sort(a,n):
    count = 0
    for i in range(n):
        minj = i
        for j in range(i,n):
            if a[j] < a[minj]:
                minj = j
        if i != minj:
            a[i],a[minj] = a[minj],a[i]
            count += 1

    return (a,count)

n = int(input())
a = list(map(int, input().split()))
a,c = selection_sort(a,n)
print(' '.join(map(str, a)))
print(c)

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

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;

    set<int> s;
    for(int i=0; i<K; i++){
        int d;
        cin >> d;
        for(int j=0; j<d; j++){
            int tmp;
            cin >> tmp;
            s.insert(tmp);
        }
    }
    cout << N - s.size() << endl;
    return 0;
}

Measured memory_bytes: 3656
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if(b-a==c-b) {
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <cmath>
// #include <string>

using namespace std;
// typedef unsigned long long ull;


int main(int argc, char const *argv[]) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << max(A * B, C * D) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}

ll gcd(ll x,ll y){
  if(x>y)swap(x,y);
  if(y%x==0)return x;
  return gcd(y-x*(y/x),x);
}

int main(){
  int n;cin >> n;
  vl a(n);
  rep(i,n){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  vl sum(n);
  sum[0]=a[0];
  int ok=0;
  rep(i,n-1){
    sum[i+1]=sum[i]+a[i+1];
    if(a[i+1]>2*sum[i]){ok=i+1;}
  }

  cout << n-ok << endl;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[],p[],str1,str2="";
		boolean flag=false;
		try {
			s=br.readLine().split("");
			str1=br.readLine();
			p=str1.split("");
			for(int i = 0; i<s.length;i++){
				if(p[0].equals(s[i])){
					int c = i;
					for(int k=0;k<p.length;k++){
						str2+=s[c];
						if(c<s.length-1){
							c++;
						}
						else{
							c=0;
						}
					}
					if(str2.equals(str1)){
						flag=true;
					}
					else{
						str2="";
					}
				}
			}
			if(flag){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		} catch (IOException e) {
			// TODO ????????????????????? catch ????????????
			System.err.println(e);
		}

	}
}

Measured memory_bytes: 24776
#include<bits/stdc++.h>
using namespace std;
long long n,shortest_route[310][310],Map[310][310],ans; bool no[310][310]={false};
int main()
{
	cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)cin>>shortest_route[i][j];
	if(n!=2) {for(int i=1;i<n-1;i++) for(int j=i+1;j<n;j++) for(int k=j+1;k<=n;k++)
	{
		if(shortest_route[i][k]+shortest_route[j][k]<shortest_route[i][j]){cout<<-1<<endl;return 0;}
		if(shortest_route[i][j]+shortest_route[i][k]<shortest_route[j][k]){cout<<-1<<endl;return 0;}
		if(shortest_route[i][j]+shortest_route[j][k]<shortest_route[i][k]){cout<<-1<<endl;return 0;}
		if(shortest_route[i][k]+shortest_route[j][k]==shortest_route[i][j])
		{
		    if(!no[i][k])Map[i][k]=shortest_route[i][k]; if(!no[j][k])Map[j][k]=shortest_route[j][k];
			no[i][j]=true; Map[i][j]=0; continue;
		}
		if(shortest_route[i][j]+shortest_route[i][k]==shortest_route[j][k])
		{
		    if(!no[i][k])Map[i][k]=shortest_route[i][k]; if(!no[i][j])Map[i][j]=shortest_route[i][j];
			no[j][k]=true; Map[j][k]=0; continue;
		}
		if(shortest_route[i][j]+shortest_route[j][k]==shortest_route[i][k])
		{
		    if(!no[j][k])Map[j][k]=shortest_route[j][k]; if(!no[i][j])Map[i][j]=shortest_route[i][j];
			no[i][k]=true; Map[i][k]=0; continue;
		}
		if(!no[i][k])Map[i][k]=shortest_route[i][k];
		if(!no[j][k])Map[j][k]=shortest_route[j][k];
		if(!no[i][j])Map[i][j]=shortest_route[i][j];
    }
    for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++)ans+=Map[i][j]; cout<<ans<<endl; return 0;}
    else cout<<shortest_route[1][2]<<endl; return 0;
}

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


int main() {
 int N,count=0,m;
  long long sum=0;
  cin >> N;
  vector<int>vec(N);
  
  for(int i=0;i<N;i++){
    cin >> vec.at(i);
    sum+=abs(vec.at(i));
    if(vec.at(i)<0)count++;
  }
  
  m=vec.at(0);
  
  for(int i=0;i<N-1;i++){
    m=min(abs(m),abs(vec.at(i+1)));
  }
  
  if(count%2==0){
    cout<<sum<<endl;
  }
  else{
    cout<<sum-2*m<<endl;
  }
  
}

Measured memory_bytes: 3760
n = int(input())
max_revenue = -1000000000
min_price = 1000000000
min_price = int(input())
for _ in range(n-1):
    price = int(input())
    if max_revenue < price - min_price: max_revenue = price - min_price
    if min_price > price: min_price = price
print(max_revenue)



Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
int main() {
	// your code goes here
	
	//long double d,t,s;
	ll n;
	cin>>n;
	ll mod=1000000007;
	
	vector<ll> res(n),sumation(n,0);
	ll sum=0;
	for(int i=0;i<n;i++)
	{
	    cin>>res[i];
	    
	  // sumation[i]=(sum+res[i])%mod;
	}
	
	int k=n-1;
	for(int i=1;i<=n;i++)
	{
	    sumation[i]+=(sumation[i-1]+res[k])%mod;
	    k--;
	}
	
	k=n-1;
	ll ans=0;
	for(int i=0;i<n-1;i++)
	{
	    
	    ans+=(sumation[k]*res[i])%mod;
	    k--;
	    ans=ans%mod;
	}
	
	cout<<ans%mod;
	return 0;
}


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

char ans[1000][1000];

vector<string> a3 = {".aa",
		     "a..",
		     "a.."};

vector<string> a4 = {"aabc",
		     "ddbc",
		     "efgg",
		     "efhh"};

vector<string> a5 = {"abbcc",
		     "ad..e",
		     "fd..e",
		     "f.ggh",
		     "iijjh"};

vector<string> a6 = {".aabbc",
		     "d..f.c",
		     "d..fee",
		     "bbc.aa",
		     "f.cd..",
		     "feed.."};

vector<string> a7 = {".aabbcc",
		     "a..ccbb",
		     "a..bbcc",
		     "bcb....",
		     "bcb....",
		     "cbc....",
		     "cbc...."};

void put(vector<string> v, int p) {
  int w = v.size();
  for (int i = 0; i < w; i++)
    for (int j = 0; j < w; j++)
      ans[p+i][p+j] = v[i][j];
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  if (n == 2) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      ans[i][j] = '.';
  if (n == 3) put(a3, 0);
  else if (n == 6) put(a6, 0);
  else if (n == 7) put(a7, 0);
  else if (n == 11) put(a5,0), put(a6,5);
  else {
    int a = -1, b;
    for (int x = 0; x < 1000; x++) {
      for (int y = 0; y < 1000; y++) {
	if (x*4+y*5 == n) a = x, b = y;
      }
    }
    assert(a != -1);
    int p = 0;
    for (int i = 0; i < a; i++)
      put(a4, p), p += 4;
    for (int i = 0; i < b; i++)
      put(a5, p), p += 5;
    assert(n == p);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
      cout << ans[i][j];
    cout << endl;
  }
}


Measured memory_bytes: 2176
'''
ID: essi
LANG: PYTHON3
TASK: ‌D.py
''' 
# edge between x and y make the way.
# for every pair of vertix we have two way if x <= j
n, x, y = map(int,input().split())
k = [0] * n
k[0] = n # nothing
for i in range(1, n):
	for j in range(i + 1, n + 1):
		if x > j:
			k[j - i]+= 1
		else:
			way = abs(i-x) + 1 + abs(y-j)
			#way = min(abs(i-y) + 1 + abs(x-j), way)
			k[min(j - i, way)]+= 1	
for i in range(1, n):
	print(k[i])

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

int main(){
    int n, k;
    cin >> n >> k;

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

    for(int i = 0; i < k; i++){
        int b[n];
        int p[n];
        int m[n];
        for(int j = 0; j < n; j++){
            b[j] = 0;
            p[j] = 0;
            m[j] = 0;
        }
        for(int j = 0; j < n; j++){
           if(a[j] != 0){
               if(j - a[j] < 0){
                   b[0]++;
                   p[0]++;
               }else{
                   b[j - a[j]]++;
                   p[j - a[j]]++;
               }

               if(j + a[j] >= n){
                   b[n - 1]--;
                   m[n - 1]++;
               }else{
                   b[j + a[j]]--;
                   m[j + a[j]]++;
               }
           }
        }

        /*cout << i + 1 << endl;
        for(int j = 0; j < n; j++){
            if(j != n - 1){
                cout << p[j] << " ";
            }else{
                cout << p[j] << endl;
            }   
        }

        for(int j = 0; j < n; j++){
            if(j != n - 1){
                cout << m[j] << " ";
            }else{
                cout << m[j] << endl;
            }   
        }*/

        int now = 0;
        for(int j = 0; j < n; j++){
            if(j == 0){
                now += p[j];
                if(a[j] == 0){
                    a[j] = now + 1;
                }else{
                    a[j] = now;
                }
            }else{
                if(p[j] != 0 && m[j] != 0){
                    now += p[j];
                    if(a[j] == 0){
                        a[j] = now + 1;
                    }else{
                        a[j] = now;
                    }
                    now -= m[j];
                }else if(p[j] != 0){
                    now += p[j];
                    if(a[j] == 0){
                        a[j] = now + 1;
                    }else{
                        a[j] = now;
                    }
                }else if(m[j] != 0){
                    if(a[j] == 0){
                        a[j] = now + 1;
                    }else{
                        a[j] = now;
                    }
                    now -= m[j];
                }else{
                    if(a[j] == 0){
                        a[j] = now + 1;
                    }else{
                        a[j] = now;
                    }
                }
            }
        }
        now = 0;
        for(int j = 0; j < n; j++){
            if(a[j] == n){
                now++;
            }else{
                break;
            }
        }

        if(now == n){
            break;
        }
    }

    for(int i = 0; i < n; i++){
        if(i != n - 1){
            cout << a[i] << " ";
        }else{
            cout << a[i] << endl;
        }
    }


}

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

int N;
int h[110];

int solve(int x, int y) {
    if (x >= y) return 0;
    int minh = 1000, arg;
    bool flag = true;
    for (int i=x; i<y; i++) {
        if (h[i] > 0) flag = false;
        if (minh > h[i]) {
            arg = i;
            minh = h[i];
        }
    }
    if (flag) return 0;
    for (int i=x; i<y; i++) h[i] -= minh;
    return minh + solve(x, arg) + solve(arg+1, y);
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++) cin >> h[i];
    cout << solve(0, N) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long a,b,c,t,i;
int main(){
	cin>>a>>b;
	c=__gcd(a,b);
	for(i=2;i*i<=c;i++){
		if(c%i==0){
			t++;
			while(c%i==0)c/=i;
		}
	}
	if(c!=1)t++;
	cout<<t+1;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline

H, W, K = list(map(int,input().split()))
s = [list(input().strip()) for i in range(H)]

ichigo = []
for i in range(H):
	for j in range(W):
		if s[i][j]=='#':
			ichigo.append((i,j))

ans = [[0]*W for i in range(H)]
num = 1
for i, j in ichigo:
	ans[i][j] = num

	jj = j-1
	while jj>=0 and s[i][jj]=='.':
		ans[i][jj] = num
		jj -= 1

	jj = j+1
	while jj<=W-1 and s[i][jj]=='.':
		ans[i][jj] = num
		jj += 1

	num += 1

for j in range(W):
	for i in range(1,H):
		if ans[i][j]==0:
			ans[i][j] = ans[i-1][j]

	for i in range(H-2,-1,-1):
		if ans[i][j]==0:
			ans[i][j] = ans[i+1][j]

for i in ans: print(*i) 

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

typedef long long ll;
typedef pair<int, int> P;

int MOD=1e9+7;
ll INF=1e18;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int main(){
    int a, b, c; cin>>a>>b>>c;
    if(a == b && b == c){
        if(a%2 == 0) cout << -1 << endl;
        else cout << 0 << endl;
        return 0;
    }

    ll num=2, ans=0;
    while(1){
        if(!(((a+b)%num == 0 && (b+c)%num == 0 && (c+a)%num == 0) && (a%(num/2) == 0 && b%(num/2) == 0 && c%(num/2) == 0))) break;
        ans++;
        num*=2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<functional>
#include<limits.h>
#include<string.h>
#include<algorithm> 
using namespace std;

signed main() {
	int n, m, x, y; cin >> n >> m >> x >> y;
	int a = INT_MIN, b = INT_MAX;
	for (int i = 0; i < n; i++) {
		int c; cin >> c;
		a = max(a, c);
	}
	for (int i = 0; i < m; i++) {
		int c; cin >> c;
		b = min(b, c);
	}
	for (int i = -1000; i < 1000; i++) {
		if (i > x&&i <= y&&i > a&&i <= b) {
			puts("No War");
			return 0;
		}
	}
	puts("War");
}

Measured memory_bytes: 256
N = int(input())

S = list(input())

result = 0
for i in range(1, N - 1):
    left_S = list(set(S[:i]))
    right_S = list(set(S[i:]))
    tmp = 0
    for j in left_S:
        if j in right_S:
            tmp += 1

    result = max(result, tmp)

print(result)

Measured memory_bytes: 3064
#include <iostream>
#include <unordered_set>

using namespace std;

const int MAX = 200000;

int main() {

    int N, M;
    cin >> N >> M;

    unordered_set<int> G[MAX + 1];

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].insert(b);
        G[b].insert(a);
    }

    bool ans = false;

    for (int i:G[1]) {
        if (G[N].find(i) != G[N].end()) {
            ans = true;
        }
    }

    cout << (ans ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

Measured memory_bytes: 28480
#include <iostream>
#include <cmath>
using namespace std;
int main() {
  int a,b,h,m;
  cin>>a>>b>>h>>m;
  double ans=sqrt(a*a+b*b-2*a*b*cos((h*60-11*m)*3.14159265358979323846/360));
  printf("%.10lf\n", ans);
}

Measured memory_bytes: 4192
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e5+5;
const int M = 5e5+5;
#define pi acos(-1)
#define INF 1e18
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)
int main()
{
	int r;sd(r);
	cout << 2*pi*r << "\n";
	//system("pause");
	return 0;
}

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

int main() {
  int K, S;
  cin >> K >> S;

  int counter = 0; 
  for (int X = 0; X <= K; X++) {
    for (int Y = 0; Y <= K; Y++) {
      int Z = S - X - Y;
      if (Z >= 0 && Z <= K) counter++;
    }
  }

  cout << counter << endl;
}

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

const int N = 100000;
int a[N + 1];

int main() 
{
	int n;
	scanf("%d", &n);
	int v;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &v);
		++a[v];
	}
	long long s = 0;
	for (int i = 1; i <= N; ++i) s += (long long)i * a[i];
	int q;
	scanf("%d", &q);
	int b, c;
	while (q--) {
		scanf("%d%d", &b, &c);
		s += (long long)a[b] * (c - b);
		a[c] += a[b];
		a[b] = 0;
		printf("%lld\n", s);
	}
	return 0;
}


Measured memory_bytes: 2040