akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int flagx[100001];
int flagy[100001];
int n,w,h,x,y,z;

int main(){
	cin >>n >>w >>h;
	for(int i=0;i<w;i++)flagx[i]=0;
	for(int i=0;i<h;i++)flagy[i]=0;

	for(int i=0;i<n;i++){
		cin >>x >>y >>z;
		if(x-z>=0){
			flagx[x-z]++;
		}else{
			flagx[0]++;
		}
		if(x+z<=w)flagx[x+z]--;
		if(y-z>=0){
			flagy[y-z]++;
		}else{
			flagy[0]++;
		}
		if(y+z-1<=h)flagy[y+z]--;
	}
	for(int i=1;i<w;i++){
		flagx[i]+=flagx[i-1];
	}
	for(int i=1;i<h;i++){
		flagy[i]+=flagy[i-1];
	}

	int a,b;
	for(a=0;a<w;a++){
		if(flagx[a]==0)break;
	}
	for(b=0;b<h;b++){
		if(flagy[b]==0)break;
	}
	if(a==w||b==h){
		cout <<"Yes" <<endl;
	}else{
		cout << "No"<<endl;
	}
	
}

Measured memory_bytes: 3872
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

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

    int dp[100002][3];
    int h[3][100002];

    rep(i,n){
        cin >> h[0][i] >> h[1][i] >> h[2][i];
    }
    rep(i,100002){
        rep(j,3){
            dp[i][j] = 0;
        }
    }
    dp[0][0] = h[0][0];
    dp[0][1] = h[1][0];
    dp[0][2] = h[2][0];
    reps(i,1,n){
        rep(j,3){
            dp[i][j] = max(dp[i-1][(j+1)%3] + h[j][i] , dp[i-1][(j+2)%3] +h[j][i]);
        }
    }
    // rep(i,n){
    //     rep(j,3){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])) << endl;

    return 0;
}


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

void solve(void)
{
    ll x, y;
    cin >> x >> y;
    ll a = abs(-x - y) + 1;
    ll b = INF;
    if (x < y)
        b = abs(x - y);
    ll c = abs(x - y) + 2;
    cout << min(a, min(b, c)) << endl;
}
int main(void)
{
    solve();
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    if(k%2) --k,x-=d;
    x=abs(x);
    k/=2;
    d*=2;
    ll y=x/d,ans{};
    if(y<k) ans=min(x-d*y,d*y+d-x);
    else ans=x-d*k;
    cout<<ans<<'\n';
}

Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
ll f[N],invs[N];
ll pows(ll a,ll n )
{
    ll ans=1;
    while(n)
    {
        if(n&1)
        {
            ans=ans*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
ll inv(ll a)//求逆元
{
    return pows(a,mod-2);
}
ll C(ll n,ll m)//组合数公式
{
    return f[m]*inv(f[n])%mod*inv(f[m-n])%mod;
    //return f[m]*invs[n]%mod*invs[m-n]%mod;
}
int main()
{

    ll n;
    f[0]=1;
    for(ll i=1; i<N; i++)
    {
        f[i]=f[i-1]*i%mod;
        invs[i]=inv(f[i])%mod;
    }
    cin>>n;
    if(n<2)
    {
        cout<<0<<endl;
    }
    else
    {
        ll sum=0;
        for(ll i=2; i<=n; i++)
        {
            sum=(sum+C(i,n)%mod*(pows(2,i)-2)%mod*pows(8,n-i)%mod)%mod;

        }
        cout<<sum<<endl;
    }
    return 0;

}


Measured memory_bytes: 19252
#include <iostream>
#include <set>

typedef std::set<unsigned> Set;

int main()
{
  unsigned N;
  std::cin >> N;

  Set set;
  for (int ii=0; ii<N; ++ii) {
    unsigned A;
    std::cin >> A;
    auto itr = set.find(A);
    if (itr==set.end())
      set.insert(A);
    else
      set.erase(itr);
  }
  
  std::cout << set.size() << std::endl; 
  
  return 0;
}


Measured memory_bytes: 4864
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	while(true){
		int H, W;
		cin >> H >> W;
		if(H == 0){
			return EXIT_SUCCESS;
		}
		for(int i = 0; i < H; i++){
			if(i == 0 || i == H - 1){
				for(int k = 0; k < W; k++){
					cout << '#';
				}
				cout << '\n';
			}else{
				cout << '#';
				for(int j = 1; j < W - 1; j++){
					cout << '.';
				}
				cout << '#';
				cout << '\n';
			}
		}
		cout << '\n';
	}
}



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

int main(){
    int K, L;
    cin >> K;
    if(K%7 == 0){
        L = 9 * K / 7;
    }
    else{
        L = 9 * K;
    }

    if(L%2 == 0 || L%5 == 0){
        cout << "-1" << endl;
        exit(0);
    }

    int amari = 1, ans = 0;
    for(int i = 1; i < L; i++){
        amari = (amari * 10)%L;
        if(amari == 1){
            ans = i;
            break;
        }
    }
    cout << ans << endl;

}

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

int n, l, q, ai, bi; 
int a[1000010];
int f[1000010][40];

void prepare() {
	for(int i = 1; i <= n; i++){
		int id = upper_bound(a + 1,a + 1 + n, a[i] + l) - a - 1;  
		if(a[i] + l > a[n])	f[i][0] = n;
		else f[i][0] = id;
	} 
	for(int i = 1; i <= 32; i++)
		for(int j = 1; j <= n; j++)
			f[j][i] = f[f[j][i - 1]][i - 1];
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) 
		scanf("%d", &a[i]);
	scanf("%d%d", &l, &q);
	prepare();
	while(q--) {
		scanf("%d%d", &ai, &bi);
		if(ai > bi) swap(ai, bi);
		int ans = 0;
		for(int j = 30; j >= 0; j --)  
			if(f[ai][j] < bi) { ans += (1 << j); ai = f[ai][j];}
		printf("%d\n", ans + 1);
	}
	return 0;
} 

Measured memory_bytes: 19200
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()
def gcd_core(a, b):
    if b == 0: return a
    else: return gcd_core(b, a % b)
def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)): g = gcd_core(g, arr[i])
    return g
