akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 40000
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n,a,b;
	cin>>a>>b;
	for(i=1;i<=100000;i++){
		k=i*0.08;
		l=i*0.1;
		if(k==a&&l==b)
			break;
	}
	if(i==100001){
		cout<<"-1";
	}
	else cout<<i;
	return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
ps = gets.chomp.split.map(&:to_i)

possible = true
swapped = false
swappable = nil
(1..n).each do |n|
  p = ps[n - 1]
  next if p == n

  if swappable
    if !swapped && swappable[:got] == n && swappable[:want] == p
      swapped = true
      swappable = nil
    else
      possible = false
      break
    end
  else
    swappable = { got: p, want: n }
  end
end

puts possible ? 'YES' : 'NO'


Measured memory_bytes: 1788
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        long[] march = new long[5];
        for (int i = 0; i < n; i++) {
            String s = in.ns();
            if(s.charAt(0)=='M') march[0]++;
            else if(s.charAt(0)=='A') march[1]++;
            else if(s.charAt(0)=='R') march[2]++;
            else if(s.charAt(0)=='C') march[3]++;
            else if(s.charAt(0)=='H') march[4]++;
        }
        long ans = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = i+1; j < 4; j++) {
                for (int k = j+1; k < 5; k++) {
                    ans += march[i]*march[j]*march[k];
                }
            }
        }
        out.println(ans);
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32648
s = input()
n = len(s)
d = [s[0]]
for i in range(1,n):
  if s[i]=="C" and s[i-1]=='B':
    d.pop()
    d.append("x")
  else:
    d.append(s[i])
q = "".join(d)
cou = 0
cou_a = 0
l = len(q)
for i in range(l):
  if q[i]=="A":
    cou_a += 1
  elif q[i]=="x":
    cou +=  cou_a
  else:
    cou_a = 0
print(cou)

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

int main(){
  int a, b;
  cin >> a >> b;
  if(a < b){
    cout << "a" << " < " << "b" << endl;
  } else {
    if(a > b){
      cout << "a" << " > " << "b" << endl;
    } else {
      if(a == b){
	cout << "a" << " == " << "b" << endl;
      }
    }
  }
}

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

#define MAX 50

using namespace std;

int main(){

 long long n;

  n=int(n);

  cin>>n;

  char str[MAX];  

    int i = 0;

  

    while (n > 0) { 
        // Find remainder 

        int rem = n % 26; 
  
        if (rem == 0) { 

            str[i++] = 'z'; 

            n = (n / 26) - 1; 
        } 
        
        else{ 
            str[i++] = (rem - 1) + 'a'; 
            n = n / 26; 

        } 

    } 

    str[i] = '\0'; 
    reverse(str, str + strlen(str)); 

    cout << str << endl; 

}


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

using namespace std;

typedef int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int h,w;
char a[125][125];

// graph
unordered_map<int,int> fl[128*128*2];

vi bfspath(int s,int t){
  // not dfs but bfs
  vector<bool> used(128*128*2,false);
  vi bef(128*128*2,-1);
  queue<int> Q;
  Q.push(s);
  used[s] = true;
  while(!Q.empty()){
    int p = Q.front(); Q.pop();
    for(pii P : fl[p]){
      int to = P.first;
      int c = P.second;
      if(c==0)continue;
      if(used[to])continue;
      used[to] = true;
      bef[to] = p;
      if(to==t){
        queue<int> dummy;
        swap(Q,dummy);
        break;
      }
      Q.push(to);
    }
  }
  if(bef[t]==-1)return vi();
  vi ret;
  int cur = t;
  ret.push_back(cur);
  while(cur != s){
    cur = bef[cur];
    ret.push_back(cur);
  }
  reverse(ALL(ret));
  return ret;
}

int main(){
  scanf("%d%d",&h,&w);
  REP(i,h)scanf("%s",a[i]);
  int si,sj,ti,tj;
  REP(i,h)REP(j,w)if(a[i][j]=='S'){
    si=i;
    sj=j;
    a[i][j]='o';
  }else if(a[i][j]=='T'){
    ti=i;
    tj=j;
    a[i][j]='o';
  }
  if(si==ti || sj==tj){
    puts("-1");
    return 0;
  }
  // construct graph
  #define ID(i,j,x) ((100*(i)+j)*2+x)
  REP(i,h)REP(j,w){
    fl[ID(i,j,0)][ID(i,j,1)] = 1;
    REP(k,w)if(j!=k){
      if(a[i][k]=='o'){
        fl[ID(i,j,1)][ID(i,k,0)] = 1252;
      }
    }
    REP(k,h)if(i!=k){
      if(a[k][j]=='o'){
        fl[ID(i,j,1)][ID(k,j,0)] = 1252;
      }
    }
  }
  int sid = ID(si,sj,1);
  int tid = ID(ti,tj,0);
  int ans = 0;
  while(true){
    vi path = bfspath(sid,tid);
    if(path.size()==0)break;
    REP(i,path.size()-1){
      int x = path[i];
      int y = path[i+1];
      fl[x][y]--;
      fl[y][x]++;
    }
    ans++;
  }
  printf("%d\n",ans);
  return 0;
}


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

