akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>
#include<math.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))
#define SORT(a,num,cmp) qsort((a),(num),sizeof(*(a)),cmp)

int cmp_int (const void *a, const void *b) {
  i32 d = *(i32 *)a - *(i32 *)b;
  return d == 0 ? 0 : d < 0 ? -1 : 1;
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *a = ALLOC (n, i32);
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, a + i);
  }
  SORT (a, n, cmp_int);
  i32 *cnt = ALLOC (n, i32);
  i32 len = 0;
  for (i32 i = 0; i < n;) {
    a[len] = a[i];
    for (; i < n && a[len] == a[i]; ++i) {
      cnt[len]++;
    }
    len++;
  }
  if (len > 3) {
    puts ("No");
    return;
  }
  if (len == 1) {
    puts (a[0] == 0 ? "Yes" : "No");
    return;
  }
  if (n % 3 != 0) {
    puts ("No");
    return;
  }
  i32 m = n / 3;
  for (i32 i = 0; i < len; ++i) {
    if (cnt[i] % m != 0) {
      puts ("No");
      return;
    }
  }
  if (len == 2) {
    puts (a[0] == 0 && cnt[1] == 2 * m ? "Yes" : "No");
  } else {
    puts ((a[0] ^ a[1]) == a[2] ? "Yes" : "No");
  }
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 892
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using ii = pair<int,int>;
using ll = long long;

const int N = 100005;
const int mod = 1000000007;

/*
 * okay operation 2 basically says that we sort the integers
 * on odd and even positions independently from each other
 * now to think about the operation 1 takes an integer and
 * will swap it until it goes into it's position
 * so i want to use operation 2 to make the sum of differences between
 * the sorted array and the real array as small as possible
 */

vector<int>odds,evens;
vector<int> compress(vector<int> a){
	vector<int> ord = a;
	sort(ord.begin(),ord.end());
	for(auto & x : a)
		x = lower_bound(ord.begin(),ord.end(), x) - ord.begin();
	return a;
}
int main() {
#ifdef ONLINE_JUDGE
	ios_base::sync_with_stdio(0);
	cin.tie(0);
#endif

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

	a = compress(a);

	for(int i = 0; i < n; i++)
		if(i&1)odds.push_back(a[i]);
		else evens.push_back(a[i]);

	sort(odds.begin(),odds.end());
	sort(evens.begin(),evens.end());
	a.clear();
	int ans = 0;
	for(int i = 0; i < n; i++){
		if(i&1)a.push_back(odds[i>>1]);
		else a.push_back(evens[i>>1]);
		if((i&1)!=(a[i]&1))ans++;
	}

	cout << (ans>>1) <<'\n';


	return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int cnt = 0;
	char s[7];
	scanf("%s",s);
	for (int i = 0; i < 3; ++i)
	{
		if(s[i] == '1')	++cnt;
	}
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define  ll long long int
#define mx 100007
ll dp[mx];
ll a[mx];

int main()
{
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];

    memset(dp,0,sizeof(dp));
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(i-a[j]>=0){
                if(dp[i-a[j]]==0){
                    dp[i]=1;
                    break;
                }
            }
        }
    }
    if(dp[k]==1) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
}


Measured memory_bytes: 4384
#include <stdio.h>

int main() {
    unsigned long N,w,wp2=0,wp1=0,i,k;
    unsigned int h,hp2=0,hp1=0;

    scanf("%ld",&N);
    scanf("%d",&hp1);
    scanf("%d",&h);

    if(h>hp1) w=h-hp1;
    else w=hp1-h;

    for(i=3;i<=N;i++) {
        wp2=wp1;
        wp1=w;
        hp2=hp1;
        hp1=h;

        scanf("%d",&h);
        if(h>hp1) w=wp1+h-hp1;
        else w=wp1+hp1-h;
        if(h>hp2) k=wp2+h-hp2;
        else k=wp2+hp2-h;

        if(w>k) w=k;
    }

    printf("%ld\n",w);
    return 0;
}

Measured memory_bytes: 128
//Name: Doctor's Strange Particles
//Level: 2
//Category: 全探索
//Note: 

/**
 * 一番上の行に対する照射方法を固定すると、それより下の行が全て一意に決まる。
 * したがって、一番上の行だけを全探索してシミュレーションすればよい。
 *
 * オーダーは O(2^W HW)。
 */
#include <iostream>
#include <array>

using namespace std;

array<int,1<<10> eff;