def main():
    K = I()
    for a in range(1, K+1):
        for b in range(a, K+1):
            for c in range(b, K+1):
                x = len({a, b, c})
                if x == 1: pass
                elif x == 2: x = 3
                else: x = 6
                yield gcd([a, b, c])*x
if __name__ == '__main__':
    print(sum(main()))

Measured memory_bytes: 9356
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <deque>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <numeric>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define mt make_tuple
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecvec vector<vec>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vecpll vector<pll>
#define vecbl vector<bool>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
string stin(){string s;cin>>s;return s;}

int main(){
    int n=in(),k=in();
    vecll a(n);
    rep(i,n)a[i]=in();
    ll ng=0,ok=1000000000;
    while(ng+1<ok){
        ll mid=(ng+ok)/2;
        ll cnt=0;
        rep(i,n){
            cnt += (a[i]+mid-1)/mid-1;
        }
        if(cnt > k)ng=mid;
        else ok=mid;
    }
    cout<<ok<<endl;
}


Measured memory_bytes: 4808
import sys

read = sys.stdin.read
readline = sys.stdin.readline


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if x == y:
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, M, K, *ABCD = map(int, read().split())
AB = ABCD[:M * 2]
CD = ABCD[M * 2:]
F = UnionFind(N)
friend = [[] for _ in range(N + 1)]
for A, B in zip(*[iter(AB)] * 2):
    F.Unite(A, B)
    friend[A].append(B)
    friend[B].append(A)

block = [[] for _ in range(N + 1)]
for C, D in zip(*[iter(CD)] * 2):
    block[C].append(D)
    block[D].append(C)

answer = []
for i in range(1, N + 1):
    cnt = F.Count(i) - 1
    for j in block[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    for j in friend[i]:
        if F.isSameGroup(i, j):
            cnt -= 1
    answer.append(cnt)

print(' '.join(map(str, answer)))


Measured memory_bytes: 58372
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
interval = [1, N]
def intersect(ia, ib):
    if not ia or not ib:
        return []
    l = max(ia[0], ib[0])
    r = min(ia[1], ib[1])
    if l > r:
        return []
    else:
        return [l, r]

for i in range(M):
    l, r = tuple(li())
    interval = intersect(interval, [l, r])
if not interval:
    print(0)
else:
    print(interval[1] - interval[0] + 1)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  int res = 1e+9;
  for(int i=-100;i<101;++i){
    int sum = 0;
    rep(j,n){
      sum += (i-a[j])*(i-a[j]);
    }
    res = min(res,sum);
  }
  
  cout << res << "\n";

  return 0;
}


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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    Ap = N + 100
    Score = 0
    for Ai in A:
        Score += B[Ai-1]
        if Ai == Ap + 1:
            Score += C[Ap-1]
        Ap = Ai
    print(Score)



if __name__ == "__main__":
    main()


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