using namespace std;
#define ll long long
#define sz(x) (ll)(x.size())
#define f first
#define se second
const ll N1 = 123456, N2 = 123;
ll dp[N1][N2];
ll w[N2],v[N2];
ll get_ans(ll W, ll n){
    if(W == 0 || n == 0){
        return 0;
    }
    if(dp[W][n] != -1){
        return dp[W][n];
    }
    if(W < w[n - 1]){
        dp[W][n] = dp[W][n - 1] = get_ans(W, n - 1);
    }else{
        dp[W][n - 1] = get_ans(W, n - 1);
        dp[W - w[n - 1]][n - 1] = get_ans(W - w[n - 1],n - 1);
        dp[W][n] =  max(dp[W][n - 1],dp[W - w[n - 1]][n - 1] + v[n - 1]);
    }
    return dp[W][n];
}
int main() {
    ios::sync_with_stdio(0);
    for(ll i = 0;i < N1; i++){
        for(ll j = 0; j < N2; j++){
            dp[i][j] = -1;
        }
    }
    ll n, W;
    cin >> n >> W;
    for(ll i = 0;i < n;i++){
        cin >> w[i] >> v[i];
    }
    cout << get_ans(W, n) << "\n";
}

Measured memory_bytes: 118912
#include <bits/stdc++.h>
 
using namespace std;
 
long long n, a[10001], b[10001], A[10001][1001], fix[1000001];
long long usj;
long long p = 1000000007;
 
long long go (long long a, long long b){
	if (b == 0){
		return 1;
	}
	if (b == 1){
		return a;
	}
	else {
		if (b%2 == 0){
		    long long u = go(a, b/2);
		
			return (u*u)%p;
		}
		else
			return (go(a, b-1)*a)%p;
	}
}
 
int main () {
	usj = 1;
	cin >> n;
	for (int i=1; i<=n; i++){
		cin >> a[i];
		b[i] = a[i];
		for (int j=2; j<=1000; j++){
			while (a[i]%j==0){
				a[i]=a[i]/j;
				A[i][j]++;
			}
		}
	}
	
	for (int i=1; i<=1001; i++){
		long long x = 0;
		long long k = 0;
		for (int j=1; j<=n; j++){
			x = max (x, A[j][i]);
			k = i;
		}
		
		k = go(k,x);
		usj*=k;
		usj=usj%p;
	}
	for (int i=1; i<=n; i++){
		if (fix[a[i]] == 0){
			fix[a[i]] = 1;
			usj*=a[i];
			usj=usj%p;
		}
	}
	
	long long  sum = 0;
	for (int i=1; i<=n; i++){
		b[i] = go(b[i], p-2);
		sum += b[i];
		sum = sum%p;
	}
	sum = (usj*sum)%p;
	cout << sum;
}

Measured memory_bytes: 82816
#include<iostream>

using namespace std;

int main(void) {

	long long N, ans = 1,a;

	cin >> N;

	for (int i = 1; i <= N; i++) {

		ans = ans*i;
		ans= ans % (1000000000 + 7);

	}

	a = ans % (1000000000 + 7);

	cout << a << endl;

}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue>
#define LL long long
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
//#define int LL
using namespace std;
const int N   = 3e5+233;
//const int mod = ;
const int INF =numeric_limits<int >::max();
#define For(n) for (int i=1;i<=n;++i)
#define rep(i,n) for (int i=1;i<=n;++i)
#define repp(i,x,y) for (int i=x;i<=y;++i)
void read(int &x)
{
	x=0;
	char ch=getchar();
	int f=1;
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}

void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
int n,a[N],b[N],c[N],d[N];
signed main()
{
	read(n);
	rep(i,n)  read(a[i]),++c[a[i]];
	rep(i,n) read(b[i]),++d[b[i]];
	reverse(b+1,b+1+n);
	rep(i,n ) if (c[i]+d[i]>n) 
	{
		printf("No");
		return 0;
	}
	int l=n,r=1;
	rep(i,n) if (a[i]==b[i])  l=min(l,i),r=max(r,i);
	int pos=l;
	for (int i=1;i<l&&pos<=r;++i) if (b[i]!=a[l]&&a[i]!=a[l]) swap(b[i],b[pos]),++pos;
	for (int i=r+1;i<=n&&pos<=r;++i) if (b[i]!=a[l]&&a[i]!=a[l]) swap(b[i],b[pos]),++pos;
	if (pos<r) {
		printf("No");
		return 0;
	}
	printf("Yes\n");
	rep(i,n) printf("%d ",b[i]);
	return 0;
}


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