bool solve(bool first) {
    array<int,10> f;
    for(int r = 0; r < 10; ++r) {
        f[r] = 0;
        for(int c = 0; c < 10; ++c) {
            int v;
            cin >> v;
            f[r] |= (v << c);
        }
    }

    array<int,10> ans;
    for(int pat = 0; pat < (1<<10); ++pat) {
        int prev = f[0] ^ eff[pat];
        int pmask = pat;
        ans[0] = pat;
        for(int r = 1; r < 10; ++r) {
            ans[r] = prev;
            const int tmp = f[r] ^ eff[prev] ^ pmask;
            pmask = prev;
            prev = tmp;
        }
        if(prev == 0) break;
    }
    for(int r = 0; r < 10; ++r) {
        for(int c = 0; c < 10; ++c) {
            if(c > 0) cout << ' ';
            cout << !!(ans[r] & (1<<c));
        }
        cout << endl;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    for(int pat = 0; pat < (1<<10); ++pat) {
        eff[pat] = pat;
        for(int c = 0; c < 10; ++c) {
            if(pat & (1<<c)) {
                if(c > 0) eff[pat] ^= (1<<(c-1));
                if(c < 9) eff[pat] ^= (1<<(c+1));
            }
        }
    }

    bool first = true;
    int N;
    cin >> N;
    while(N-- && solve(first)) {
        first = false;
    }
    return 0;
}

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

int main(){
  int n,k; cin >>n >>k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >>a[i];
  vector<double>b(n+1,0); b[0]=a[0];
  for(int i=0; i<n; i++) b[i+1]=b[i]+(a[i]+1)/2.0;
  double ans=0;
  for(int i=0; i<n-k+1; i++) ans=max(b[i+k]-b[i],ans);
  cout <<fixed<<setprecision(10)<<ans;
return 0;}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
        long long int n,m;
        vector<long long int> x, y, num;
        cin >> n >> m;
        
        x = vector<long long int>(n);
        y = vector<long long int>(m);
        num = vector<long long int>((n > m)?n:m);
        iota(num.begin(), num.end(),1);
        for (auto i = 0; i < x.size(); ++i) {
                cin >> x[i];
        }
        for (auto i = 0; i < y.size(); ++i) {
                cin >> y[i];
        }
        
        long long int sumX = 2ll * inner_product(x.begin(), x.end(), num.begin(), 0ll) - (n + 1ll) * accumulate(x.begin(), x.end(), 0ll);
        long long int sumY = 2ll * inner_product(y.begin(), y.end(), num.begin(), 0ll) - (m + 1ll) * accumulate(y.begin(), y.end(), 0ll);
        
        sumX = (sumX % ((long long int)powl(10ll, 9ll) + 7ll));
        sumY = (sumY % ((long long int)powl(10ll, 9ll) + 7ll));
        long long int sum = sumX * sumY;
        
        cout << (sum % ((long long int)powl(10ll, 9ll) + 7ll)) << endl;
        return 0;
}

Measured memory_bytes: 2560
P=10**9+7
N=int(input())
A=list(map(int, input().split()))
ans=1
c=[0,0,0]
for i in range(N):
  a,f,k=A[i],-1,0
  for j in range(3):
    if c[j]==a:
      k+=1
      if f==-1:
        c[j]+=1
        f=j
  ans=(ans*k)%P
print(ans)

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


int main()
{
	int a, b;
	cin >> a >> b;
	string t;
	cin >> t;
	bool ans = true;
	for (int i = 0; i < a; i++) {
		if (!(t[i] >= '0' && t[i] <= '9')) {
			ans = false;
		}
	}
	if (t[a] != '-') {
		ans = false;
	}
	for (int i = a + 1; i < a + b + 1; i++) {
		if (!(t[i] >= '0' && t[i] <= '9')) {
			ans = false;
		}
	}
	if (ans)
		cout << "Yes" << endl;
	if (!ans)
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
/*
 * じょえチャンネル
 * 高評価・チャンネル登録よろしくおねがいします！
 * https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
 */
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)
template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}


signed main(){
	string s;
	int n;
	cin>>s>>n;
	string t,u;
	bool b=false;
	rep(i,n){
		int type;cin>>type;
		if(type==1)b=!b;
		else {
			int a;char c;cin>>a>>c;
			if(!b&&a==1)t.push_back(c);
			else if(!b)u.push_back(c);
			else if(b&&a==1)u.push_back(c);
			else t.push_back(c);
		}
	}
	if(!b){
		reverse(all(t));
		cout<<t<<s<<u<<endl;
	}else {
		reverse(all(u));
		reverse(all(s));
		cout<<u<<s<<t<<endl;
	}
}


Measured memory_bytes: 1088
#include <bits/stdc++.h>
#define rep(i,n) REP(i,0,n)
#define REP(i,l,r) for(int i=l;i<r;++i)
#define int long long
#ifdef DEBUG
#define dout cout
#else
std::stringstream dout;
#endif
using namespace std;
typedef pair<int,int> P;
//other libs

signed main(int argc, char * argv[]) {
	int a;
	cin>>a;
	string s;
	cin>>s;
	if(a<3200)cout<<"red"<<endl;
	else cout<<s<<endl;
}

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