int main() {
  string s,t; cin >> s >> t;
  if (s.size() < t.size()) {
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  vector<string> ans;
  for (int i = 0; i <= s.size()-t.size(); i++) {
    bool f = true;
    for (int j = 0; j < t.size(); j++) {
      if (s[i+j] != t[j] && s[i+j] != '?') {
        f = false;
        break;
      }
    }
    if (f) {
      string ss = s;
      for (int j = 0; j < ss.size(); j++) if (ss[j] == '?') ss[j] = 'a';
      for (int j = 0; j < t.size(); j++) ss[i+j] = t[j];
      ans.push_back(ss);
    }
  }
  if (!ans.empty()) cout << *(ans.end()-1) << endl;
  else cout << "UNRESTORABLE" << endl;
  return 0;
}


Measured memory_bytes: 256
#[test]
fn test_solve() {
    assert_eq!(solve("2 3\n0 1 1\n1 0 1\n1 4 0\n1 2\n3 3\n"), "3\n");
    assert_eq!(
        solve("4 3\n0 12 71\n81 0 53\n14 92 0\n1 1 2 1\n2 1 1 2\n2 2 1 3\n1 1 2 2\n"),
        "428\n"
    );
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let cmx: usize = sc.read();

    let d: Vec<Vec<usize>> = (0..cmx)
        .map(|_| (0..cmx).map(|_| sc.read()).collect())
        .collect();
    let c: Vec<Vec<usize>> = (0..n)
        .map(|_| (0..n).map(|_| sc.read()).collect())
        .collect();
    let mut cst = vec![vec![0; cmx]; 3];
    for i in 0..n {
        for j in 0..n {
            for to in 0..cmx {
                cst[(i + j) % 3][to] += d[c[i][j] - 1][to];
            }
        }
    }
    let cst = cst;

    let mut ans = 1000 * 500 * 500;
    use std::cmp::min;
    for i in 0..cmx {
        for j in 0..cmx {
            for k in 0..cmx {
                if i != j && j != k && k != i {
                    ans = min(ans, cst[0][i] + cst[1][j] + cst[2][k]);
                }
            }
        }
    }

    format!("{}\n", ans)
}
fn main() {
    let mut buf = String::new();
    use std::io::{Read, Write};
    std::io::stdin().read_to_string(&mut buf).unwrap();
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i=0;i<(n);i++)
#define rep2(i, m, n) for(int i=m;i<(n);i++)
#define rrep(i, n, m) for(int i=n;i>=(m);i--)
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll MOD = 1000000007;
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N, T;
    cin >> N >> T;
    vector<int> t(N);
    rep(i, N) cin >> t[i];
    int ans = 0;
    int last = T;
    for (int i = 1; i < N; ++i) {
        int time = t[i];
        if (last > time) {
            ans += time - t[i - 1];
        } else {
            ans += T;
        }
        last = time + T;
    }
    ans += T;
    cout << ans << endl;

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}


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

int arraySum(int a[],int start, int end){
  int sum=0;
  for(int i=start;i<=end;i++)
    sum+=a[i];
  return sum;
}

int main(){
  int N,res=0,sum=0,num;
  int a[2][100]={};
  cin >> N;
  for(int i=0;i<2;i++){
    for(int j=0;j<N;j++){
      cin >> a[i][j];
    }
  }
  for(int i=0;i<N;i++){
    sum=arraySum(a[0],0,i)+arraySum(a[1],i,N);
    res=res<sum?sum:res;
  }
  cout<<res<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

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; }

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,a,b;cin>>n>>a>>b;
  vector<ll>h(n);
  rep(i,n)cin>>h[i];
  ll ok=1e9,ng=0;
  auto check=[&](ll num){
    auto th=h;
    rep(i,n)th[i]-=(b)*num;
    rep(i,n)if(th[i]<0)th[i]=0;
    ll cnt=0;
    rep(i,n)if(th[i]>0)cnt+=max(0LL,(th[i]-1)/(a-b)+1);
    return cnt<=num;
  };
  while(ok-ng>1){
    ll nn=(ng+ok)/2;
    if(check(nn))ok=nn;
    else ng=nn;
  }
  cout<<ok<<endl;



}


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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

const double eps = 1e-10;
const int MOD = 1000000007;

void printv(vector<auto> const& s) {
  REP(i, s.size()) {
    cout << s[i] << endl;
  }
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  vi a(3);
  REP(i, 3) {
    cin >> a[i];
  }
  sort(ALL(a));
  cout << a[2] - a[0] << endl;
}


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

public class Main {
	public static final int[] charCount = new int[26];
	public static final StringBuilder sb = new StringBuilder();
	public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String... args) throws IOException {
		while (true) {
			final int charactor = br.read();
			if (97 <= charactor && charactor <= 123) {
				charCount[charactor - 97]++;
			} else if (65 <= charactor && charactor <= 91) {
				charCount[charactor - 65]++;
			} else if (charactor == -1) {
				break;
			}
		}

		for (int i = 0; i < 26; i++) {
			sb.append(((char) (i + 97))).append(" : ").append(charCount[i]).append(i != 25 ? '\n' : "");
		}

		System.out.println(sb);
	}
}

Measured memory_bytes: 16888
/*
　　　　　／＞　 フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ
 */


#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;
 
template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}
 
template<typename F>
inline void write(F x)
{
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar('\n');
}
 
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
 
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }
 
const int P = 998244353;
ll fpw(ll x, ll mi) {
	ll res = 1;
	for (; mi; mi >>= 1, x = x * x % P) 
		if (mi & 1) res = res * x % P;
	return res;
}
 
const int N = 1005000;
ll jie[N], inv[N];
inline ll C (ll n, ll m) {
	return jie[n] * inv[m] % P * inv[n-m] % P;
}
 