using namespace std;
#define MOD 1000000007
#define pi 3.1415926535897932384626433832795028841971693993751058209749445923078164062
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define popb pop_back()
#define popf pop_front()
#define ff first
#define ss second
#define vl vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vll vector< pair<ll,ll> >
#define vii vector< pair<int,int> >
#define viii vector< tuple <int,int,int> >
#define vlll vector< tuple <ll,ll,ll> >
#define vvl vector<vector<ll>>
#define vv vector<vector<int>>
#define all(v) v.begin(),v.end()
#define sqrt sqrtl
#define cbrt cbrtl
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mapcl map<char,ll>
#define mapci map<char,int>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define seti set<int>
ifstream fin("input.txt");
ofstream fout("output.txt");

int gcd(int a,int b){while (a&&b)a>b?a%=b:b%=a;return a+b;}
ll pows(int a , int b){ll res=1;for(int i=0; i<b; ++i){res*=a;}return res;}
ll logx(ll base, ll num){int cnt=0;while(num!=1){num/=base; ++cnt;}return cnt;}

vi vis(100001,0);
vi adj[100001];

int main()
{	
    std::ios::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);
    ll n;
    cin>>n;
    vi m,h;
    for(int i=0; i<n+1; ++i)
    {
    	int x;
    	cin>>x;
    	m.pb(x);
    }
    for(int i=0; i<n; ++i)
    {
    	int x;
    	cin>>x;
    	h.pb(x);
    }
    ll sum =0;
    ll cur=0;
    for(int i=0; i<n; ++i)
    {
    	cur=min(h[i],m[i]);
    	sum+=cur;
    	if(h[i]>m[i])
    	{
    		h[i]-=m[i];
    		m[i]=0;
    		
    	}
    	else
    	{
    		m[i]-=h[i];
    		h[i]=0;
    	}
    	cur=min(h[i],m[i+1]);
    	sum+=cur;
    	if(h[i]>m[i+1])
    	{
    		h[i]-=m[i+1];
    		m[i+1]=0;
    		
    	}
    	else
    	{
    		m[i+1]-=h[i];
    		h[i]=0;
    		
    	}
    	cur=0;
    }
    cout<<sum<<"\n";
}

Measured memory_bytes: 4216
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

typedef long long ll ;
typedef double db;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forab(a,b)       for(int i=a;i<=b;i++)
//#define gcd(a, b)     __gcd(a, b)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)     cout<<"Case "<<z<<": "<<x<<"\n"
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