int main(){
    int n;
    cin >> n;
    int t[n+1],x[n+1],y[n+1];
    for(int i=1;i<n+1;i++){
        cin >> t[i] >> x[i] >> y[i];
    }
    t[0] = 0;x[0] = 0;y[0] = 0;
    for(int i=0;i<n;i++){
       int dt = t[i+1]-t[i];
        int dx = abs(x[i+1] - x[i]);
        int dy = abs(y[i+1] - y[i]);
        if( !((dt-(dx+dy)) >=0&&(dt-(dx+dy))%2==0)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;


}

Measured memory_bytes: 1408
class Stack:

    def __init__(self):
        self.top = 0
        self.stack = [0] * 1000

    def is_empty(self):
        return self.top == 0

    def push(self, x):
        self.top += 1
        self.stack[self.top] = x

    def pop(self):
        if self.is_empty():
            raise RuntimeError
        self.top -= 1
        return self.stack[self.top + 1]


def main():
    A = input().split(' ')
    S = Stack()

    for a in A:

        if a == '+':
            y = S.pop()
            x = S.pop()
            S.push(x + y)
        elif a == '-':
            y = S.pop()
            x = S.pop()
            S.push(x - y)
        elif a == '*':
            y = S.pop()
            x = S.pop()
            S.push(x * y)
        else:
            S.push(int(a))

    print(S.pop())


if __name__ == "__main__":
    main()



Measured memory_bytes: 5604
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val A = Array.fill(N)(sc.nextInt())
    val M = new Array[Int](N)

    var f = false
    var i = 0
    var sr = 0L
    var sl = 0L
    while (i < N) {
      if (f)
        sr += A(i)
      sl += A(i)
      f = !f
      i += 1
    }
    val X1 = sl - 2 * sr

    // x1 は山1に降った雨の量
    // x2 = A(1) - x1
    // ...
    // xN = A(N-2) - xN-2
    // xN + x1 == A(N-1)かどうか？
    // solveは, これを達成する時のx1の値を返す.
    def ans(x1: Long): Array[Long] = {
      val arr = new Array[Long](N)
      var nx = x1 / 2
      var i = 0
      while (i < N) {
        arr(i) = nx * 2
        nx = A(i) - nx
        i += 1
      }
      arr
    }

    println(ans(X1).mkString(" "))
  }

}


Measured memory_bytes: 69644
#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 ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

vector<int> color;
vector<vector<int>> e;
// 2部グラフ判定
bool dfs(int i,int c) {
    color[i] = c;
    for(auto x:e[i]) {
        if (color[i] == color[x]) return false;
        if (color[x] == 0 && !dfs(x,-c)) return false;
    }
    return true;
}

int main(void)
{
    IOS
    const int INF = 1e8;
    int n; cin >> n;
    color.resize(n);
    e.resize(n);
    int ans = 0;

    vector<vector<int>> v(n,vector<int>(n,INF));
    REP(i,n) v[i][i] = 0;
    REP(i,n) {
        string s; cin >> s;
        REP(j,s.size()) {
            if (s[j] == '1') {
                v[i][j] = 1;
                e[i].push_back(j);
            }
        }
    }

    if (!dfs(0,1)) ans = -1;
    else {
        // ワーシャルフロイド法
        REP(k,n) REP(i,n) REP(j,n) {
            v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
        }

        REP(i,n) REP(j,n) {
            ans = max(ans,v[i][j]);
        }
        ans++;

    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
string s;
int main(){
	int ans=0,n=0;
	cin >> s;
	for(int i=0;s[i];i++){
		ans+=s[i]-'0';
		n*=10;
		n+=s[i]-'0';
	}
	if(n%ans==0){
		cout << "Yes";
	}else{
		cout << "No"; 
	} 
	return 0;
}

Measured memory_bytes: 256
def main():
    s = list(input())
    n = len(s)

    ans = 0
    l, r = 0, n-1
    while l < r:
        if s[l] == "x" and s[r] == "x":
            l += 1
            r -= 1
        elif s[l] == "x":
            l += 1
            ans += 1
        elif s[r] == "x":
            r -= 1
            ans += 1
        elif s[l] == s[r]:
            l += 1
            r -= 1
        else:
            print(-1)
            exit()
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 49520
#include <iostream>
#include <vector>

struct union_find {
	long long N;					// the number of nodes
	long long M;					// the number of trees
	std::vector<long long> parent;	// parent[i] := the direct parent of i
	std::vector<long long> size;	// size[i] := the number of nodes in the tree containing i

	union_find(long long n) : N(n), M(n) {
		parent.resize(n, -1);
		size.resize(n, 1);
	}

	long long root(long long i) {
		if (parent[i] == -1) return i;
		else return parent[i] = root(parent[i]);
	}

	bool is_united(long long i, long long j) {
		return (root(i) == root(j));
	}

	// true : unite succeeded
	bool unite(long long i, long long j) {
		i = root(i); j = root(j);
		if (i == j) return false;
		if (size[i] < size[j]) std::swap(i, j);
		parent[j] = i;
		size[i] += size[j];
		M--;
		return true;
	}
};

int main() {
	long long n, q;
	std::cin >> n >> q;
	union_find uf(n);
	while (q--) {
		long long com, x, y;
		std::cin >> com >> x >> y;
		if (com == 0) uf.unite(x, y);
		else std::cout << (uf.is_united(x, y)?1:0) << '\n';
	}
}


Measured memory_bytes: 3216
def f(m):
  k = 0
  while m > 0:
    k += m%10
    m //= 10
  return k

n = int(input())

m = f(n)
p = 1
while p <= n:
  m = max(m, f((n//p)*p-1))
  p *= 10
  
print(m)

Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.next());
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        if((a+k-1)/k*k <= b){
            System.out.println("OK");
        }else{
            System.out.println("NG");
        }
        sc.close();
    }
}

Measured memory_bytes: 35648
K,N=map(int,input().split(' '))
A=list(map(int,input().split(' ')))
#print(A)
D=[]
for i in range(len(A)):
    if i!=len(A)-1:
        d=A[i+1]-A[i]
    else:
        d=K-A[i]+A[0]
    D.append(d)

D.sort()
D.pop()
#print(D)

print(sum(D))

Measured memory_bytes: 25800
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

		int N = sc.nextInt();
		int M = sc.nextInt();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		for (int i = 0; i < N; i++) {
			int K = sc.nextInt();
			for (int j = 0; j < K; j++) {
				int Ai = sc.nextInt();
				if (map.get(Ai) != null) {
					map.put(Ai, map.get(Ai) + 1);
				} else {
					map.put(Ai, 1);
				}
			}
		}

		int result = 0;
		for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
			if (entry.getValue() == N ) {
				result++;
			}
		}

		System.out.println(result);
	}
}