int m, n;
int main() {
	read(n), read(m);
	int lim = n + m; jie[0] = inv[0] = inv[1] = 1;
	for (int i = 2;i <= lim; i++)
		inv[i] = (ll)(P - P / i) * inv[P % i] % P;
	for (int i = 1; i <= lim; i++)
		inv[i] = inv[i - 1] * inv[i] % P, jie[i] = jie[i-1] * i % P;
	ll ans = 0;
	for (int i = 1;i <= min(n, m); i++)
		ans = (ans + C(2 * i, i) * C(n + m - 2 * i, n - i)) % P;
	ans = ans * fpw(C(n + m, n) * 2 % P, P - 2);
	write((max(n, m) + ans) % P);
	return 0;
}

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

int main(){
//srandom((unsigned long)time(NULL));
    int n;
    cin>>n;
   string s[n];
   int p[n];

    pair<pair<string,int>,int> a[n];

   for(int i=0;i<n;i++){
       cin>>s[i]>>p[i];
      a[i].first.first=s[i];
      a[i].first.second=-p[i];
      a[i].second=i+1;
   }

    sort(a,a+n);
    for(int i=0;i<n;i++){
        cout<<a[i].second<<endl;
    }






return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,ls[30],mx1,mx2,x,c[30];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=26;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)
    {
        mx1=0,mx2=1;
        for(int j=1;j<=26;j++)
        {
            scanf("%d",&x);
            if(mx1<(i-ls[j])*c[i])mx1=(i-ls[j])*c[i],mx2=j;
            else if(mx1==(i-ls[j])*c[i])if(ls[j]<ls[mx2])mx2=j;
        }
        //printf("[%d]",mx1);
        ls[mx2]=i;
        printf("%d\n",(i%26)+1);
    }
}


Measured memory_bytes: 3800
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;


class Program {
    internal static void Main(string[] args) {
        int[] inp = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        if (inp[0] <= 8 && inp[1] <= 8)
        {
            WriteLine("Yay!");
        } else {
            WriteLine(":(");
        }

    }
}



Measured memory_bytes: 13268
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR (i,n) for(int i=n;i>0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
const int MOD{ int(1e9 + 7) };	// int 1000000007
const int inf{ int(1e9) };	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;

int main(void) {

	int n, l;
	cin >> n >> l;
	vector<string> s(n);
	REP(i, n) cin >> s[i];

	sort(s.begin(), s.end());
	for (auto x : s) cout << x << flush;
	cout << endl;

	return 0;
}

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

int32_t main() {
    
    int a,b;
    cin >> a >> b;
    
    if(b==1)
    cout << 0 ;
    else if(b<=a) {
        cout << 1 ;
    }
    else {
        int an=a,c=1;
        while(b>an) {
            an+=(a-1);
            c++;
        }
        cout <<c;
        
    }
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		long S = long.Parse(Console.ReadLine());
		long T = (long)Math.Pow(S,0.5);
		long X1 = 0;
		long X2 = 0;
		long X3 = 0;
		long Y1 = 0;
		long Y2 = 0;
		long Y3 = 0;
		long S1 = T*T;
		long S2 = T*(T+1);
		long S3 = (T+1)*(T+1);
		if(S==S1){
			X1 = T;
			Y2 = T;
			X3 = T;
			Y3 = T;
		} else if(S==S2){
			X1 = (T+1);
			Y2 = T;
			X3 = (T+1);
			Y3 = T;
		} else if(S>S1 && S<S2){
			X1 = T;
			Y2 = S-S1;
			Y3 = T;
			X3 = T+1;
		} else {
			X1 = T;
			Y2 = S-S2;
			Y3 = T+1;
			X3 = T+1;
		}
      	Console.Error.WriteLine(S1+" "+S2+" "+S3);
		Console.WriteLine(X1+" "+Y1+" "+X2+" "+Y2+" "+X3+" "+Y3);
	}
}

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

int main(){
 int r,c,i,j;
 
 cin >> r >> c ;
 int matrix[r+1][c+1];

 for(i=0;i<r+1;i++){
  for(j=0;j<c+1;j++){
   matrix[i][j]=0;
  }
 }

 for(i=0;i<r;i++){
  for(j=0;j<c;j++){
   cin >> matrix[i][j] ;
  }
 }

 for(i=0;i<r;i++){
  for(j=0;j<c;j++){
   matrix[i][c]+=matrix[i][j];
  }
 }

 for(i=0;i<c+1;i++){
  for(j=0;j<r;j++){
   matrix[r][i]+=matrix[j][i];
  }
 }

 for(i=0;i<r+1;i++){
  for(j=0;j<c+1;j++){
   if(j!=0)cout << " " ;
   cout << matrix[i][j];
  }
  cout << endl;
 }
 

 return 0;
}

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

using namespace std;
typedef long long ll;

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}
ll n, d, ans, x, y;

int main() {
    read(n), read(d);
    for (int i = 1; i <= n; i++) {
        read(x), read(y);
        if (x * x + y * y <= d * d) ans++;
    }
    cout << ans;
    return 0;
}


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