int main()
{
	int n,k,i,d,x;
	cin>>n>>k;
	vector<int>v(n+1,0);
	while(k--){
		cin>>d;
		while(d--){
			cin>>x;
			v[x]++;
			}
		}
	int c=0;
	for(i=1 ; i<=n ; i++){
		if(v[i]==0) c++;
		}
	cout<<c<<nw;
	return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>

int GCD(int m,int n);


int main(void){
	
	int a,b,gcd,lcm;
	/*printf("Insert two numbers\n");*/	
	
	while(scanf("%d %d",&a,&b)!=EOF)
	{
	
	
	gcd=GCD(a,b);
	lcm=gcd*(a/gcd)*(b/gcd);
	
	
	
	/*printf("GCD and LCM are:\n");*/
	printf("%d %d\n",gcd,lcm);
	

}
	return 0;
} 




int GCD(int m,int n){

	int remain=0;

	while(n!=0)
	{		remain=m%n;
			m=n;
			n=remain;
	}


	return m;
}




Measured memory_bytes: 2028
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
#define setzero(x) memset(x,0,sizeof(x))
  
using namespace std;
 
const int inf = 2e9+500;
const int N = 1e3+10;
const int bits = 20;
const ld pi = 3.14159265358979323846;
const ll mod = 1e9+7;
const ll p = 29;


int main(){

    FASTIO;
    PRECISION; 
    
    ll n,k;
    cin>>n>>k;
    ll ans = 0;
    for(ll i=k;i<=n+1;i++){
        ll smallest_number = i*(i-1)/2;
        ll largest_number = n*(n+1)/2 - (n-i)*(n-i+1)/2;

        // cout<<k<<" "<<smallest_number<<" "<<largest_number<<"\n";

        ans+=(largest_number-smallest_number+1)%mod;
        ans%=mod; 
    }
    cout<<ans<<"\n";
    

}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using ll = long long;
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)	return a;
	return gcd(b, a % b);
}
int main()
{
	int k;
	cin >> k;
	ll ans = 0;
	int ab;
	for (int a = 1; a <= k; ++a) {
		for (int b = 1; b <= k; ++b) {
			for (int c = 1; c <= k; ++c) {
				ab = gcd(a, b);
				ans += gcd(ab, c);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3176
#include <stdio.h>
#include <string.h>

#define MIN(A,B) (A)<(B)?(A):(B)
#define MAX(A,B) (A)>(B)?(A):(B)

#define N 5

int main(){
  int n, a, b, c=0, i;
  char S[N], T[N];
  scanf("%d %d", &a, &b);
  c=(b-1)/(a-1);
  if ((b-1)%(a-1)) c++;
  printf("%d\n", c);
  return 0;
}


Measured memory_bytes: 128
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]

N,M = I()
u = UnionFind(N)
for i in range(M):
    a,b = I()
    u.unite(a-1,b-1)
ans = 0
for i in range(N):
    ans = max(ans,u.count(i))
print(ans)

Measured memory_bytes: 82868
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scan() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	n := scan()
	min := scan()

	var r int
	max := math.MinInt64
	for i := 0; i < n-1; i++ {
		r = scan()
		max = int(math.Max(float64(max), float64(r-min)))
		min = int(math.Min(float64(min), float64(r)))
	}
	fmt.Println(max)
}


Measured memory_bytes: 4100
import java.util.Scanner;

public class Main{
  public static void main(String[]args){
    
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int l=sc.nextInt();
    
    int lwBound=2*n;
    int upBound=4*n;
    
    if(l>=lwBound && l<=upBound) {
    	if(l%2==0 ) {
    		System.out.println("Yes");
    	}
    	else
    		System.out.println("No");
    	
    }
    else
    	System.out.println("No");
    
  }
}


Measured memory_bytes: 27084
#include <iostream>
#include <locale>

using namespace std;

int main()
{
    int n, k;
    cin >> n;
    cin >> k;
    char str[51];
    scanf("%s", str);
    str[k-1] = tolower(str[k-1], locale::classic());
    cout << str << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;
int N,K;
long long v[200001],sum=0;
int main()
{
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        cin>>v[i];
    }
    sort (v+1,v+N+1);
    for(int i=0;i<=N-K;i++){
        sum=sum+v[i];
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 1792
n = int(input())
if n == 1:
    print(0)
    exit()
F = {}
tmp = n
i = 2
while i**2 <= tmp:
    cnt = 0
    while tmp % i == 0:
        cnt += 1
        tmp //= i
    if cnt > 0:
        F[i] = cnt
    i += 1
if tmp != 1 or F == {}:
    F[tmp] = 1
ans = 0
for p in F:
    a = 1
    while F[p] >= a:
        F[p] -= a
        ans += 1
        a += 1
print(ans)

Measured memory_bytes: 9212
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define Maxn 100010
#define INF 10010
inline int read()
{
    char c=getchar();re ll f=1,s=0;
    while(!isdigit(c)){if(c=='-')f=-1,c=getchar();}
    while(isdigit(c)){s=s*10+c-48;c=getchar();}
    return f*s;
}
map<int,int> m;
int n,x,s;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
    	cin>>x;
    	if(m[x]) s++;
    	else m[x]++; 
    }
    if(s&1) s++;
    cout<<n-s<<endl;
    return 0;
}     

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

public class Node
{
    public int nno { get; set; }
    public List<int> child { get; set; }
}

public class TimeStump
{
    public int ts { get; set; }
}

public class hello
{
    public static void Main()
    {
        var nodes = new List<Node>();
        var n = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n; i++)
        {
            string[] s = Console.ReadLine().Trim().Split(' ');
            var u = int.Parse(s[0]);
            var k = int.Parse(s[1]);
            var a = new Node { child = new List<int>(), nno = u };
            for (int j = 0; j < k; j++) a.child.Add(int.Parse(s[j + 2]));
            nodes.Add(a);
        }
        var ts = new TimeStump { ts = 1 };
        var df0 = new int[n + 1];
        var df1 = new int[n + 1];
        var sno = 1;
        while (true)
        {
            VisitNode(nodes, df0, df1, sno, ts);
            df1[sno] = ts.ts; ts.ts++;
            var t3 = GetNum(df0);
            if (t3 == 0) break;
            else sno = t3;
        }
        DispAns(df0, df1);
    }
    public static void DispAns(int[] df0, int[] df1)
    {
        for (int i = 1; i < df0.Length; i++)
            Console.WriteLine("{0} {1} {2}", i, df0[i], df1[i]);
    }
    public static void VisitNode(List<Node> node, int[] df0, int[] df1, int n, TimeStump ts)
    {
        var r = node[n - 1];
        df0[n] = ts.ts; ts.ts++;
        if (r.child.Count() == 0) return;
        foreach (var x in r.child)
        {
            if (df0[x] == 0)
            {
                VisitNode(node, df0, df1, x, ts);
                { df1[x] = ts.ts; ts.ts++; }
            }
        }
    }
    public static int GetNum(int[] df0)
    {
        for (int i = 1; i < df0.Length; i++)
            if (df0[i] == 0) return i;
        return 0;
    }
}

Measured memory_bytes: 9572
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

const int max_n = 10005;
int par[max_n];
int rank[max_n];

// n 要素で初期化
void init_union_find (int n )
{
	rep (i, n )
		par[i] = i, rank[i] = 0; 
}	

// 木の根を求める
int find (int x )
{
	if (par[x] == x ) return x;
	
	// 親を遡る
	return par[x] = find (par[x] );
}

// x と y の属する集合をマージ
void unite (int x, int y )
{
	x = find (x );
	y = find (y );

	// 親が一緒なら何もしない
	if (x == y ) return;

	//  ランクが小さい方の木をぶら下げる
	if (rank[x] < rank[y] ){
		// x を y にぶら下げる
		par[x] = y;
	}else{
		// ランクが同じか rank[x] > rank[y];
		par[y] = x;
		if (rank[x] == rank[y] ) rank[x]++;
	} // end if
}

// x と y が同じ集合に属するか
bool same (int x, int y )
{
	return (find (x ) == find (y ) );
}

int main()
{
	ios_base::sync_with_stdio(0);
	int n, q; cin >> n >> q;
	init_union_find (n );
	rep (i, q ){
		int com, x, y; cin >> com >> x >> y;
		if (com == 0 ){	// case 'unite'
			unite (x, y );
		}else{			// case 'same'
			cout << same(x, y ) << endl;
		} // end if
	} // end rep

	return 0;
}

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


int main(){
    ll N,A,B,C,D,E;
    cin >> N >> A >> B >> C >> D >> E;
    ll min_dist;
    min_dist = min(A,min(B,min(C,min(D,E))));
    //cout << min_dist << endl;
    
    cout << 5 + (N-1)/min_dist << endl;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1e9+7) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

// ------------------------------------------------------------------------------------------

const int INF = 1e18;

// idx, (未処理, 偶数左, 奇数, 偶数右)
const int VARI = 5;
int dp[200010][VARI];

signed main() {
  int N;
  cin >> N;
  vec<int> v(N);
  rep (i, N) {
    cin >> v[i];
  }

  const int one = 0; // 左のゼロ区間
  const int two = 1; // 右のゼロ区間
  const int three = 2; // 左の偶数区間
  const int four = 3; // 右の偶数区間
  const int five = 4; // 奇数区間

  // 初期化
  fill(dp[0], dp[N+1], INF);
  dp[0][one] = 0;

  // DP
  rep (i, N) {
    // 左のゼロ区間
    chmin(dp[i+1][one], dp[i][one] + v[i]);

    // 左の偶数区間
    int cost1 = (v[i] == 0 ? 2 : (v[i] % 2));
    chmin(dp[i+1][two], min(dp[i][two], dp[i][one]) + cost1);

    // 奇数
    int cost3 = 1 - (v[i] % 2);
    int mi = min({dp[i][two], dp[i][three], dp[i][one]});
    chmin(dp[i+1][three], mi + cost3);

    // 右の偶数区間
    int cost2 = (v[i] == 0 ? 2 : (v[i] % 2));
    chmin(dp[i+1][four], min(dp[i][three], dp[i][four]) + cost2);


    // 未処理右
    int mi2 = min({dp[i][two], dp[i][four], dp[i][three], dp[i][five]});
    chmin(dp[i+1][five], mi2 + v[i]);
  }

  int ans = INF;
  rep (i, VARI) {
    chmin(ans, dp[N][i]);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 9600
import java.util.Scanner;

public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][] cost = new int [n][3];
        int[][] plans=new int[n][3];
        for(int i=0;i<n;i++){
            plans[i][0]=sc.nextInt();
            plans[i][1]=sc.nextInt();
            plans[i][2]=sc.nextInt();
        }
        
        for (int i=0;i<3;i++)
            cost[0][i]=plans[0][i];
        for (int i=1;i<n;i++)
            for (int j=0;j<3;j++){
                cost[i][j]=plans[i][j]+Math.max(cost[i-1][(j+1)%3],cost[i-1][(j+2)%3]);
            }
        System.out.println(Math.max(cost[n-1][0],Math.max(cost[n-1][1],cost[n-1][2])));
    }
}


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