Measured memory_bytes: 23764
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    k = int(input())
    s = input()

    if len(s) <= k:
        print(s)
    else:
        print(s[:k], '...', sep='')


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


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

using namespace std;

typedef long long lli;

const int N = 200000 + 10;

struct Node
{
	lli sum, add;
};

vector<int> G[N];
int cntl[N], cntr[N];
Node stree[N*4];

void push_up(int index)
{
	stree[index].sum = stree[index*2].sum + stree[index*2+1].sum;
}

void push_down(int index, int begin, int end)
{
	int mid = (begin + end) / 2;
	stree[index*2].add += stree[index].add;
	stree[index*2].sum += 1LL * (mid - begin + 1) * stree[index].add;
	stree[index*2+1].add += stree[index].add;
	stree[index*2+1].sum += 1LL * (end - mid) * stree[index].add;
	stree[index].add = 0;
}

void update(int index, int begin, int end, int left, int right, int x)
{
	int mid;
	if (left <= begin && right >= end)
	{
		stree[index].add += x;
		stree[index].sum += 1LL * (end - begin + 1) * x; 
		return;
	}
	if (stree[index].add) push_down(index, begin, end);
	mid = (begin + end) / 2;
	if (right <= mid) update(index * 2, begin, mid, left, right, x);
	else if (left > mid) update(index * 2 + 1, mid + 1, end, left, right, x);
	else
	{
		update(index * 2, begin, mid, left, mid, x);
		update(index * 2 + 1, mid + 1, end, mid + 1, right, x);
	}
	push_up(index);
}

int main()
{
	lli res;
	int n, u, v, i, j;
	scanf("%d", &n);
	for (i=0; i<n-1; i++)
	{
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		if (v < u) cntl[u] ++; else cntr[u] ++;
		G[v].push_back(u);
		if (u < v) cntl[v] ++; else cntr[v] ++;
	}
	res = 0;
	update(1, 1, n, 1, n, 1);
	for (i=n-1; i>=1; i--) update(1, 1, n, 1, i, cntl[i+1] - 1);
	res += stree[1].sum;
	for (i=1; i<n; i++)
	{
		update(1, 1, n, i, n, cntr[i] - 1);
		for (j=0; j<G[i].size(); j++)
		{
			u = G[i][j];
			if (u > i) 
			{
				cntl[u] --;
				update(1, 1, n, i, u - 1, -1);
			}
		}
		res += stree[1].sum;
	}
	printf("%lld\n", res);
	return 0;
}

Measured memory_bytes: 24700
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7


def main():
    n = int(input())
    return int(n*(n+1) // 2)



print(main())


Measured memory_bytes: 5420
#include <iostream>
#include <vector>
#include <ctime>
#include <array>
#include <cmath>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <limits>  //std::numeric_limits<int>::max(), min()


class MyPow {
  private:
  typedef long long ll;
  std::unordered_map<ll, ll> memo;

  public:
  ll MOD = std::numeric_limits<long long>::max();

  MyPow ( ll a_ ) {
    memo[0] = 1 % MOD;
    memo[1] = a_ % MOD;
  }

  ll power ( ll p ) {
    if ( memo.count(p) != 0 ) return memo[p];
    return memo[p] = ((power(p/2)%MOD) * (power(p-p/2)%MOD)) % MOD;
  }
};

namespace MyMod {
  typedef long long ll;
  ll mod = 1000000007LL;

  ll add ( ll a, ll b) {
    return ((a%mod) + (b%mod))%mod;
  }

  ll sub ( ll a, ll b) {
    return ( a%mod + mod - b%mod)%mod;
  }

  ll mul ( ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
  }

  ll div ( ll a, ll b) {
    MyPow k(b); k.MOD = mod;
    return ((a%mod) * k.power(mod-2)) % mod;
  }
};

long long combination(long long N, long long r) {
  long long numerator = 1;
  for(long long i=N-r+1; i<=N; i++) numerator = MyMod::mul(numerator, i);

  long long denominator = 1;
  for(long long i=1; i<=r; i++ ) denominator = MyMod::mul(denominator, i);

  return MyMod::div ( numerator, denominator );
}

int main (void) {
  int N, M, K;
  std::cin >> N >> M >> K;

  // sum x
  long long sumx = 0;
  for(int i=1; i<=M-1; i++) sumx = MyMod::add(sumx, MyMod::mul(MyMod::mul(MyMod::mul(N,N),i), M-i) );

  // sum y
  long long sumy = 0;
  for(int i=1; i<=N-1; i++) sumy = MyMod::add(sumy, MyMod::mul(MyMod::mul(MyMod::mul(M,M),i), N-i) );

  // comb
  long long comb = combination(N*M-2, K-2);

  // ans
  long long ans = MyMod::mul(comb, MyMod::add(sumx,sumy));
  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        x: usize,
        y: usize,
    }

    println!("{}", x + y/2);
}


Measured memory_bytes: 4352
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
 