int main() {
  int N;
  cin >> N ;
  if(1 <= N &&N <10){
    cout << N << endl;
  }
  if (10 <= N&&N < 100){
    cout << 9 << endl;
  }
  if (100 <= N&&N < 1000){
    cout << 9 + N - 99<<endl;
  }
  if (1000 <=N&&N < 10000){
    cout << 909 << endl;
  }
  if (10000<=N&&N<100000){
    cout << 909 + N - 9999<<endl;
  }
  if (N==100000){
    cout << 90909 <<endl;
  }
}


Measured memory_bytes: 256
import Control.Applicative
import Data.List
import Control.Monad
import Data.Function
import Data.Array

getLineN :: Int -> IO [String]
getLineN n = replicateM n getLine

main = do
    _ <- getLine
    s <- getLine
    putStrLn.show.maximum $ map (answer s) [1..(length s-1)]

answer :: String -> Int -> Int
answer s k = length  $ filter (\v -> v `elem` s1 ) s2 where
    s1 = nub $ take k s
    s2 = nub $ drop k s

Measured memory_bytes: 892
#define _GLIBCXX_DEBUG
#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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int n,m; cin >> n >> m;
  int ans=n*(n-1)+m*(m-1);
  cout << ans/2 << endl;
  
}

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a;
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputDoubleArray(a,N) double a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
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; }

//参考
/*int rec(int v) {
    if (dp[v] != -1) return dp[v]; // 既に更新済み

    int res = 0;
    for (auto nv : G[v]) {//要素nvについてループを回す。
        chmax(res, rec(nv) + 1);
    }
    return dp[v] = res; // メモしながらリターン
}*/

struct Edge {
  int to;
  int weight;
  Edge(int t, int w):to(t),weight(w){}
};

typedef vector<vector<Edge>> Graph;//グラフ→ノードの配列→辺の構造体を持った配列という抽象化
//Edgeのベクトル→ノード。ノードのベクトル→グラフ。

vector<int> status;

bool dfs(const Graph &G, int v, int cur = 0){//default
  status[v] = cur;//まず塗る
  
    for(auto edge : G[v]){//隣接する辺について
      
      if(status[edge.to] == -1){//未探索なら
        if(edge.weight%2 == 0){//辺の重みが偶数の時
          if(!dfs(G,edge.to,cur)) return false;//同じ色で塗る
        }else{
          if(!dfs(G,edge.to,1-cur)) return false;
        }
      }else if(status[edge.to] == cur){
        if(edge.weight%2 == 0){
          continue;
        }else{
          return false;
        }
      }else{
        if(edge.weight%2 == 0){
          return false;
        }else{
          continue;
        } 
      } 
    }
  return true;
}

int main() {
    // 入力受け取り
    inputInt(N);
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        --from, --to; // 0-indexed にする
        G[from].push_back(Edge(to,weight));//GraphVector[x]にyを追加
        G[to].push_back(Edge(from,weight));
    }
  
    //二部グラフ判定
    // 探索
    status.assign(N, -1);//初期化
    bool is_bipartite = true;
    for (int v = 0; v < N; ++v) {
        if (status[v] != -1) continue; // v が探索済みだったらスルー
        if (!dfs(G, v)) is_bipartite = false;
    }

    if (is_bipartite) {
      fN(i,N) cout << status[i] << endl;  
    }
}

Measured memory_bytes: 8192
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), r = sc.nextInt();
        
        if (n <= 10) {
            int x = 100 * (10 - n);
            System.out.println(r + x);
            return;
        }
        System.out.println(r);
    }
}


Measured memory_bytes: 21716
import java.util.*;

public class Main { 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    boolean[] used = new boolean[30];
    String ans = "";
    if (s.length() < 26) {
      for (int i=0; i<s.length(); i++) {
        used[Ind(s.charAt(i))] = true;
      }
      for (int i=0; i<30; i++) {
        if(!used[i]) {
          ans = s + ((char) (i + 97));
          break;
        }
      }
    } else {
      int index = -1;
      for (int i = s.length() - 2; i >= 0; i--) {
        if( s.charAt(i) < s.charAt(i+1)) {
          index = i;
          break;
        }
      }
      if (index == -1) {
        ans = "-1";
      } else {
        char c = 'z';
        for (int j = index + 1; j < s.length(); j++) {
          if (s.charAt(j) > s.charAt(index) && s.charAt(j) < c) {
            c = s.charAt(j);
          }
        }
        ans = s.substring(0,index) + c;
      }
    }
    System.out.println(ans);
    
   }
  public static int Ind(char x) {
    return ((int) x) - 97;
  }
}

Measured memory_bytes: 23252
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
 
ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
	}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
	int ab,bc,ca;
    cin >> ab >> bc >> ca;
    cout << ab*bc/2 << endl;
	return 0;
}


Measured memory_bytes: 256
s=input()
n=len(s)
res = -1
leng = 0
for i in range(n-2):
    if s[i] == s[i+1]:
        res = i+1
        leng = 2
        break
    elif s[i] == s[i+2]:
        res = i+1
        leng = 3
        break
