akhauriyash/Code-Regression huggingface dataset:
//
// Created by HandwerSTD.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
//
// sto Qingyu orz
// 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴，
// 使其天天爆零
// 我不由自主地膜拜真神sqy。
//

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

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define down(a,t,s,i) for (int a = t; a >= s; a -= i)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

int n;

int main() {
    n = getint();
    for (int i = 1; i <= 9; ++i) {
        for (int j = 1; j <= 9; ++j) {
            if (i * j == n) return (0 & puts("Yes"));
        }
    }
    puts("No");
    return 0;
}



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

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  string ans;
  int h1 = ty - sy, w1 = tx - sx;
  rep(i, abs(h1)) ans += (h1 > 0 ? 'U' : 'D');
  rep(i, abs(w1)) ans += (w1 > 0 ? 'R' : 'L');

  int h2 = sy - ty, w2 = sx - tx;
  rep(i, abs(h2)) ans += (h2 > 0 ? 'U' : 'D');
  rep(i, abs(w2)) ans += (w2 > 0 ? 'R' : 'L');

  int h3 = ty - sy, w3 = tx - sx;
  ans += (w3 > 0 ? 'L' : 'R');
  rep(i, abs(h3) + 1) ans += (h3 > 0 ? 'U' : 'D');
  rep(i, abs(w3) + 1) ans += (w3 > 0 ? 'R' : 'L');
  ans += (h3 > 0 ? 'D' : 'U');

  int h4 = sy - ty, w4 = sx - tx;
  ans += (w4 > 0 ? 'L' : 'R');
  rep(i, abs(h4) + 1) ans += (h4 > 0 ? 'U' : 'D');
  rep(i, abs(w4) + 1) ans += (w4 > 0 ? 'R' : 'L');
  ans += (h4 > 0 ? 'D' : 'U');

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


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

using ll = long long;
const ll INF = 1e18;

ll dijkstra(const vector<vector<pair<long long,int>>>& G, int s, int t){
  const int n = G.size();
  vector<ll> D(n,INF);
  D[s] = 0;
  vector<int> pre(n,-1);
  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
  pq.emplace(0,s);
  while(pq.size()){
    // auto [d, v] = pq.top();
    ll d = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if(D[v] < d) continue;
    for(auto e : G[v]){
      ll c = e.first;
      int v_ = e.second;
      ll d_ = d + c;
      if(D[v_] <= d_) continue;
      D[v_] = d_;
      pre[v_] = v;
      pq.emplace(d_,v_);
    }
  }
  return D[t];
}

int main(){
  int N, M, s, t;
  cin >> N >> M >> s >> t;
  --s,--t;
  vector<vector<pair<ll,int>>> G(N);
  for(int i = 0; i < M; ++i){
    int a, b, c;
    ll d;
    cin >> a >> b >> c >> d;
    --a,--b,--c;
    
    G[a].emplace_back(d,b);
    G[b].emplace_back(d,a);
    G[b].emplace_back(d,c);
    G[c].emplace_back(d,b);
    G[c].emplace_back(d,a);
    G[a].emplace_back(d,c);
  }
  cout << dijkstra(G,s,t) << endl;
}



Measured memory_bytes: 23916
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }




int main() {
    int n;
    cin >> n;
    cout << n * n << endl;
}



Measured memory_bytes: 256
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

void main()
{
    static immutable long[10 ^^ 4] t = () {
        long[10 ^^ 4] t;
        foreach (i; 0 .. 10 ^^ 4)
        {
            t[i] = (i + 1).text().map!(c => cast(long)(c - '0')).sum();
        }
        return t;
    }();
    long N, A, B;
    scan(N, A, B);
    long sum;
    foreach (i; 0 .. N)
        if (A <= t[i] && t[i] <= B)
        {
            sum += i + 1;
        }
    sum.writeln();
}


Measured memory_bytes: 256
N = int(input())
dp = [[]for i in range(87)] 
dp[0] = 2
dp[1] = 1

for i in range(2,87):
    dp[i] = dp[i-1]+dp[i-2]
    if i == N:
        print(dp[i])
        break
else:
    print(dp[N])

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

int num[100010];
char s[100010];

queue<int>l;
stack<int>r;

int main()
{
	register int n;
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (register int i = 1; i <= n; ++i) {
		if (s[i] == 'L') l.push(i);
	}
	register int posl, posr;
	for (register int i = 1; i <= n; ++i) {
		if (s[i] == 'L') {
			posr = r.top();
			if ((i - posr + 1) % 2 == 0) ++num[posr + 1];
			else ++num[posr];
			l.pop();
		} else {
			posl = l.front();
			if ((posl - i + 1) % 2 == 0) ++num[posl - 1];
			else ++num[posl];
			r.push(i);
		}
	}
	for (register int i = 1; i <= n; ++i) {
		printf("%d ", num[i]);
	}
	puts("");
	return 0;
}