did = "-" * k
ans = 0
for i in t:
    if i == "r":
        if did[-k] == "p":
            did += "-"
        else:
            did += "p"
            ans += p
    elif i == "s":
        if did[-k] == "r":
            did += "-"
        else:
            did += "r"
            ans += r
    else:
        if did[-k] == "s":
            did += "-"
        else:
            did += "s"
            ans += s
 
print(ans)

Measured memory_bytes: 9408
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

// keyenence keyenccce
void solve() {
    string s; cin >> s;
    bool f = false;
    if(s.substr(s.size()-7, 7) == "keyence") 
    f = true;
    if(s.substr(0, 1) == "k" && s.substr(s.size()-6, 6) == "eyence")
    f = true;
    if(s.substr(0, 2) == "ke" && s.substr(s.size()-5, 5) == "yence")
    f = true;
    if(s.substr(0, 3) == "key" && s.substr(s.size()-4, 4) == "ence")
    f = true;
    if(s.substr(0, 4) == "keye" && s.substr(s.size()-3, 3) == "nce")
    f = true;
    if(s.substr(0, 5) == "keyen" && s.substr(s.size()-2, 2) == "ce")
    f = true;
    if(s.substr(0, 6) == "keyenc" && s.substr(s.size()-1, 1) == "e")
    f = true;
    if(s.substr(0, 7) == "keyence")
    f = true;
    if(f) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

    solve();
    return 0;
}
 


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")

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

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const ld EPS = 1e-6;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const char nl = '\n';

template <typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <typename T> inline T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> void ckmin(T& a, T b) { a = min(a, b); }
template <class T> void ckmax(T& a, T b) { a = max(a, b); }

// (Integer/Long).bitCount(x)
int pct(int x) { return __builtin_popcount(x); }
int pctll(ll x) { return __builtin_popcountll(x); }

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
}

// Binary Exponentiation
ll pow(ll b, ll e, ll m = 0LL, ll ans = 1LL) { while (e) { if (e & 1LL) { ans *= b; if (m) ans %= m; } b *= b, e >>= 1LL; if (m) b %= m; } return ans; }



void solve(int tcn) {
	string s;
	cin >> s;
	if (s[sz(s) - 1] == 's') {
		cout << s << "es" << endl;
	}
	else {
		cout << s << "s" << endl;
	}
}

int main() {
    setIO();

    int t = 1; //cin >> t;
	for (int i = 1; i <= t; ++i) {
		//cout << "Case #" << i << ": ";
		solve(i);
	}
	return 0;
}

Measured memory_bytes: 3672
s = input()

def chr_to_index(chr):#文字列を受け取って一文字ずつ配列に入れる
  a = []
  n = len(chr)
  for i in range(n):
    a.append(chr[i])
  return a

my = chr_to_index(s)

mae = int(my[0])*10 + int(my[1])
ato = int(my[2])*10 + int(my[3])

if mae in range(1,13) and ato in range(1,13):
    print("AMBIGUOUS")
elif mae in range(1,13):
    print("MMYY")
elif ato in range(1,13):
    print("YYMM")
else:
    print("NA")


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

int main() {
    vector<int> h(10);
    for (int i = 0; i < 10; ++i) {
        cin >> h[i];
    }
    sort(h.rbegin(), h.rend());
    for (int i = 0; i < 3; ++i) {
        cout << h[i] << endl;
    }
}



Measured memory_bytes: 3080
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

static const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<int> a(n), b(n), c(n), d(m), e(m), f(m);
  map<int, int> hm, vm;
  for (int i = 0; i < n; i++) {
    scanf("%d %d %d", &a[i], &b[i] ,&c[i]);
    hm.insert({a[i], 0});
    hm.insert({b[i], 0});
    vm.insert({c[i], 0});
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &d[i], &e[i], &f[i]);
    hm.insert({d[i], 0});
    vm.insert({e[i], 0});
    vm.insert({f[i], 0});
  }

  vector<int> h(hm.size()), v(vm.size());
  int counter = 0;
  for (auto p : hm) {
    h[counter] = p.first;
    hm[p.first] = counter++;
  }
  counter = 0;
  for (auto p : vm) {
    v[counter] = p.first;
    vm[p.first] = counter++;
  }

  vector<vector<vector<bool>>> connect(h.size() + 1, vector<vector<bool>>(v.size() + 1, vector<bool>(4, true)));
  for (int i = 0; i < n; i++) {
    int s = hm[a[i]], t = hm[b[i]], u = vm[c[i]];
    for (int j = s; j < t; j++) {
      connect[j + 1][u][1] = false;
      connect[j + 1][u + 1][3] = false;
    }
  }
  for (int i = 0; i < m; i++) {
    int s = vm[e[i]], t = vm[f[i]], u = hm[d[i]];
    for (int j = s; j < t; j++) {
      connect[u][j + 1][0] = false;
      connect[u + 1][j + 1][2] = false;
    }
  }

  queue<pair<int, int>> q;
  int x0 = 0, y0 = 0;
  for (int i = 0; i < h.size(); i++)
    if (h[i] >= 0) {
      x0 = i;
      break;
    }
  for (int i = 0; i < v.size(); i++)
    if (v[i] >= 0) {
      y0 = i;
      break;
    }
  q.push({x0, y0});

  vector<vector<bool>> visited(h.size() + 1, vector<bool>(v.size() + 1));
  visited[x0][y0] = true;
  while (!q.empty()) {
    auto p = q.front();
    q.pop();

    int x = p.first, y = p.second;
    for (int i = 0; i < 4; i++)
      if (connect[x][y][i]) {
        int xx = x + dir[i][0], yy = y + dir[i][1];
        if (xx >= 0 && xx <= h.size() && yy >= 0 && yy <= v.size() && !visited[xx][yy]) {
          visited[xx][yy] = true;
          q.push({xx, yy});
        }
      }
  }

  bool inf = false;
  long long ans = 0;
  for (int i = 0; i <= h.size(); i++)
    for (int j = 0; j <= v.size(); j++)
      if (visited[i][j]) {
        if (i == 0 || i == h.size() || j == 0 || j == v.size())
          inf = true;
        else
          ans += 1LL * (h[i] - h[i - 1]) * (v[j] - v[j - 1]);
      }

  if (inf)
    printf("INF\n");
  else
    printf("%lld\n", ans);

  return 0;
}