if s[-2] == s[-1]:
    res = n-1
    leng = 2

if res == -1:
    print("-1 -1")
elif leng == 2:
    print(str(res)+" "+str(res+1))
else:
    print(str(res)+" "+str(res+2))

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

int main() {
    int n,x,t;
    cin>>n>>x>>t;
    int s=(n+x-1)/x;
    cout<<s*t<<endl;
    
  return 0;
}


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

#define sysp system("pause")
#define int long long

int n;
string bin;
int mbin;

int dnb(int a){//それをこえるのを出力
	int dispo=1;
	int ret=0;
	if(a>=0){
		for(int i=1;i<a;i+=(dispo*=4),ret++,mbin=i);
		return ret;
	}
	if(a<0){
		a*=-1;
		dispo=2;
		for(int i=2;i<a;i+=(dispo*=4),ret++,mbin=i);
		return ret;
	}
}

void mb(int a){
	if(a>=0){
		bin="1";
		for(int i=0;i<(dnb(a));i++,bin+="01");
	}
	if(a<0){
		bin="10";
		for(int i=0;i<(dnb(a));i++,bin+="10");
	}
}

int fac(int a,int b){
	int ret=1;
	for(int i=0;i<b;ret*=a,i++);
	return ret;
}

string solve(){
	int hb=fac(2,bin.size());
	string mo="";
	int hhb=hb/2;
	int cn=n;
	if(cn<0)cn*=-1;
	for(int i=0;i<bin.size();i++,hhb/=2){
		if(mbin-hhb>=cn){
			mo+='1';
			mbin-=hhb;
		}
		else mo+='0';
	}
	for(int i=0;i<mo.size();i++){
		if(mo[i]=='1'){
			bin[i]-='0';
			if(bin[i]==0){
				bin[i]++;
			}else{
				bin[i]--;
			}
			bin[i]+='0';
		}
	}
	return bin;
}

main(){
	cin>>n;
	if(n==0){cout<<0<<endl;return 0;}//れいがいしょりめんどい
	mb(n);
	cout<<solve()<<endl;
	sysp;
}

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

int main()
{
    int H, W, D, A[310][310], Q, L[100010], R[100010];
    cin >> H >> W >> D;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];
    cin >> Q;
    for (int i = 0; i < Q; i++) cin >> L[i] >> R[i];

    map<int, pair<int, int>> mp;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            mp[A[i][j]] = make_pair(i, j);
        }
    }

    int cost[100010] = {};
    for (int i = D + 1; i <= H * W; i++) {
        cost[i] = cost[i - D] + abs(mp[i].first - mp[i - D].first) + abs(mp[i].second - mp[i - D].second);
    }

    for (int i = 0; i < Q; i++) {
        cout << cost[R[i]] - cost[L[i]] << endl;
    }

    return 0;
}


Measured memory_bytes: 8320
using ll=long long;using ull=unsigned long long;
#include<limits>
namespace pcl{template<typename T>constexpr T TNF=std::numeric_limits<T>::max()/2;constexpr int INF=TNF<int>;constexpr ll LNF=TNF<ll>;constexpr double DNF=TNF<double>;constexpr double EPS=1e-8;constexpr int P7=1'000'000'007;constexpr int DX[]={1,0,-1,0,1,1,-1,-1};constexpr int DY[]={0,1,0,-1,-1,1,1,-1};}
#include<algorithm>
#include<cmath>
#include<iostream>
namespace pcl{template<typename T>void updmax(T&a,T const&b){a=std::max(a,b);}template<typename T>void updmin(T&a,T const&b){a=std::min(a,b);}template<typename T,typename U,typename V>bool in_range(T const&begin,U const&mid,V const&end){return begin<=mid&&mid<end;}template<typename T,typename U,typename V>bool in_range(T const&begin,std::initializer_list<U>list,V const&end){auto p=std::minmax_element(list.begin(),list.end());return begin<=*p.first&&*p.second<end;}template<typename T,typename U,typename V>bool in_range_strict(T const&begin,std::initializer_list<U>list,V const&end){if(!std::is_sorted(list.begin(),list.end()))return false;return in_range(begin,list,end);}template<typename T>inline T cget(){T x;std::cin>>x;return x;}}
#include<iostream>
#include<vector>
namespace pcl{template<typename T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){os<<'[';for(size_t i=0;i<v.size();i++){if(i!=0)os<<",";os<<v[i];}os<<']';return os;}template<typename T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(size_t i=0;i<v.size();i++)is>>v[i];return is;}}
#include<bits/stdc++.h>
using namespace std;using namespace pcl;int main(){int X,Y,Z,K;cin>>X>>Y>>Z>>K;vector<ll>A(X),B(Y),C(Z);cin>>A>>B>>C;vector<ll>AB;AB.reserve(X*Y);for(ll a:A){for(ll b:B)AB.push_back(a+b);}sort(AB.rbegin(),AB.rend());if((int)AB.size()>K)AB.resize(K);vector<ll>ABC;for(ll ab:AB){for(ll c:C)ABC.push_back(ab+c);}sort(ABC.rbegin(),ABC.rend());for(int i=0;i<K;i++)cout<<ABC[i]<<endl;}