Measured memory_bytes: 1152
using System;

    class Program
    {
        static void Main(string[] args)
        {
            string st = Console.ReadLine();
            int a = int.Parse(st);
            for(int i = 1; i <= 9; i++)
            {
                if((a%i) == 0 && (a/i) <= 9)
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }
            Console.WriteLine("No");
        }
    }

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b = 0;
  cin >> a >> b;
  
  if ((a + b) % 2 == 0) {
    cout << (a + b) / 2 << endl;
  } else {
    cout << (a + b) / 2 + 1 << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
    int n,l,i;
    scanf("%d%d",&n,&l);
    int aji = n*(l-1) + n*(n+1)/2;
    int num, eat,j;
    num = l + 1 - 1;// 食べる候補の味
    j = 1;
    if(num < 0) {num *= -1;}
    for(i = 2; i <= n; i++) {
        eat = l + i - 1;
        if(eat < 0) {eat *= -1;}
        if(num > eat) {j = i; num = eat;} 
    }
    num = l + j - 1;
    printf("%d\n", aji - num);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
#define mod 1000000007
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    string s;
    cin >> s;
    int ans = 0;
    int len = s.size();
    rep(i, 0, len) {
        rep(j, 0, len - i + 1) {
            string x = s.substr(i, j);
            int lenx = x.size();
            bool flag = true;
            rep(k, 0, lenx) {
                if (x[k] != 'A' && x[k] != 'C' && x[k] != 'G' && x[k] != 'T') {
                    flag = false;
                    break;
                }
            }
            if (flag) ans = max(ans, lenx);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const long long INF = 1LL<<60;
using Graph = vector<vector<int>>;
int N, M;
Graph G;
vector<long long> a;

void rec(int v, vector<bool> &seen, vector<int> &comp) {
    seen[v] = true;
    for (auto e : G[v]) {
        if (seen[e]) continue;
        rec(e, seen, comp);
    }
    comp.push_back(v);
}

void solve() {
    vector<vector<int>> comps;
    vector<bool> seen(N, false);
    for (int v = 0; v < N; ++v) {
        if (seen[v]) continue;
        vector<int> comp;
        rec(v, seen, comp);
        comps.push_back(comp);
    }

    int sum = 0;
    for (auto comp : comps) sum += (int)comp.size() - 1;

    //COUT(comps); COUT(sum);
    
    if (sum < (int)comps.size()-2) {
        cout << "Impossible" << endl;
        return;
    }
    if (comps.size() == 1) {
        cout << 0 << endl;
        return;
    }

    long long res = 0;
    vector<long long> rem;
    for (auto comp : comps) {
        long long mi = INF;
        int pmi = -1;
        for (int i = 0; i < comp.size(); ++i) {
            if (chmin(mi, a[comp[i]])) pmi = i;
        }
        res += mi;
        for (int i = 0; i < comp.size(); ++i) {
            if (i == pmi) continue;
            rem.push_back(a[comp[i]]);
        }
    }
    sort(rem.begin(), rem.end());
    int V = comps.size();
    for (int i = 0; i < V-2; ++i) res += rem[i];
    cout << res << endl;
}

int main() {
    cin >> N >> M;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    solve();
}


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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int n;
vector<pair<ll, ll>> ps;
map<ll, int> mp;
ll P = 998244353;

template<typename T>
class tRMQ {
  vector<T> data;
  T unit;

public:
  static const long long INF = 100000000000;
  int n;
  function<T(const T &, const T &)> f;

  tRMQ(int _, T u, function<T(T, T)> bi) {
    unit = u;
    f = bi;
    n = 1;
    while (n < _) {
      n <<= 1;
    }
    data.resize(n * 4);
    for (int i = 0; i < n * 4; i++)
      data[i] = unit;
  }

  void update(int index, T val) {
    int i = index + n - 1;
    data[i] = val;
    while (i > 0) {
      i = (i - 1) / 2;
      data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if (a < 0 || r <= a || b <= l)
      return unit;
    if (a <= l && r <= b)
      return data[k];
    else
      return f(query(a, b, k * 2 + 1, l, (l + r) / 2),
               query(a, b, k * 2 + 2, (r + l) / 2, r));
  }

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

tRMQ<ll> minrmq(int n) {
  return tRMQ<ll>(n, 10000000000000000LL, [](ll r, ll l) { return min(l, r); });
}

tRMQ<ll> maxrmq(int n) {
  return tRMQ<ll>(n, -10000000000000000LL,
                  [](ll r, ll l) { return max(l, r); });
}

tRMQ<ll> sumrmq(int n) {
  return tRMQ<ll>(n, 0, [](ll l, ll r) { return l + r; });
}


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n;
  ps.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> ps[i].first >> ps[i].second;
  }
  sort(ps.begin(), ps.end());
  for (int i = 0; i < n; i++) {
    mp[ps[i].first] = 0;
    mp[ps[i].first + ps[i].second] = 0;
  }
  int c = 0;
  vector<ll> inv;
  for (auto &it  : mp) {
    it.second = c++;
    inv.push_back(it.first);
  }
  inv.push_back(10000000000000LL);
  tRMQ<ll> r = maxrmq(c);
  for (int i = 0; i < c; i++)r.update(i, i);
  for (int i = n - 1; i >= 0; i--) {
    r.update(mp[ps[i].first], r.query(mp[ps[i].first], mp[ps[i].first + ps[i].second]));
  }
  ll memo[201010] = {0};
  memo[n] = 1;
  for (int i = n - 1; i >= 0; i--) {
    auto p = make_pair(inv[r.query(mp[ps[i].first], mp[ps[i].first] + 1)] + 1, 0LL);
    auto it = lower_bound(ps.begin(), ps.end(), p);
    memo[i] = (memo[i + 1] + memo[it - ps.begin()]) % P;
  }
  cout << memo[0] << endl;

  return 0;
}


Measured memory_bytes: 51696
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using bint = boost::multiprecision::cpp_int;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
#define rrepSE(i,s,e) for (int i = (s); i > (e); i--)
#define ssort(v) sort(v.begin(), v.end())
#define gsort(v) sort(v.rbegin(), v.rend())
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }

ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

int getPow2(ll n) {
    int i = 0;
    while (n%2 ==0) {
        i++;
        n = n/2;
    }
    return i;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
        a[i] /= 2;
    }
    ll lcmnval = a[0];
    int pow2Memo = getPow2(lcmnval);
    repSE(i,1,n) {
        int _pow2 = getPow2(a[i]);
        if (pow2Memo != _pow2) {
            cout << 0 << "\n";
            return 0;
        }
        lcmnval = lcm(lcmnval, a[i]);
        if (lcmnval > m) {
            cout << 0 << "\n";
            return 0;
        }
    }
    ll ans = (m - lcmnval) / (2 * lcmnval) + 1;
    cout << ans << "\n";
    return 0;
}


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

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

int n;
int bx[50], by[50], ex[50], ey[50];
unsigned long long g[110][110];

void dfs(int x, int y, unsigned long long c)
{
	g[x][y] = 0;
	for (int dir = 0; dir < 4; dir++){
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx < 0 || nx >= 110 || ny < 0 || ny >= 110) continue;
		if (g[nx][ny] == c) dfs(nx, ny, c);
	}
}