int main(){
  int n;
  cin >> n;
  int ans=0;
  int a;
  for(int i=1;i<n+1;i++){
    cin >> a;
    if(i%2==1){
      if(a%2==1){
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
 
if a < b:
    if v <= w:
        print('NO')
    else:
        if b - a <= t * (v - w):
            print('YES')
        else:
            print('NO')
elif a > b:
    if v <= w:
        print('NO')
    else:
        if a - b <= t * (v - w):
            print('YES')
        else:
            print('NO')

Measured memory_bytes: 61864
#include<bits/stdc++.h>
using namespace std;
int main(){

    long long n;
    cin>>n;
    string s="";
    while(n){
        n-=1;
        s+=char(('a')+(n%26));
        n/=26;
    }
    reverse(s.begin(),s.end());
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 3540
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long int
#define pb push_back

using namespace std;

const int mx = 1e6+5;

bool sieve[mx];
vector<int> p;

void fastp(){
	memset(sieve, true, sizeof(sieve));
	sieve[1] = false;
	for(int j = 2*2; j < mx; j += 2) sieve[j] = false;
	p.pb(2);
	for(int i = 3; i < mx; i += 2){
		if(sieve[i]){
			p.pb(i);
			if(i > mx/i) continue;
			for(int j = i*i; j < mx; j+=i+i) sieve[j] = false;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	fastp();
	int n;
	scanf("%d", &n);
	for(int i = 0; i < p.size(); ++i){
		if(p[i] >= n) {
			printf("%d\n", p[i]);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1916
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)




int main() {
	int N, K;
	cin >> N >> K;
	int ans = 0;
	rep(i, N) {
		int h;
		cin >> h;
		if (K <= h) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

template<int m>
class Prime{
  std::vector<bool> p;
public:
  std::vector<int> ps;
  Prime(){
    p = std::vector<bool>(m,true);
    assert(m>1);
    p[0]=p[1]=false;
    for(int i=4;i<m;i+=2)
      p[i]=false;
    ps.push_back(2);
    for(int i=3;i<m;i+=2){
      if(p[i]){
        ps.push_back(i);
        for(int j=i+i;j<m;j+=i)
          p[j]=false;
      }
    }
  }

  bool isPrime(int n){
    assert(m>n);
    return p[n];
  }

  int operator [] (int n){
    if(n<ps.size()) return ps[n];
    else return 0;
  }

  int size(){
    return ps.size();
  }
};

int main(){
  Prime<100000+10000> p;
  int n,m;
  while(scanf("%d%d",&n,&m), n + m != -2){
    vector<int> v((m+1)*m/2);
    int base = lower_bound(ALL(p.ps), n) - p.ps.begin();
    vector<int>::iterator it = v.begin();
    if(p.ps[base] == n) base++;

    for(int i=0; i<m; i++)
      for(int j=i; j<m; j++)
        *it++ = p.ps[base + i] + p.ps[base + j];

    sort(v.begin(), v.end());
    printf("%d\n",v[m-1]);
  }
  return 0;
}

Measured memory_bytes: 1048
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int par[100001];
int ran[100001];

void init(int n){
	for (int i = 1; i <= n; i++){
		par[i] = i;
		ran[i] = 0;
	}
}

int find(int x){
	if (par[x] == x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (ran[x] < ran[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if (ran[x] == ran[y]) ran[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}


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

	init(n);

	for (int i = 0; i < m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		unite(x, y);
	}

	vector<int> vec;
	for (int i = 1; i <= n; i++){
		vec.push_back(find(i));
	}

	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	cout << vec.size() << endl;
	return 0;
}

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

int main()
{
  string str ;
  cin >> str ;
  int cnt = 0 ;
  for(int i = 0 ; i < str.size() ; i++)
  {
   if(str[i] == '1')
   cnt++ ;
  }
 cout << cnt << endl;
  return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n);
    vector<int>sum(n+1);
    for(int i=0; i<n; i++){
        cin>>a.at(i);
    }
    for(int i=0; i<n; i++){
        sum.at(i+1)+=sum.at(i)+a.at(i);
    }
    sort(a.begin(),a.end(),greater<int>());
    if(a.at(m-1)*4*m>=sum.at(n)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = b - 1; i >= a; i--)
#define ALL(a) a.begin(), a.end()
#define pii pair<int,int>
#pragma GCC optimize("Ofast")
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.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(a>b){a = b; return 1;} return 0; };
inline void IN(void){return;}
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
inline void OUT(void){cout << "\n";return;}
template <typename First, typename... Rest> void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}
const double EPS = 1e-9;
const int mod = 1e9 + 7;
const int INF = 1e9;
const long long LLINF = 1e18;
long long lcm(ll a, ll b){return a * b / __gcd(a,b);}
struct IoSetup { IoSetup() {
    cin.tie(nullptr);ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
} } iosetup;
template< int mod > struct ModInt {
    int x; ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}
    ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}
    ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}
    ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }return ModInt(u);}
    ModInt pow(int64_t n) const {ModInt ret(1), mul(x); while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x;}
    friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); }
    static int get_mod() { return mod; }
}; using modint = ModInt< mod >;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    iosetup;
    ll a, b; cin >> a >> b;
    ll n = b - a;
    cout << n * (n - 1) / 2 - a << endl;

    return 0;
}

Measured memory_bytes: 256
// Author : Chi
// created : Sunday 2020-05-31
// Sawal : https://www.codechef.com/LTIME84B/problems/TREDIFF

//header files
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//namespaces
using    namespace __gnu_pbds;
using    namespace std;
typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

//macros
#define ll 		    long long
#define ss          second
#define ff          first
#define vi          vector<int>
#define vll         vector<long long>
#define pb(x)       push_back(x)
#define TEST  	    int TesT;cin>>TesT;while(TesT--)solve();
#define TEST1       solve();
#define mod         998244353
#define r0n(i,n)    for(ll i = 0; i < n; ++i)
#define r1n(i,n)    for(ll i = 1; i <= n; ++i)
#define pdp(d,i)    fixed<<setprecision(i)<<d
#define CHI         ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define db(...)     __f(#__VA_ARGS__, __VA_ARGS__)                      //for debugging
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#define dig(n) floor(log10(n) + 1)
//LOVE ALGO
void solve(){
    long long a;
    cin>>a;
    ll b;
    char c;
    ll d;
    cin>>b>>c>>d;
    cout<<(a*(b*100+d))/100;

}

// Driver Code
int main(){
    CHI
    TEST1
    return 0;
}



Measured memory_bytes: 3660
#include<stdio.h>

void quick(int *,int,int);

int main()
{
  int N,M,X,Y;
  scanf("%d%d%d%d\n", &N,&M,&X,&Y);
  int A[N+1],B[M+1],cnt = 0;
  int i;
  for(i=0;i<N;++i)
    scanf("%d", &A[i]);
  A[N] = X;
  
  for(i=0;i<M;++i)
    scanf("%d", &B[i]);
  B[M] = Y;

  quick(A,0,N);
  quick(B,0,M);
  
  if(X < Y)
    ++cnt;
  if(A[N] < B[0])
    ++cnt;

  if(cnt == 2)
    printf("No War\n");
  else
    printf("War\n");
  
  return 0;
}

void quick(int *a,int left,int right)
{
  int s,t,i,j;
  
  if(left < right){
    s = a[left];
    i = left; j = right+1;
    while(1){
      while(a[++i] < s);
      while(a[--j] > s);
      if(i >= j) break;
      t = a[i]; a[i] = a[j]; a[j] = t;
    }
    a[left] = a[j]; a[j] = s;
      quick(a,left,j-1);
      quick(a,j+1,right);
  }
}

Measured memory_bytes: 128
#include "bits/stdc++.h"

struct RangeMinimumQuery {
    using type = int;
    static type id() { return INT_MAX; }
    static type op(const type &l, const type &r) { return std::min(l, r); }
};

struct RangeMaximumQuery {
    using type = int;
    static type id() { return -INT_MAX; }
    static type op(const type &l, const type &r) { return std::max(l, r); }
};

struct RangeSumQuery {
    using type = int;
    static type id() { return 0; }
    static type op(const type &l, const type &r) { return l + r; }
};

template <typename M>
class SegmentTree
{
    using T = typename M::type;
    int n;
    std::vector<T> node;

public:
    // v を基に初期化
    SegmentTree(const std::vector<T> &v)
    {
        // n は v.size() 以上の最小の2冪
        n = 1;
        while (n < int(v.size()))
            n *= 2;
        node.resize(2 * n, M::id());

        // i の子 -> 2*i+1, 2*i+2 , 親 -> (i-1)/2
        for (int i = 0; i < int(v.size()); i++)
            node[i + n] = v[i];
        for (int i = n - 1; i >= 0; i--)
            node[i] = M::op(node[2 * i], node[2 * i + 1]);
    }
    // Monoid::id 初期化
    SegmentTree(int _n)
    {
        n = 1;
        while (n < _n)
            n *= 2;
        node.resize(2 * n, M::id());
    }
    // x 番目を val に更新
    void update(int x, T val)
    {
        x += n;
        node[x] = val;
        while (x >>= 1)
        {
            node[x] = M::op(node[2 * x], node[2 * x + 1]);
        }
    }
    // v[x] を M::op(v[x], val) に更新
    void operation(int x, T val)
    {
        x += n;
        node[x] = M::op(node[x], val);
        while (x >>= 1)
        {
            node[x] = M::op(node[2 * x], node[2 * x + 1]);
        }
    }
    // [a, b) の op
    T query(int l, int r)
    {
        l += n;
        r += n;
        T retl = M::id(), retr = M::id();
        while (l < r)
        {
            if (l & 1)
                retl = M::op(retl, node[l++]);
            if (r & 1)
                retr = M::op(node[--r], retr);
            l >>= 1;
            r >>= 1;
        }
        return M::op(retl, retr);
    }
};

using namespace std;

void solve_dsl_2_a()
{ // range min
    int n, q;
    cin >> n >> q;
    SegmentTree<RangeMinimumQuery> st(n);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 0)
        {
            int index, x;
            cin >> index >> x;
            st.update(index, x);
        }
        else
        {
            int s, t;
            cin >> s >> t;
            t++;
            cout << st.query(s, t) << endl;
            ;
        }
    }
}

void solve_dsl_2_b()
{ // range sum
    int n, q;
    cin >> n >> q;
    SegmentTree<RangeSumQuery> st(n);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 0)
        {
            int index, x;
            cin >> index >> x;
            index--;
            st.operation(index, x);
        }
        else
        {
            int s, t;
            cin >> s >> t;
            s--;
            cout << st.query(s, t) << endl;
            ;
        }
    }
}