Measured memory_bytes: 638652
#include <stdio.h>
char snake[201];
int main() {
	int N, I;
	int i, j, flag;
	scanf("%d", &N);
	for(I = 0; I < N; ++ I) {
		scanf("%s", snake);
		j = 0; flag = 0;
		if(snake[0] == '>') {
			if(snake[1] == '\'') {
				for(i = 2; ; ++ i) {
					if(flag == 0) {
						if(snake[i] == '#') {
							if(j > 0) flag = 1;
							else {
								printf("NA\n");
								break;
							}
						} else if(snake[i] == '=') j ++;
						else {
							printf("NA\n");
							break;
						}
					} else {
						if(snake[i] == '=') j --;
						else {
							if(j == 0 && snake[i++] == '~' && snake[i] == 0) printf("A\n");
							else printf("NA\n");
							break;
						}
					}
				}
			} else if(snake[1] == '^') {
				for(i = 2; ; i += 2) {
					if(snake[i] == 'Q' && snake[i + 1] == '=') ++ j;
					else break;
				}
				if(j > 0 && snake[i++] == '~' && snake[i++] == '~' && snake[i] == 0) printf("B\n");
				else printf("NA\n");
			} else printf("NA\n");
		} else printf("NA\n");
	}
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb push_back;
#define sp " ";
void vout(vector<int> v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    bool d=false;
    for(int i=1;i<=b;i++){
        if((a*i)%b==c) {d=true;break;}
    }
    cout<<(d?"YES":"NO")<<endl;
}

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

#define MAXN (100010)

int n, k;
int h[MAXN];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", h + i);
    }
    std::sort(h + 1, n + h + 1);
    int ans = INT_MAX;
    for (int i = 1; i + k - 1 <= n; ++i) {
        ans = std::min(ans, h[i + k - 1] - h[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll a,b,k;
	cin >> a >> b >> k;
	ll ans1 = 0;
	ll ans2 = b;
	if(k<a) ans1 = a-k;
	else ans2 = b-(k-a);
	if(ans2<0) ans2 = 0;
	cout << ans1 << " " << ans2 << '\n';
	return 0;
}



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

#define int           long long 
#define S             second
#define F             first
#define pb            push_back
#define all(c)        (c).begin(),(c).end()
#define rall(c)       (c).rbegin(),(c).rend() 
#define lb            lower_bound
#define si(c)         (int)((c).size())
#define lcm(a, b)      (a * (b / __gcd(a,b)))  
#define inf           (int)(1e18)
#define endl          '\n'
#define mp            make_pair
#define time(s)       (double(clock()-s)/double(CLOCKS_PER_SEC))
#define debug(args...)    _F(#args, args)
#define vi            std::vector<int>
#define pii           pair<int, int> 
#define vpi           vector<pii>

clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template<typename T> void _F(const char *name, T arg1){ cerr << name << " = " << arg1 << endl;}
template<typename T, typename... Args> void _F(const char *names, T arg1, Args... args)
{ const char *name = strchr(names, ',');cerr.write(names, name-names) << " = " << arg1 << endl;_F(name+2, args...);}

template< typename T1, typename T2 > istream& operator>>(istream& in, pair<T1, T2> &q){ in >> q.F >> q.S; return in;}
template< typename T1, typename T2 > ostream& operator<<(ostream& out, pair<T1, T2> &q){ out << q.F << " " << q.S; return out;}
template< typename T1, typename T2 > pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F+p2.F, p1.S+p2.S};}
template< typename T1, typename T2 > pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F-p2.F, p1.S-p2.S};}
template< typename T1, typename T2 > bool operator<(pair<T1, T2> p1, pair<T1, T2> p2){ return p1 < p2 ;}

template<typename T> void Unique(vector<T> &v){
    sort(all(v)), v.resize(distance(v.begin(), unique(all(v))));
}

void solve(int &test) {
	int h, w, m;
	cin >> h >> w >> m;

	int row[h+1], col[w+1];
	memset(row, 0, sizeof(row));
	memset(col, 0, sizeof(col));

	vi r[h+1];

	for(int i = 0; i < m; i++) {
		int hh, ww;
		cin >> hh >> ww;
		row[hh]++, col[ww]++;

		r[hh].pb(ww);
	}

	set<pair<int, int> > s;
	for(int i = 1; i <= w; i++)
		s.insert(mp(col[i], i));
	int ans = 0;

	for(int i = 1; i <= h; i++) {
		for(auto u : r[i]) {
			ans = max(ans, col[u]+row[i]-1);
			s.erase(mp(col[u], u));
		}
		if(si(s))ans = max(ans, row[i]+(*rbegin(s)).F);
		for(auto u : r[i]) {
			s.insert(mp(col[u], u));
		}
	}

	cout << ans << endl;
}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);   
    start = clock(); 

   
    int t = 1;
    // cin >> t;

    cout << fixed << setprecision(2);
     
    for(int i = 1; i <= t; ++i){
        solve(i); 
    }

    cerr << time(start);
    return 0;
}