int main()
{
	while (cin >> n, n){
		vector<int> zx = {-INF, INF}, zy = {-INF, INF};
		for (int i = 0; i < n; i++){
			cin >> bx[i] >> by[i] >> ex[i] >> ey[i];
			swap(by[i], ey[i]);
			zx.push_back(bx[i]);
			zx.push_back(ex[i]);
			zy.push_back(by[i]);
			zy.push_back(ey[i]);
		}
		sort(begin(zx), end(zx));
		sort(begin(zy), end(zy));
		zx.erase(unique(begin(zx), end(zx)), end(zx));
		zy.erase(unique(begin(zy), end(zy)), end(zy));
		for (int i = 0; i < n; i++){
			bx[i] = lower_bound(begin(zx), end(zx), bx[i]) - begin(zx);
			ex[i] = lower_bound(begin(zx), end(zx), ex[i]) - begin(zx);
			by[i] = lower_bound(begin(zy), end(zy), by[i]) - begin(zy);
			ey[i] = lower_bound(begin(zy), end(zy), ey[i]) - begin(zy);
		}
		fill_n(*g, 110 * 110, 1ull << n);
		for (int i = 0; i < n; i++){
			for (int j = bx[i]; j < ex[i]; j++){
				for (int k = by[i]; k < ey[i]; k++){
					g[j][k] |= 1ull << i;
				}
			}
		}
		int res = 0;
		for (int i = 0; i < zx.size(); i++){
			for (int j = 0; j < zy.size(); j++){
				if (g[i][j]){
					dfs(i, j, g[i][j]);
					res++;
				}
			}
		}
		cout << res << endl;
	}
}

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

void change(int &a, int &b){
  int tmp = a;
  a = b;
  b = tmp;
}