Measured memory_bytes: 42984
// IlyM

#include <bits/stdc++.h>
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define tra(a,b) for (auto a:b) 
#define fo(a,b,c) for (int a=b;a<=c;a++) 
#define ms(a,b) memset(a,b,sizeof(a)) 
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define bit(i,j) (i&(1<<j))

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef pair<int,ii> iii;

const int N=2e5+5,mod=998244353;
int n;
int main()
{
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	cin>>n; 
	n++;
	cout<<n/2;
	return 0;
}


Measured memory_bytes: 256
/**
 *  author: Haunted_Cpp
**/

#include <bits/stdc++.h>
using namespace std;

template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string w;
  cin >> w;
  int q;
  cin >> q;
  vector<tuple<int, int, int>> perguntas(q);
  int flip = 0;
  for (int i = 0; i < q; i++) {
    int task;
    cin >> task;
    if (task == 1) {
      ++flip;
      perguntas[i] = make_tuple(1, -1, -1);
    } else {
      int lado;
      char c;
      cin >> lado >> c;
      --lado;
      perguntas[i] = make_tuple(2, lado, c - 'a');
    }
  }
  if (flip & 1) reverse(w.begin(), w.end());
  string inicio;
  for (int i = 0; i < q; i++) {
    int task = get<0>(perguntas[i]);
    if (task == 1) {
      --flip;
    } else {
      int lado = get<1>(perguntas[i]);
      int c = get<2>(perguntas[i]);
      if (flip & 1) lado ^= 1;
      debug(lado);
      if (lado == 0) inicio += char(c + 'a');
      else w += char (c + 'a');
    }
  }
  reverse(inicio.begin(), inicio.end());
  cout << inicio + w << '\n';
  return 0;
}


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

const int sz=262144;
long long seg[sz*2];
int lazy[sz*2];
const int mod=998244353;
int n;
long long inv;
long long fp[500001];

long long fastpow(long long a,long long b) {
    if (b==0) {
        return 1;
    }
    if (b%2==1) {
        return (fastpow(a,b-1)*a)%mod;
    }
    long long half=fastpow(a,b/2);
    return (half*half)%mod;
}

void propagate(int node,int nodel,int noder) {
    if (lazy[node]!=0) {
        long long val=(fp[noder-nodel+1]+mod-1)*inv;
        val%=mod;
        val*=fp[n-1-noder];
        val%=mod;
        val*=lazy[node];
        val%=mod;
	seg[node]=val;
        if (node<sz) {
            lazy[node*2]=lazy[node];
            lazy[node*2+1]=lazy[node];
        }
        lazy[node]=0;
    }
}

long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    propagate(node,nodel,noder);
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return (sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder))%mod;
}

void update(int l,int r,int val,int node=1,int nodel=0,int noder=sz-1) {
    propagate(node,nodel,noder);
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        lazy[node]=val;
        propagate(node,nodel,noder);
        return;
    }
    int mid=(nodel+noder)/2;
    update(l,r,val,node*2,nodel,mid);
    update(l,r,val,node*2+1,mid+1,noder);
    seg[node]=(seg[node*2]+seg[node*2+1])%mod;
}

int main(void) {
    fp[0]=1;
    for(int i=1;i<=500000;i++) {
        fp[i]=(fp[i-1]*10)%mod;
    }
    inv=fastpow(9,mod-2);
    int q;
    scanf("%d %d",&n,&q);
    update(0,n-1,1);
    for(int i=0;i<q;i++) {
        int l,r,d;
        scanf("%d %d %d",&l,&r,&d);
        l--;
        r--;
        update(l,r,d);
        printf("%lld\n",sum(0,sz-1));
    }
}

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

typedef long long int ll;
typedef vector<int> vi;            typedef vector<ll> vl;
typedef vector<vi> vvi;         typedef vector<vl> vvl;
typedef pair<int, int>     pii;    typedef pair<ll, ll> pll;
typedef vector<pii> vii;         typedef vector<pll> vll;
typedef map<int,int> mii;
typedef vector<char> vc;
typedef vector<bool> vb;
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define rforne(i,n) for(int i=n;i>=1;i--)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
const ll INFL = 1e18;
const int INFI = 1e9;
#ifdef KARAN
    #include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}
ll modpow(ll a, ll b, ll m = MOD){a %= m; ll res = 1; 
    while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}
void graph(vvi &adj, int m) {int x, y; forn(i, m){cin>>x>>y; adj[--x].pb(--y); adj[y].pb(x);}}