Measured memory_bytes: 43688
#include <stdio.h>

int main()
{
	int input_m, input_n_min, input_n_max;
	int score_P[200];
	int score_gap, max_score_gap = 0;
	int answer_n;
	int counter_i;
	
	for( ; ; )
	{
		scanf("%d %d %d", &input_m, &input_n_min, &input_n_max);
		if(input_m == 0 && input_n_min == 0 && input_n_max == 0)
			break;
		
		for(counter_i = 0 ; counter_i < input_m ; counter_i++)
			scanf("%d", &score_P[counter_i]);
		
		for(counter_i = input_n_min - 1 ; counter_i <= input_n_max - 1 ; counter_i++)
		{
			score_gap =  score_P[counter_i] - score_P[counter_i + 1];
			if(score_gap >= max_score_gap)
			{
				max_score_gap = score_gap;
				//printf("max_score_gap: %d\n", max_score_gap);
				answer_n = counter_i + 1;
			}
		}
		
		printf("%d\n", answer_n);
		
		max_score_gap = 0;
		answer_n = 0;
		
	}
	return 0;
}



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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define TS to_string
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}

//-----------------------------------------
class segment_tree{
  private:
    ll N = 1;
    vector<vector<ll>> data;
  public:

    segment_tree(string s){
      ll m = s.size();
      while(N < m) N *= 2;
      data.resize(2*N, vll(26,0));

      for(int i=0;i<m;i++) update(i,s[i]);
    }

    // b -> a;
    void update(ll k, char a, char b = '$'){
      k += N - 1;
      if(b != '$') data[k][b - 'a']--;
      data[k][a - 'a']++;
      while(k > 0){
        k = (k-1) / 2;
        for(ll i = 0; i < 26; i++){
          data[k][i] = data[k * 2 + 1][i] +  data[k * 2 + 2][i];
        }
      }
    }

    // [a,b) のクエリを処理する
    vll query_(ll a, ll b, ll k, ll l, ll r){
      // [a,b)　と [l,r) が交差しない時
      if(r <= a || b <= l) return {}; 

      // 完全に含まれている時
      if(a <= l && r <= b) return data[k];
      else{
        ll mid = (l + r) / 2;
        // 2つの子の最小値
        vll vl = query_(a,b,k*2+1,l,mid);
        vll vr = query_(a,b,k*2+2,mid,r);

        if(vl.size() == 0) return vr;
        if(vr.size() == 0) return vl;

        vll res(26,0);
        for(ll i = 0; i < 26; i++){
          res[i] = vl[i] + vr[i];
        }
        return res;
      }
    }

    int query(ll a, ll b){
      vll tmp = query_(a, b, 0, 0, N);
      ll res = 0;
      for(ll i = 0; i < 26; i++){
        if(tmp[i]) res++;
      }
      return res;
    }
};
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  ll n;
  string s;
  cin >> n >> s;
  segment_tree tree(s);

  ll q;
  cin >> q;
  REP(i,q){
    ll com;
    cin >> com;
    if(com == 1){
      ll j; char a;
      cin >> j >> a;
      tree.update(j-1,a,s[j-1]);
      s[j-1] = a;
    }
    else{
      ll lef, rig;
      cin >> lef >> rig;
      cout << tree.query(lef-1,rig) <<endl;
    }
  }



  return 0;
}



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

long long_abs(long k){
    if(k>=0){
        return k;
    }else{ 
        return -k;
    }
}

int main(){

    int xmax=100;
    int ymax=100;
    long H, htemp;

    int N;
    cin >> N;

    int x[N], y[N];
    long h[N];

    for(int i=0; i<N; i++){
        cin >> x[i] >> y[i] >> h[i];
    }

    H=0;
    htemp=0;

    bool flag;

    flag=false;
    for(int i=0; i<=xmax; i++){
        for(int j=0; j<=ymax; j++){
            for(int k=0; k<N; k++){
                htemp= long_abs( (long) x[k]-i )+long_abs( (long) y[k]-j )+h[k];
                
                //cout << "i j htemp H = " << i << " " << j << " " << htemp << " " << H << endl;
                if(H == 0){
                    if( h[k] == 0 && htemp >= H ){
                        continue;
                    }
                    H=htemp;
                }else if(htemp != H){
                    if( h[k] == 0 && htemp > H ){
                        continue;
                    }
                    flag=true;
                    //break; //next j
                }
            } 
            if(flag){
                flag=false;
                H=0;
                continue;
            }

            flag=false;
            for( int k=0; k<N; k++){
                htemp= H-long_abs( (long) x[k]-i )-long_abs( (long) y[k]-j );
                if(htemp < 0) htemp=0;
                if( htemp != h[k] ){
                    //cout << "k= " << k << endl;
                    flag=true;
                    break;
                }               
            }
            if(flag){
                flag=false;
                H=0;
                //cout << "i j htemp H = " << i << " " << j << " " << htemp << " " << H << endl;
                continue;
            }

            cout << i << " " << j << " " << H << endl;
            return 0;            
        }
    }


    return 1;
}


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