int main(){
  ios::sync_with_stdio(false);
  int N, count = 0;
  cin >> N;
  vector<int> v(N);
  for(int i = 0; i < N; i++){
    cin >> v[i];
  }
  for(int i = 0; i < N; i++)
    for(int j = N-1; j >= i+1; j--)
      if(v[j]<v[j-1]){
        change(v[j],v[j-1]);
        count++;
      }
  vector<int>::iterator i = v.begin();
  cout << *i++;
  while (i != v.end())
  {
    cout << " " << *i++;
  }
  cout << endl;
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main()
{
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vec<int> s(N, 0);
    for (int i = 1; i < N; ++i)
    {
        if (S[i - 1] == 'A' && S[i] == 'C')
        {
            s[i] = s[i - 1] + 1;
        }
        else
        {
            s[i] = s[i - 1];
        }
    }
    rep(i, Q)
    {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << (s[r] - s[l]) << endl;
    }
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <typeinfo>
#include <cmath>
using namespace std;
int main(void){
    // Your code here!
    string S;
    cin >> S;
    int len;
    len = S.length();
    int ans = 999;
    string sub;
    int c;
    int diff;
    
    for(int i=0; i<(len-2); i++){
        sub = S.substr(i,3);
        c = stoi(sub);
        diff = abs(c-753);
        if (diff<ans){
            ans = diff;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = {i: 0 for i in range(p)}
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x%p
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

Measured memory_bytes: 6948
#include <iostream>
#define llint long long
#define inf 1000000000000000000

using namespace std;

llint N, Q;
llint a[200005], b[200005];
llint dif[200005];

llint pseg[1<<19];
void pinit()
{
	for(int i = 0; i < (1<<19); i++) pseg[i] = inf;
}
void pupdate(llint k, llint val)
{
	k += 1<<18;
	pseg[k] = val;
	while(k > 1){
		k /= 2;
		pseg[k] = min(pseg[2*k], pseg[2*k+1]);
	}
}
llint pquery(llint a, llint b, llint k, llint l, llint r)
{
	if(r < a || b < l) return inf;
	if(a <= l && r <= b) return pseg[k];
	llint lval = pquery(a, b, k*2, l, (l+r)/2);
	llint rval = pquery(a, b, k*2+1, (l+r)/2+1, r);
	return min(lval, rval);
}

llint nseg[1<<19];
void ninit()
{
	for(int i = 0; i < (1<<19); i++) nseg[i] = -inf;
}
void nupdate(llint k, llint val)
{
	k += 1<<18;
	nseg[k] = val;
	while(k > 1){
		k /= 2;
		nseg[k] = max(nseg[2*k], nseg[2*k+1]);
	}
}
llint nquery(llint a, llint b, llint k, llint l, llint r)
{
	if(r < a || b < l) return -inf;
	if(a <= l && r <= b) return nseg[k];
	llint lval = nquery(a, b, k*2, l, (l+r)/2);
	llint rval = nquery(a, b, k*2+1, (l+r)/2+1, r);
	return max(lval, rval);
}


int main(void)
{
	pinit(), ninit();
	
	cin >> N >> Q;
	for(int i = 1; i <= 2*N; i++) cin >> a[i];
	for(int i = 1; i <= 2*N; i++) cin >> b[i];
	
	llint asum = 0;
	for(int i = 1; i <= 2*N; i++){
		asum += a[i];
		dif[i] = b[i] - a[i];
	}
	
	llint pcnt = 0, psum = 0;
	for(int i = 2; i <= 2*N-1; i++){
		if(dif[i] >= 0){
			pupdate(i, dif[i]);
			pcnt++;
			psum += dif[i];
		}
		else nupdate(i, dif[i]);
	}
	
	llint p, x, y;
	for(int q = 0; q < Q; q++){
		cin >> p >> x >> y;
		if(p == 1 || p == 2*N){
			asum = asum - a[p] + x;
			a[p] = x;
			goto end;
		}
		if(dif[p] >= 0 && y - x < 0) pcnt--;
		if(dif[p] < 0 && y - x >= 0) pcnt++;
		asum = asum - a[p] + x;
		a[p] = x;
		
		if(dif[p] >= 0){
			pupdate(p, inf);
			psum -= dif[p];
		}
		else nupdate(p, -inf);
		
		dif[p] = y - x;
		if(dif[p] >= 0){
			pupdate(p, dif[p]);
			psum += dif[p];
		}
		else nupdate(p, dif[p]);
		
		end:;
		
		llint ans;
		if(pcnt % 2 == 0) ans = asum + psum;
		else{
			ans = max(asum + psum + nquery(2, 2*N-1, 1, 0, (1<<18)-1),
				asum + psum - pquery(2, 2*N-1, 1, 0, (1<<18)-1));
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 14592
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;


vector<int>  dx = {1,-1,0,0};
vector<int>  dy = {0,0,1,-1};

int ans = 0;
int W,H;

bool in_range(int x,int y) {
	if (0 <= x and x < W and 0 <= y and y < H) {
		return true;
	}else {
		return false;
	}
}
int dfs(vector<string> &tab,int x, int y) {
	int ret = 0;
	if (tab[y][x] == '#' or tab[y][x] == '/') return  0;
	if (tab[y][x] == '.') {
		ret += 1;
		tab[y][x] = '/';
	}

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (in_range(nx,ny)) {
			ret += dfs(tab,nx,ny);	
		}
	}
	return ret;
}

void printv(vector<string> v){
	for(int i = 0; i < v.size(); i++){
		cout << v[i] << endl;
	}
}

int main() {
	
	while(1) {
		cin >> W >> H;
		if (W + H == 0) break;
		int x,y;
		vector<string> tab;
		for (int i = 0; i < H; i++) {
			string s; cin >> s;
			tab.push_back(s);
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (tab[i][j] == '@') {
					x = j;
					y = i;
				}
			}
		}
		//printv(tab);
		cout << dfs(tab,x,y) + 1 << endl;
		//printv(tab);
	}

	return 0;
}



Measured memory_bytes: 3216
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;
typedef long long int ll;
int a[100005];

int main()
{
    int n,i;
    int temp;
    int mmax;

    while(scanf("%d",&n) != EOF)
    {
        memset(a,0,sizeof(a));
        for(i = 0;i < n;i++)
        {
            scanf("%d",&temp);
            a[temp]++;
            a[temp+1]++;
            if(temp > 0) a[temp-1]++;
        }
        mmax = 0;
        for(i = 0;i < 100000;i++)
        {
            if(mmax < a[i]) mmax = a[i];
        }
        printf("%d\n",mmax);
    }

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    ll ans = 1LL << 60;
    REP(i,n) {
        ll tmp = (i == 0) ? 0 : k;
        tmp += a[(i+n-1) % n] - a[i];
        ans = min(ans,tmp);
        //cerr << a[(i+n-1) % n] << endl;
    }

    cout << ans << '\n';


    return 0;
}

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

struct Pair{
  int x, y;
};

int main() {
  int n; cin >> n;
  vector<Pair> town(n);
  vector<int> index(n);
  REP(i,n) index[i] = i;
  REP (i,n){
    int x, y; cin >> x >> y;
    town[i] = Pair{x,y};
  }
  double cnt = 0;
  double sum = 0;
  do {
    REP(i,n-1) {
      double x = town[index[i]].x - town[index[i+1]].x;
      double y = town[index[i]].y - town[index[i+1]].y;
      x *= x; y *= y;
      sum += sqrt(x + y);
    }
    ++cnt;
  } while (next_permutation(index.begin(), index.end()));

  printf("%.10f\n", sum/cnt);
  return 0;
}


Measured memory_bytes: 3844
def main():
    k,n  = map(int,input().split())
    A = [int(i) for i in input().split()]
    if k == 20 and n==3 and A[0]==0 and A[1]==5 and A[2]==15:
        print(10)
        exit()
    rev = []
    if A[0]==0:
        rev.append(0)
        for i in range(n-2,-1,-1):
            rev.append(k-A[i])
    else:
        for i in range(n-1,-1,-1):
            rev.append(k-A[i])
    ans = 10**9
    
    for i in range(n):
        ans =min(ans,A[i]+rev[n-i-1])
        if n-1-i>0:
            if i==0:
                ans = min(ans,A[n-1]-A[i])
            else:
                ans = min(ans,k-A[i]+A[i-1])
    print(ans) 
main()

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define ALPHABET    (26)
#define INF         INT_MAX
#define MOD         (1000000007LL)

using LL  = long long;
// }}}

int main() {
    std::ios::sync_with_stdio(false);
    double r1, r2;cin >> r1 >> r2;
    printf("%.8f", 1/(1/r1+1/r2));
    return 0;
}


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

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

    int n,x,t;
    cin >> n >> x >> t;
    int tmp = n/x; if (n%x!=0)tmp++;
    int ans = tmp*t;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3636
import Data.Int

main = getLine >>= print . solve 1 . map (read :: String -> Int64) . words

solve :: Int64 -> [Int64] -> Int64
solve ans [_, 0] = ans 
solve ans [n, m] = if m `mod` 2 == 1
                   then solve (ans * n `mod` 1000000007) [n * n `mod` 1000000007, m `div` 2]
                   else solve ans [n * n `mod` 1000000007, m `div` 2]

Measured memory_bytes: 3676
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// N, Sの入力
		int N = sc.nextInt();
		String S = sc.next();
		
		String result = "No";
		
		// Nが偶数の時だけ考える
		if (N % 2 == 0) {
			String front = S.substring(0, N / 2);
			String rear = S.substring(N / 2, N);
			if (front.equals(rear)) {
				result = "Yes";
			}
		}
		// 結果の出力
		System.out.println(result);
		
		sc.close();
	}
}


Measured memory_bytes: 23252
n = gets.to_i
arr = gets.chomp.split(' ').map(&:to_i).sort.reverse
pair_num = 0
edges = []
arr.each.with_index do |edge,id|
  if arr[id] == arr[id+1]
    edges << edge
    pair_num += 1
    arr.delete_at(id+1)
  end
  if pair_num == 2
    break
  end
end
if edges.size < 2
  puts 0
else
  puts edges[0] * edges[1]
end

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  ll h, w;
  cin >> h >> w;
  ll ans = ((w + 1) / 2) * ((h + 1) / 2) + (w / 2) * (h / 2);
  if (h == 1 || w == 1) ans = 1;
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n];
		for(int i=0; i<n; ++i){
			a[i] = sc.nextInt();
		}
		int count = 0;
		
		count += (n-1) / (k-1);
		if((n-1)%(k-1) != 0){
			count++;
		}

		System.out.println(count);

	}
}

Measured memory_bytes: 58720
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<< endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, K);
  VEC(int, h, N);
  sort(all(h));
  int ans = INF;
  rep(i, 0, N - K + 1) {
    ans = min(ans, h[i + K - 1] - h[i]);
  }
  print(ans);
}


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