int main()
{
    solve_dsl_2_b();
}



Measured memory_bytes: 3848
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

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

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.push_back(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
int main(){
  ll i,j,N,M,a,b,ans=0;
  cin>>N>>M;
  vec v(N);
  rep(i,N){
    cin>>v[i];
    v[i]-=M;
  }
  map<datas,ll> mp;
  set<ll> se;
  queue<ll> que;
  se.insert(0);
  mp[datas(-1,0)]=1;
  rep(j,N){
    for(auto i:se){
      if(!mp[datas(j-1,i+v[j])])que.push(i+v[j]);
      mp[datas(j,i+v[j])]=mp[datas(j-1,i+v[j])]+mp[datas(j-1,i)];
      mp[datas(j,i)]=max(mp[datas(j-1,i)],mp[datas(j,i)]);
    }
    while(!que.empty()){
      se.insert(que.front());que.pop();
    }
  }
  cout<<mp[datas(N-1,0)]-1<<endl;
  return 0;
}


Measured memory_bytes: 1664
loop do
  n, x = gets.chomp.split.map(&:to_i)
  break if n.zero? && x.zero?

  cnt = 0
  (1..(n-2)).each do |a|
    ((a+1)..(n-1)).each do |b|
      c = x - a - b
      if c <= n && c > b && a != b
        cnt += 1
      end
    end
  end
  puts cnt
end

Measured memory_bytes: 8712
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int dp[100010], nxt[100010];

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

    int n, x;
    cin >> n >> x;
    vector<int> s(n);
    rep(i, n) cin >> s[i];
    sort(all(s));
    reverse(all(s));
    dp[x] = 1;
    rep(i, n)
    {
        rep(j, 100010) nxt[j] = 0;
        rep(j, 100010)
        {
            (nxt[j % s[i]] += dp[j]) %= mod;
            nxt[j] += dp[j] * (n - i - 1) % mod;
            nxt[j] %= mod;
        }
        rep(j, 100010) dp[j] = nxt[j];
    }
    int ans = 0;
    rep(i, 100010)(ans += i * dp[i]) %= mod;
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(void){
    string str;
    int nums[26] = {};
    while(getline(cin,str)){
        for(int i = 0;i < str.length();++i){
            char c = str.at(i);
            if(islower(c)){
                int a = c - 97;
                nums[a]++;
            }
            else if(isupper(c)){
                int a = c + 32 - 97;
                nums[a]++;
            }
        }
    }

    for(int i = 0;i < 26;++i){
        cout << char('a' + i) << " : " << nums[i] << endl;
    }
}


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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> bool chmax(T& a,const T& b){return a < b ? (a = b,true) : false;}
template<typename T> bool chmin(T& a,const T& b){return b < a ? (a = b,true) : false;}
typedef long long ll;

string S;

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

	cin >> S;
	int N = S.size();

	bool flag = false;
	FOR(i,0,N){
		if(S [i] == 'C'){
			flag = true;
		}
		if(S [i] == 'F' && flag){
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}


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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

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

const int N = (int)1e5 + 123, mod = (int)1e9 + 7;
const ll inf = 1e18;

ll n, a[N], ans, dp[N][2];
int main(){    
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	dp[0][0] = 0;   
	dp[0][1] = -inf;
	
	for(int i = 1; i <= n; i++){
		dp[i][0] = dp[i][1] = -inf;
		if(a[i]&1){                               
			dp[i][0] = dp[i - 1][1] + a[i]/2 + 1;
			dp[i][1] = dp[i - 1][0] + a[i]/2;
		}else{
			dp[i][0] = dp[i - 1][0] + a[i]/2;
			if(a[i] > 0)
            	dp[i][1] = dp[i - 1][1] + a[i]/2;
		}
		dp[i][0] = max(dp[i][0], dp[i][1]);
		//cerr << i << " " << dp[i][0] << " " << dp[i][1] << endl;
	}
	cout << max(dp[n][0], dp[n][1]);
	return 0;
}


Measured memory_bytes: 2560
#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;
    cin >> n;
    vector<int> p(n), q(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];
    vector<int> r(n);
    rep(i, n) r[i] = i + 1;
    int cntP = 0, cntQ = 0, cnt = 0;
    do
    {
        cnt++;
        if (p == r)
            cntP = cnt;
        if (q == r)
            cntQ = cnt;
    } while (next_permutation(r.begin(), r.end()));
    cout << abs(cntP - cntQ) << endl;
    return 0;
}

Measured memory_bytes: 3604