using namespace std;
typedef long long ll;

#define rep(i , j , n) for(long long i = j ; i <= n ; i++)
#define per(i , j , n) for(long long i = j ; i >= n ; i--)
const ll N = 123456;

int a[N];
int k;
int check(int x , int n) {
    int reqd = 0;

    vector < int > ans;

    rep(i , 1 , n) {
        ans.push_back(a[i] % x);
    }

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

    int l = 0;
    int r = ans.size() - 1;
    int rem = 0;

    while(l <= r) {
        if(rem <= 0) {
            rem += ans[l];
            reqd += ans[l];
            l++;
        }
        else {
            rem -= (x - ans[r]);
            reqd += (x - ans[r]);
            r--;
        }
    }

    if(reqd > 2 * k || rem != 0) return 0;
    return 1;
}

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

    int n;

    cin >> n >> k;

    rep(i , 1 , n) cin >> a[i];

    int sum = 0;

    rep(i , 1 , n) sum += a[i];

    int ans = 1;

    for(int i = 1 ; i * i <= sum ; i++) {
        if(sum % i == 0) {
          // cout << i  << " " << sum / i << endl;
            if(check(i , n)) {
                ans = max(ans , i);
            }
            if(check(sum / i , n)) {
                ans = max(ans , sum / i);
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

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

    string str;
    cin >> str;
    int len_str = str.length();

    vector<int> s(len_str+1,0);
    vector<int> a(len_str,0);
    for (int i = 1; i < len_str; ++i) {
        if(str[i-1] == 'A'&&str[i] == 'C'){
            a[i] = 1;
        }
    }

    for (int j = 0; j < len_str ; ++j) {
        s[j+1] = s[j] + a[j];
    }



    for (int k = 0; k <  q; ++k) {
        int l,r;
        cin >> l;
        cin >> r;
        cout << s[r] - s[l] << endl;
    }

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x,h,w) (y) < 0 || (h) <= (y) || (x) < 0 || (w) <= (x)
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    string s; cin >> s;
    reverse(all(s));
    int n = s.length();

    vector<VL> dp(n + 1, VL(13, 0));
    dp[0][0] = 1;
    ll digit = 1;
    FOR(i, 0, n) {
        if (i)(digit *= 10) %= 13;
        if (s[i] == '?') {
            FOR(num, 0, 10)FOR(j, 0, 13) {
                (dp[i + 1][(j + num * digit) % 13] += dp[i][j]) %= mod;
            }
        }
        else {
            int num = (s[i] - '0');
            FOR(j, 0, 13) {
                (dp[i + 1][(j + num * digit) % 13] += dp[i][j]) %= mod;
            }
        }
    }

    cout << dp[n][5] << "\n";

}


Measured memory_bytes: 13648
/**
 * @author yuzining
 * @date 2020/07/12 18:47
*/

#ifdef local
#include "D:\vscode\acm\local.hpp"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  Main();
  return 0;
}
#endif

void Main() {
  int l, r, d; cin >> l >> r >> d;
  int ans = 0;
  for(int i = l; i <= r; i++) {
    if(i % d == 0) {
      ans++;
    }
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3644
#include <stdio.h>

struct dice {
	int label[6];
};

/* dice label(record as 0base)
 *    1
 *  4 2 3 5
 *    6
 */

char *map_dir = "WNES";
#define MAP(_, a, b, c, d, e, f) {a-1, b-1, c-1, d-1, e-1, f-1}
int dice_map[4][6] = {
	MAP(W, 3, 2, 6, 1, 5, 4),
	MAP(N, 2, 6, 3, 4, 1, 5),
	MAP(E, 4, 2, 1, 6, 5, 3),
	MAP(S, 5, 1, 3, 4, 6, 2),
#undef MAP
};

void dice_init(struct dice *a)
{
	for(int i = 0; i < 6; i++)
		scanf("%d", &a->label[i]);
}

void dice_rot(struct dice *a, char rot)
{
	struct dice b;
	int i, d = 0;

	for (i = 0; i < 4; i++)
		if (map_dir[i] == rot) {
			d = i;
			break;
		}
	for(i = 0; i < 6; i++) {
		int p = dice_map[d][i];
		b.label[i] = a->label[p];
	}
	*a = b;
}

int
main(void)
{
	struct dice a;
	char cmd[101];

	dice_init(&a);
	scanf("%s", cmd);

	for (char *c = cmd; *c != '\0'; c++)
		dice_rot(&a, *c);

	printf("%d\n", a.label[0]);

	return 0;
}



Measured memory_bytes: 2136
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> p = new ArrayList<>();
        List<Integer> p2 = new ArrayList<>();
        String result = "NO";
        for(int i=0;i<n;i++){
            int tmp = sc.nextInt();
            p.add(tmp);
            p2.add(tmp);
        }
        sc.close();
        p.sort((a,b)->a-b);
        int count = 0;
        for(int i=0;i<n;i++){
            if(p.get(i)!=p2.get(i))count++;
        }
        if(count==2 || count==0)result="YES";
        System.out.println(result);
    }
}

Measured memory_bytes: 27732