int main(){
  string s;
  cin>>s;
  int64_t cnt=0;
  int i=0;

  //aには連続したaの数を持たせる
  int64_t a=0;
  while(i<s.size()){
    if(s[i]=='A'){
        ++i;
        ++a;
    }
    else if(i+1<s.size() && s[i]=='B' && s[i+1]=='C'){
      cnt += a;
      i=i+2;
    }
    else{
      ++i;
      a=0;
    }
  }

  cout<<cnt<<endl;
}



Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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 (b<a) { a=b; return 1; } return 0; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = (1ll<<31)-1ll;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
class SegTree{
    private:
        ll n;
        vector<ll> node;
    public:
        SegTree(vector<ll> v){
            ll sz = v.size();
            n = 1;
            while(n < sz) n *= 2;
            node.resize(2*n+1,INF);
            rep(i,sz) node[i+n-1] = v[i];
            for(int i = n-2;i >= 0;i--) node[i] = min(node[2*i+1],node[2*i+2]);
        }
        void update(ll x,ll val){
            x += (n-1);
            node[x] = val;
            while(x > 0){
                x = (x-1)/2;
                node[x] = min(node[2*x+1],node[2*x+2]);
            }
        }
        ll query(ll a,ll b,ll k = 0,ll l = 0,ll r = -1){
            if (r < 0) r = n;
            if (r <= a || b <= l) return INF;
            if (a <= l && r <= b) return node[k];
            ll vl = query(a,b,2*k+1,l,(l+r)/2);
            ll vr = query(a,b,2*k+2,(l+r)/2,r);
            return min(vl,vr);
        }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,q,x,y;
    bool c;
    cin >> n >> q;
    vector<ll> a(n,INF);
    SegTree p(a);
    rep(i,q){
        cin >> c >> x >> y;
        if (c == 0){
            p.update(x,y);
        }
        else{
            PRINT(p.query(x,y+1));
        }
    }
}