void solve(){
    ll n, w; cin>>n>>w;
    vvl dp(n, vl(w+1, 0));
    vl wt(n), v(n);
    forn(i, n) cin>>wt[i]>>v[i];
    for(int i = wt[0]; i<=w; i++)
        dp[0][i] = max(dp[0][i], v[0]);
    forne(i, n-1){
        forn(j, w+1){
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            if(j + wt[i]<=w)
                dp[i][j + wt[i]] = max(dp[i][j + wt[i]], dp[i-1][j] + v[i]);
        }
    }
    trace(dp);
    ll ans = 0;
    forn(j, w+1) ans = max(ans, dp[n-1][j]);
    cout<<ans<<endl; 
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef KARAN
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    int t=1;
    while(t--)
        solve();
}

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

  int main()
    {
    string A;
    cin >> A;
    
    if ( A[0] == 'S' && A[1] == 'S' && A[2] == 'S' ){
      cout << 0 << endl;
                                                    }
    
    else if ( A[1] == 'S' ) {
      cout << 1 << endl;
                            }
    
    else if ( A[0] == 'R' && A[2] == 'R' ){
      cout << 3 << endl;
                                          }
    
    else if ( A[0] == 'S' && A[2] == 'S' ) {
      cout << 1 << endl;
                                           }
      
    else {
      cout << 2 << endl;
         }
    }

Measured memory_bytes: 3628
#!/user/bin/env pypy3
import sys
from typing import List


def fast_input():
    return sys.stdin.readline()[:-1]


def solve(cards: List[int]) -> int:
    sorted_cards = sorted(cards, reverse=True)
    alice = 0
    bob = 0
    for i, card in enumerate(sorted_cards):
        if i % 2 == 0:
            alice += card
        else:
            bob += card
    return alice - bob


def main():
    n = int(fast_input())
    a = list(map(int, fast_input().split()))
    result = solve(a)
    print(result)


main()


Measured memory_bytes: 10168
/*
lakshaygpt28
Lakshay Gupta
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
using vll = vector < ll >;

template < typename T > using OrderedSet = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;


#ifndef ONLINE_JUDGE
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << std :: endl;
}
template < typename Arg1, typename... Args >
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define debug(...)
#endif

#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const db PI = acos(-1);
const ll LINF = LLONG_MAX;
const int INF = INT_MAX, MOD = 1e9 + 7, N = 1e5 + 10;

int main() {
    fast_io();
    ll k, x;
    cin >> k >> x;
    for (ll i = max(-1000000ll, x - k + 1); i <= min(1000000ll, x + k - 1); i++) {
        cout << i << " ";
    }
    cout << "\n";
    return 0;
}


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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

map<int, int> mp;
set<int> st;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int n;cin>>n;
  vector<int> as(n);
  for(int i=0;i<n;i++){
    cin>>as[i];
    st.insert(as[i]);
    if(!mp[as[i]])mp[as[i]]=0;
    mp[as[i]]++;
  }
  vector<int> vs;
  for(auto v : st) {
    vs.push_back(v);
  }
  vs.push_back(-1);
  vs.push_back(-2);
  int max_len = 0;
  for(int i=0;i<vs.size();i++){
    int a = vs[i], b = vs[i+1], c = vs[i+2];
    int t = mp[a];
    if(a + 1==b)t += mp[b];
    if(a + 1==b&&b+1==c)t += mp[c];
    max_len = max(t, max_len);
  }
  cout<<max_len<<endl;

  return 0;
}


Measured memory_bytes: 6912
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(void){
  int n,m,i,j,pi,y;
  P ans[100010];
  vector<P> p[100010];
  cin >> n >> m;
  for (i=0;i<m;i++){
    cin >> pi >> y;
    p[pi-1].push_back(P(y,i));
  }
  for (i=0;i<n;i++) sort(p[i].begin(),p[i].end());
  for (i=0;i<n;i++){
    for (j=0;j<p[i].size();j++) ans[p[i][j].second]=P(i+1,j+1);
  }
  for (i=0;i<m;i++){
    int d=10,k=5;
    while (ans[i].first >= d){
      d*=10;
      k--;
    }
    for (j=0;j<k;j++) cout << 0;
    cout << ans[i].first;
    d=10;
    k=5;
    while (ans[i].second >= d){
      d*=10;
      k--;
    }
    for (j=0;j<k;j++) cout << 0;
    cout << ans[i].second << endl;
  }
  return 0;
}

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

int main() {
  int n, x; cin >> n >> x;
  vector<int> l(n);
  rep(i,n) {
    cin >> l[i];
  }
  int ans = 1;
  int now = 0;
  rep(i,n) {
    now += l[i];
    if (now <= x) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

        int N = sc.nextInt();
        int[] count = new int[4];

        for (int i = 0; i < N; i++ ){
            String ip = sc.next();
            if (ip.equals("AC")) {
                count[0]++;
            } else if (ip.equals("WA")) {
                count[1]++;
            } else if (ip.equals("TLE")) {
                count[2]++;
            } else if (ip.equals("RE")) {
                count[3]++;
            }
        }
      
        sc.close();

        System.out.println("AC x " + count[0]);
        System.out.println("WA x " + count[1]);
        System.out.println("TLE x " + count[2]);
        System.out.println("RE x " + count[3]);
    }
}


Measured memory_bytes: 59032