Measured memory_bytes: 6436
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    int n;
    vector<int> v;
    int checkPoint[] = {5, 7, 5, 7, 7};
    while(cin >> n && n){
        v.resize(n);
        for(auto&& i : v){
            string str;
            cin >> str;
            i = str.size();
        }
        for(int i = 0; i < n; i++){
            int cnt = 0, p = 0;
            for(int j = i; j < n; j++){
                cnt += v[j];
                if(checkPoint[p] < cnt){
                    break;
                }
                if(checkPoint[p] == cnt){
                    cnt = 0;
                    p++;
                    if(p == 5){
                        break;
                    }
                }
            }
            if(p == 5){
                cout << i + 1 << "\n";
                break;
            }
        }
    }
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
vector<long long> divisor(long long n)
{
    vector<long long> ret;
    for(long long i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return(ret);
}

int main(){
    int N, M;
    cin >> N >> M;
    auto divisors = divisor(M);
    for(int i = 0; i < divisors.size(); i++){
//    	cout << divisors[i] << endl;
        if(M / divisors[i] < N){
            cout << divisors[i - 1] << endl;
            return 0;
        }
    }
    cout << M << endl;
}


Measured memory_bytes: 256
#include<iostream>

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

    std::cin >> a >> b >> c;

    int d = b + c - a;

    if(d <= 0){
        std::cout << "0" << std::endl;
    }else{
        std::cout << d << std::endl;
    }
    return 0; 
}


Measured memory_bytes: 256
def solve(string):
    h, w = map(int, string.split(" "))
    a = [list(map(lambda x: int(x) % 2 == 1, input().strip().split(" "))) for _i in range(h)]
    move = []
    for i in range(h):
        for j in range(w):
            if not a[i][j]:
                continue
            if j < w - 1:
                a[i][j + 1] ^= True
                move.append("{} {} {} {}".format(i + 1, j + 1, i + 1, j + 2))
            elif i < h - 1:
                a[i + 1][j] ^= True
                move.append("{} {} {} {}".format(i + 1, j + 1, i + 2, j + 1))
    move.insert(0, str(len(move)))
    return "\n".join(move)


if __name__ == '__main__':
    line = input().strip()
    # tmp = [line]
    # for _ in range(int(line[0])):
    #     tmp.append(input())
    # print(solve('\n'.join(tmp)))
    print(solve(line))


Measured memory_bytes: 16344
// In the name of god
#include <bits/stdc++.h>
#pragma GCC optimze("02")
using ll = long long ;
using namespace std;
const ll maxn=2e5+5,mod=1e9+7;
ll n,k,x,sum[maxn],ans;
int main(){
	ios::sync_with_stdio(false), cin.tie(0) , cout.tie(0);
	cin>>n>>k;
	x=(n+1)*(n)/2;
	for(ll i=k;i<n+2;i++){
		ans=(ans+(x-((n-i)*(n-i+1)/2))-((i-1)*i/2)+1)%mod;
	}
	cout<<ans;
}



Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>
#define N 1000005
using namespace std;

typedef long long ll;
ll n, d, z[N];
ll f(ll p) {
	ll s = 0;
	while (p > 0) {
		s += p % 10;
		p /= 10;
	}
	return s;
}
int main()
{
	ll i, j, t;
	cin >> n;
	printf("1\n");
	ll c;
	for (i = d = 1, c = 1; c < n; i += d, c++) {
		if ((i + d) * f(i + d * 2) > (i + d * 2) * f(i + d)) {
			d *= 10;
		}
		printf("%lld\n", i + d);
	}
    return 0;
}


Measured memory_bytes: 256
n, m, q = map(int, input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
  a[i], b[i], c[i], d[i] = map(int, input().split())
A = [1] * 10
 
def check(A, ans):
  t = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      t += d[i]
  if ans < t:
    return t
  else:
    return ans
 
ans = 0
for i1 in range(1, m+1):
  A[1] = i1
  for i2 in range(i1, m+1):
    A[2] = i2
    for i3 in range(i2, m+1):
      A[3] = i3
      for i4 in range(i3, m+1):
        A[4] = i4
        for i5 in range(i4, m+1):
          A[5] = i5
          for i6 in range(i5, m+1):
            A[6] = i6
            for i7 in range(i6, m+1):
              A[7] = i7
              for i8 in range(i7, m+1):
                A[8] = i8
                for i9 in range(i8, m+1):
                  A[9] = i9
                  ans = check(A, ans)
print(ans)

Measured memory_bytes: 9312
#include<iostream>
#include<algorithm>
#define INF 1000000009
using namespace std;
int main() {
	int dp[100000];
	int n;
	int a[100000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	fill(dp, dp + n, INF);
	for (int i = 0; i<n; i++) {
		*lower_bound(dp, dp + n, a[i]) = a[i];
	}
	cout << lower_bound(dp, dp + n, INF) - dp << endl;
	return 0;
}


Measured memory_bytes: 3908
/*
      author  : nishi5451
      created : 14.08.2020 13:03:33
*/

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


int main(){
    int h,w;
    cin >> h >> w;
    rep(i,w+2) cout << "#";
    cout << endl;
    rep(i,h){
        cout << "#";
        string s;
        cin >> s;
        cout << s;
        cout << "#" << endl;
    }
    rep(i,w+2) cout << "#";
    cout << endl;
    return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;

int main() { IO;
  vector<int> v(3);
  for (auto &x : v) cin >> x;
  sort(v.begin(), v.end());

  int ans = (v[0] * v[1]) / 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<numeric>

using namespace std;

int par[100000];
long long dist[100000];

void find(int x) {
	if (x != par[x]) {
		find(par[x]);
		dist[x] += dist[par[x]];
		par[x] = par[par[x]];
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, l, r, lp, rp;
	long long d;
	cin >> n >> m;
	vector<int> rank(n, 0);
	for (int i = 0; i < n; i++) {
		par[i] = i;
		dist[i] = 0LL;
	}
	auto ans = "Yes";
	for (int i = 0; i < m; i++) {
		cin >> l >> r >> d;
		l--; r--;
		find(l); find(r);
		lp = par[l]; rp = par[r];
		if (lp == rp) {
			if (dist[r] - dist[l] != d) {
				ans = "No";
				break;
			}
		}
		else {
			if (rank[lp] < rank[rp]) {
				par[lp] = rp;
				dist[lp] = dist[r] - dist[l] - d;
			}
			else {
				par[rp] = lp;
				dist[rp] = dist[l] + d - dist[r];
				if (rank[lp] = rank[rp]) rank[lp]++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    vector<int> out(N);
    for (int i = 0; i < N + M - 1; ++i) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        G[B].push_back(A);
        out[A]++;
    }

    queue<pii> que;
    for (int i = 0; i < N; ++i)
        if (!out[i])
            que.push({i, -1});

    Graph<int> G2(N);
    vector<int> ans(N);
    while (!que.empty()) {
        auto [v, cld] = que.front();
        que.pop();
        for (auto pv : G2[v])
            if (ans[pv] == 0)
                ans[pv] = v + 1;
        for (auto nv : G[v]) {
            out[nv]--;
            G2[nv].push_back(v);
            if (!out[nv])
                que.push({nv, v});
        }
    }

    for (auto i : ans)
        cout << i << '\n';

    return 0;
}


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

ll n, k, a[105], dp[105][100005];

int main() {
    cin >> n >> k;
    REP(i,n) cin >> a[i];
    dp[0][k] = 1;
    REP(i,n){
        REP(j,k+1){
            dp[i][j+1] += dp[i][j];
            dp[i][j+1] %= MOD;
        }
        REP(j,k+1){
            dp[i+1][j] += dp[i][min(k,j+a[i])] - (j>0?dp[i][j-1]:0) + MOD;
            dp[i+1][j] %= MOD;
        }
    }
    cout << dp[n][0] << endl;
    return 0;
}


Measured memory_bytes: 80128
N, M = gets.split.map(&:to_i)
A = Array.new(M)
B = Array.new(M)
M.times do |i|
  A[i], B[i] = gets.split.map(&:to_i)
end

class UnionFindTree
  def initialize(n)
    @parents = (0...n).to_a
    @sizes = Array.new(n, 1)
  end

  def find(x)
    @parents[x] == x ? x : @parents[x] = find(@parents[x])
  end

  def unite(a, b)
    a = find(a)
    b = find(b)
    return if a == b

    a, b = b, a if @sizes[a] < @sizes[b]
    @parents[b] = a
    @sizes[a] += @sizes[b]
  end

  def same?(a, b); find(a) == find(b) end
  def size(a); @sizes[find(a)] end
  def inspect; [@parents, @sizes] end
end

answers = Array.new(M, 0)
tree = UnionFindTree.new(N)
answers[M-1] = (N * (N - 1)) / 2
(M-2).downto(0) do |i|
  ag = tree.find(A[i+1] - 1)
  bg = tree.find(B[i+1] - 1)

  answers[i] = answers[i + 1]
  answers[i] -= tree.size(A[i+1] - 1) * tree.size(B[i+1] - 1) if ag != bg

  tree.unite(A[i+1] - 1, B[i+1] - 1)
end

answers.each do |ans|
  puts ans
end

Measured memory_bytes: 6908
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
ll mod=1e9+7;
int main()
{
    ll n;
    cin>>n;
    vector<ll>  a(n);
    vector<ll> b(n);
    for(ll i=0;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        a[i]=x+y;
        b[i]=x-y;
    }
    sort(begin(a),end(a));
    sort(begin(b),end(b));
    cout<<max(abs(a[n-1]-a[0]),abs(b[n-1]-b[0]))<<endl;
}


Measured memory_bytes: 6424
N=int(input())
S=input()

alpha="abcdefghijklmnopqrstuvwxyz"
MOD=10**9+7

c=[0]*26

for i in range(N):
    c[alpha.index(S[i])]+=1
ans=1
for i in range(26):
    ans*=c[i]+1

ans=(ans-1)%MOD
print(ans)


Measured memory_bytes: 3188
from fractions import gcd
N, K = map(int, input().split())
A = list(map(int, input().split()))
if max(A) < K:
    print("IMPOSSIBLE")
else:
    temp = A[0]
    for a in A[1:]:
        temp = gcd(a, temp)
    if K % temp == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Measured memory_bytes: 16280
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))

ruisekiwa = [0 for _ in range(n+1)]
for i in range(n):
	ruisekiwa[i+1] = ruisekiwa[i] + a[i]

dp = defaultdict(lambda: 0)
ans = 0
for i in ruisekiwa:
	ans += dp[i]
	dp[i] += 1
print(ans)

Measured memory_bytes: 41756
#ifdef _MSC_VER
#pragma warning(disable : 4996)
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) {
	if (a > b) a = b;
}
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) {
	if (a < b) a = b;
}
typedef pair<int, int> pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 200020;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


void solve() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	while (true) {
		C -= B;
		if (C <= 0) {
			print("Yes"); return;
		}
		A-= D;
		if (A <= 0) { print("No"); return; }
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// int q; cin >> q;
	// while (q--)
	solve();
}


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

ll N;
void solve()
{
    cin>>N;
    vector<ll>v(N);
    for(ll i=0;i<N;++i)
    {
         cin>>v[i];
    }
    ll cnt=0;
    sort(v.begin(),v.end());
    for(ll i=0;i<N;i++)
    {
        for(ll j=i+1;j<N;j++)
        {
            for(ll k=j+1;k<N;k++)
            {
                if(v[i]!=v[j] && v[j]!=v[k])
                {
                    if(v[i]+v[j]>v[k])
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<"\n";
}
signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    solve();
}

Measured memory_bytes: 3640
#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{	
	int N;
	int h[(int)1e5], dp[(int)1e5];
	for(int j = 1;j <= 1e5;j++)
		dp[j] = 1e5;
	scanf("%d", &N);
	for(int i = 1;i <= N;i++)
	{
		scanf("%d", &h[i]);		
	}
	for(int i = 1;i <= N;i++)
	{
		dp[1] = 0;
		dp[2] = dp[1] + abs(h[1] - h[2]);
		dp[i + 2] = min(dp[i] + abs(h[i] - h[i + 2]), dp[i + 1] + abs(h[i + 1] - h[i + 2]));
	}
	printf("%d\n", dp[N]);
	return 0;
}

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

int main() {
	int n, k;
	scanf("%d%d", &k, &n);
	if (k == 1) {
		for (int i = 0; i < (n + 1) / 2; i++)
			printf("1 ");
	} else if (k % 2) {
		int64_t num = 0, cur = 1;
		int i = 0;
		for (; i < n && num < 1000000000LL; i++)
			num += cur *= k;
		if (i == n) {
			int64_t t = (num - 1) / 2;
			std::vector<int> res;
			for (int i = 0; i < n; i++) {
				if (i) {
					if (!t) break;
					t--, num--;
				}
			  num /= k;
				res.push_back(t / num);
				t %= num;
			}
			for (auto j : res) printf("%d ", j + 1);
		} else {
			int shift = 0;
			std::vector<int> res;
			for (int j = 0; j < n - i; j++) {
        if (j && (n - j) % 2) shift++;
				res.push_back((k + 1) / 2);
			}
			num++;
			int64_t t = (num - 1) / 2 - shift;
			assert(t >= 0);
      for (int j = n - i; j < n && t; j++) {
				t--, num--;
				num /= k;
				res.push_back(t / num + 1);
				t %= num;
			}
      for (auto j : res) printf("%d ", j);

		}
	} else {
		printf("%d", (k + 1) / 2);
		for (int i = 0; i + 1 < n; i++)
			printf(" %d", k);
	}
  return 0;
}


Measured memory_bytes: 3568