akhauriyash/Code-Regression huggingface dataset:
class LazySegmentTreeBase
  def initialize(arr, l = 0, r = arr.size - 1)
    @l, @r = l, r
    @lazy = nil
    if l == r
      @agg = arr[l]
    else
      c = (l + r) / 2
      @left_child = self.class.new(arr, l, c)
      @right_child = self.class.new(arr, c + 1, r)
      @agg = aggregation_of(@left_child.agg, @right_child.agg)
    end
  end

  attr_reader :agg, :l, :r

  def update(l, r, x)
    if l == @l && r == @r
      defer(x)
    else
      force
      if r <= @left_child.r
        @left_child.update(l, r, x)
      elsif @right_child.l <= l
        @right_child.update(l, r, x)
      else
        @left_child.update(l, @left_child.r, x)
        @right_child.update(@right_child.l, r, x)
      end
      @left_child.force
      @right_child.force
      @agg = aggregation_of(@left_child.agg, @right_child.agg)
    end
  end

  def force
    return if !@lazy
    x = @lazy
    @lazy = nil
    whole_update(x)
    @left_child.update(@left_child.l, @left_child.r, x) if @left_child
    @right_child.update(@right_child.l, @right_child.r, x) if @right_child
  end

  def query(l, r)
    force
    return @agg if l == @l && r == @r
    if r <= @left_child.r
      return @left_child.query(l, r)
    elsif @right_child.l <= l
      return @right_child.query(l, r)
    else
      agg_left = @left_child.query(l, @left_child.r)
      agg_right = @right_child.query(@right_child.l, r)
      return aggregation_of(agg_left, agg_right)
    end
  end
end

class LazySegmentTree < LazySegmentTreeBase
  def initialize(arr, l = 0, r = arr.size - 1)
    @n = r - l + 1
    super(arr, l, r)
  end

  def defer(x)
    if @lazy
      @lazy += x
    else
      @lazy = x
    end
  end

  def whole_update(x)
    @agg += x * @n
  end

  def aggregation_of(x, y)
    x + y
  end
end

n, q = gets.split.map(&:to_i)
seg = LazySegmentTree.new(Array.new(n, 0))
q.times do
  c, x, y, z = gets.split.map(&:to_i)
  if c == 0
    seg.update(x-1, y-1, z)
  else
    puts seg.query(x-1, y-1)
  end
end


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

bool isLeap(int y){
  return y % 4 == 0 && (y % 400 == 0 || y % 100 != 0);
}

int main(){
  int a, b;

  for(int SET = 1; cin >> a >> b, a || b; SET++){
    if(SET != 1){
      cout << endl;
    }

    bool ansFlg = false;

    for(int i = a; i <= b; i++){
      if(isLeap(i)){
        ansFlg = true;
        cout << i << endl;
      }
    }

    if(!ansFlg){
      cout << "NA" << endl;
    }
  }
}

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

int main(){
  int n;
  int y,m,d;

  cin >> n;
  while( n-- ){
    cin >> y >> m >> d;
    int ans = 0, len = (y%3!=0&&m%2==0)?19:20;

    while( d<=len ){
      ans++;
      d++;
    }

    m++;
    while( m<=10 ){
      if( y%3==0 )
	ans += 20;
      else{
	if( m%2==1 )
	  ans += 20;
	else
	  ans += 19;
      }
      m++;
    }

    y++;
    while( y<1000 ){
      if( y%3==0 )
	ans += 20 * 10;
      else 
	ans += 20 * 5 + 19 * 5;
      y++;
    }
    cout << ans << endl;
  }

  return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0;i < N; i++){
    cin >> A.at(i);
  }
  int Q;
  cin >> Q;
  vector<int> B(Q), C(Q);
  for(int i = 0; i < Q; i++){
    cin >> B.at(i) >> C.at(i);
  }
  int64_t a = 0;
  
  vector<int> m(100000);
  for(int i = 0; i < N; i++){
    m.at(A.at(i) - 1)++;
    a += (int64_t)A.at(i);
  }
  
  int64_t x;
  for(int i = 0; i < Q; i++){
    x = (int64_t)C.at(i) - (int64_t)B.at(i);
    a += (x * m.at(B.at(i) - 1));
    cout << a << endl;
    m.at(C.at(i) - 1) += m.at(B.at(i) - 1);
    m.at(B.at(i) - 1) = 0;
  }
  
}


Measured memory_bytes: 4820
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil

class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self,x,y):
        return self.root(x) == self.root(y)

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        s = set()
        for par in self.par:
            s.add(par)
        return s
n,m,k = map(int,input().split())
uf = unionfind(n)
fr = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.unite(a-1,b-1)
    fr[a-1]+=1
    fr[b-1]+=1
ans = [uf.get_size(i) -fr[i]-1 for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    if uf.same(c-1,d-1):
        ans[c-1] -=1
        ans[d-1] -=1
print(*ans)


Measured memory_bytes: 90608
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;



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

    int n,m;
    cin>>n>>m;
    priority_queue<double> q;
    ld a;
    rep(i,n){
        cin>>a;
        q.push(a);
    }
    rep(i,m){
        a=q.top();
        q.pop();
        q.push(a/2);
    }
    ll ans=0;
    while(!q.empty()){
        a=q.top();
        q.pop();
        ans+=floor(a);
    }
    fin(ans);
    

//////////////////////////////////////////////////////
return 0;}



Measured memory_bytes: 1400
#include<iostream>
using namespace std;
bool isP[2000001];
int sumP[2000001];
int N=2000000;

void make_table();

int n,p,m,sum,X;
int main(){
  make_table();
  while(cin>>n&&n){
    sum=0;
    for(int i=0;i<n;i++){
      cin>>p>>m;
      X=sumP[p+m];
      if(p-m-1>=0)X-=sumP[p-m-1];
      if(X>0)sum+=(X-1);
      else sum--;
    }
    cout<<sum<<endl;
  }
  return 0;
}
void make_table(){
  for(int i=0;i<=N;i++){isP[i]=true;sumP[i]=0;}
  isP[0]=isP[1]=false;
  for(int i=2;i*i<=N;i++){
    if(isP[i]==false)continue;
    for(int j=i*i;j<=N;j+=i)isP[j]=false;
  }

  for(int i=1000003;i<=N;i++)isP[i]=false;

  for(int i=1;i<=N;i++){
    sumP[i]=sumP[i-1]+isP[i];
  }
}

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

struct Dice {
   int b,f,l,r,u,d;

   void RollN()
  {
    //  --y;
    int buff = d;
    d = f;
    f = u;
    u = b;
    b = buff;
  }

  void RollS()
  {
    // ++y;
    int buff = d;
    d = b;
    b = u;
    u = f;
    f = buff;
  }

  void RollL() // ----->
  {
    int buff = f;
    f = l;
    l = b;
    b = r;
    r = buff;
  }

  void RollR() // <------
  {
    int buff = f;
    f = r;
    r = b;
    b = l;
    l = buff;
  }

  void RollE() // .o -> o.
  {
    // --x;
    int buff = d;
    d = l;
    l = u;
    u = r;
    r = buff;
  }


  void RollW() // o. -> .o
  {
    //  ++x;
    int buff = d;
    d = r;
    r = u;
    u = l;
    l = buff;
  }

};

//頑張った
void dfs(int x, int y, int f[5][5], Dice &dice, char c, vector<vector<bool>> visited){
   if(x >= 5 || x < 0 || y >= 5 || y < 0 || visited[y][x]){
      return;
   }

   visited[y][x] = true;
   if(f[y][x] == 0){
      return;
   }

   if(c == 'r') dice.RollL();
   if(c == 'l') dice.RollR();
   if(c == 'u') dice.RollS();
   if(c == 'd') dice.RollN();

   dice.b = f[y][x];


   dfs(x+1, y, f, dice, 'r', visited);
   dfs(x-1, y, f, dice, 'l', visited);
   dfs(x, y+1, f, dice, 'd', visited);
   dfs(x, y-1, f, dice, 'u', visited);

   if(c == 'r') dice.RollR();
   if(c == 'l') dice.RollL();
   if(c == 'u') dice.RollN();
   if(c == 'd') dice.RollS();
}

int main(){
   int n; cin>>n;
   while(n--){
      int f[5][5];
      vector<int> nums(7, 0);
      int x, y;
      for(int i=0; i<5; i++){
         for(int j=0; j<5; j++){
            cin>>f[i][j];
            nums[f[i][j]]++;
            if(f[i][j] != 0) x=j,y=i;
         }
      }

      //1-6の出現回数が1ならok
      bool flag = false;
      for(int i=1; i<7; i++){
         if(nums[i] != 1) flag = true;
      }
      if(flag){
         cout << "false" << endl;
         continue;
      }

      Dice dice = {0, 0, 0, 0, 0, 0};
      vector<vector<bool>> visited(5, vector<bool>(5, false));
      dfs(x, y, f, dice, 'b', visited);

      cout << ((dice.b + dice.f == 7 && dice.l+dice.r == 7 && dice.u+dice.d == 7) ? "true" : "false") << endl;
   }
}


Measured memory_bytes: 3020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    string s;
    cin >>s;

    bool b = false;
    rep(i,3)if(s[i]==s[i+1]) b = true;

    cout << (b?"Bad":"Good") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>

using namespace std;

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

  vector<int> v;
  if (S[0] == '0') v.push_back(0);
  char ch = S[0];
  int cnt = 0;
  for (int i = 0; i < N; ++i) {
    if (S[i] != ch) {
      v.push_back(cnt);
      cnt = 1;
      ch = ch == '0' ? '1' : '0';
    }
    else {
      ++cnt;
    }
  }
  v.push_back(cnt);
  if (S[N - 1] == '0') v.push_back(0);

  int ans = 0;
  for (int L = 0; L < (int)v.size(); L += 2) {
    int R = min(L + 2 * K, (int)v.size() - 1);
    int sum = 0;
    for (int i = L; i <= R; ++i) {
      sum += v[i];
    }
    ans = max(ans, sum);
  }

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


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


#define ll          long long
#define uint        unsigned int 
#define ld          long double
#define SAM         ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define mod         1000000007
#define mxn         200005
#define pb          push_back
#define pii         pair<int,int>
#define f           first
#define s           second
#define sz(x)       (int)x.size()
#define all(x)      x.begin(),x.end()

using namespace std;


int main()
{
    SAM;
    int n,count=0;
    cin>>n;
    int arr[n];
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(i%2==1 && arr[i]%2==1)
            count++;
    }
    cout<<count;
    
    return 0;
}




Measured memory_bytes: 3640
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
int x,y;
int main(){
	cin>>x>>y;
	if(x==y)cout<<0;
	else if(x==-y)cout<<1;
	else if(x==0||y==0){
		int ans=y==0?x:y;
		ans=ans>=0?ans:-ans;
		if(x>0&&y==0)ans++;
		if(x==0&&y<0)ans++;
		cout<<abs(ans);
	}
	else if(x>=0&&y>=0){
		int ans=abs(y-x);
		if(y<x)ans+=2;
		cout<<ans;
	}
	else if(x<0&&y<0){
		if(x<y)cout<<y-x;
		else cout<<x-y+2;
	}
	else if(x<0&&y>=0){
		if(-x<y)cout<<y+x+1;
		else cout<<-x-y+1;
	}
	else if(x>=0&&y<0){
		if(x>-y)cout<<x+y+1;
		else cout<<-y-x+1;
	}
	return 0;
}

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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { 1,  0, -1,  0,  1, -1,  1, -1};
static const int dy[8] = { 0,  1,  0, -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;
const int mod = 1e9+7;

LL A,B,C,D;

int main()
{
    cin >> A >> B >> C >> D;
    LL tot = B - A + 1;
    LL dc = B/C - (A-1)/C;
    LL dd = B/D - (A-1)/D;
    LL gcd = __gcd(C,D);
    LL cd = C*D/gcd;
    LL k = B/cd - (A-1)/cd;

    cout << tot - dc - dd + k << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX_N 105
using namespace std;
int n,t[MAX_N],sum[MAX_N];
int main(){
	int i,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		sum[i]=x+sum[i-1];
	}
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		t[i]=max(t[i-1]+x,sum[i]+x);
	}
	printf("%d\n",t[n]);
	return 0;
}

Measured memory_bytes: 256
operation = {"North": (1, 5, 2, 3, 0, 4),
             "East": (3, 1, 0, 5, 4, 2),
             "West": (2, 1, 5, 0, 4, 3),
             "South": (4, 0, 2, 3, 5, 1),
             "Right": (0, 2, 4, 1, 3, 5),
             "Left": (0, 3, 1, 4, 2, 5)}

while True:
    n = int(input())
    if n == 0:
        break
    
    dice = list(range(1, 7))
    ans = 1
    for _ in range(n):
        indices = operation[input().strip()]
        dice = [dice[i] for i in indices]
        ans += dice[0]
        
    print(ans)


Measured memory_bytes: 5620
#include<stdio.h>
#include<string.h>
int main(){
  int i,j=0;
  char x[10],X[1000],y[12]="END_OF_TEXT";
  scanf("%s",x);
  while(1){ 
    scanf("%s",X);
    if (strcmp(X,y)==0)break;
    for(i = 0; X[i] != '\0'; i++){
    X[i] = tolower(X[i]);
  }
    if (strcmp(X,x)==0)j++;
    
  }
  printf("%d\n",j);
  
  return 0; 
}




Measured memory_bytes: 2100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

bool pairwise = true;
vector<bool> seen(1e+6, false);

vector<pair<int, int> > prime_factorize(int n) {
    vector<pair<int, int> > res;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        if(seen[p - 1]) pairwise = false;
        res.push_back(make_pair(p, num)); seen[p - 1] = true;
    }
    if (n != 1){
     	res.push_back(make_pair(n, 1));
  		if(seen[n-1]){
          pairwise=false;
        }
  		seen[n - 1] = true;
    }
    return res;
}


int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}

int main(){
    int N; cin>> N;
    vector<int> A(N);
    bool setwise = true;

    cin>> A[0];
    int cur = A[0];

    for(int i = 1; i < N; i++){
        cin>> A[i];

        cur = gcd(cur, A[i]);
    }

    //setwise
    if(cur != 1) setwise = false;

    //pairwise
    rep(i, N){
        prime_factorize(A[i]);
    }
    //result
    if(pairwise){
        cout<< "pairwise coprime" << endl;
        return 0;
    }
    if(setwise){
        cout<< "setwise coprime" << endl;
        return 0;
    }
    cout<< "not coprime" << endl;
    return 0;
}

Measured memory_bytes: 7148
//g++ -std=c++11 -Wall t.cpp -o test -lm -g
#include <bits/stdc++.h>
#define mod 1000000007
#define Pi 3.14159265358979311599796346854
#define INF 0x3f3f3f3f
#define MAX 400010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector< pii >
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL)
#define forn(i, n) for(int i=0; i<(int)(n); i++)
#define mdc(a, b) (__gcd((a), (b)))
#define mmc(a, b) (((a)/__gcd(a, b)) * b)
#define endl '\n'
#define teto(a, b) (a+b-1)/b
#define ld long double
 
// for(int y : {i - k, i + k})
 
using namespace std;

int dp[100010];
int vet[100010];
int N;

int solve(int x)
{
    if(dp[x]!=-1)
        return dp[x];
    if(x>=N)
        return -1;
    if(x==N-1)
        return 0;

    int um = solve(x+1);
    int dois = solve(x+2);

    int val1=abs(vet[x+1]-vet[x]), val2=abs(vet[x+2]-vet[x]);

    if(um==-1)
        return dp[x] = val2+dois;
    if(dois==-1)
        return dp[x] = val1+um;

    return dp[x] = min(val1+um, val2+dois);

}

int main()
{
    //sws;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    memset(dp, -1, sizeof(dp));

    cin >> N;

    for(int i=0;i<N;i++)
        cin >> vet[i];

    cout << solve(0) << endl;

    return 0;
    
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



void solve(){
  int n;
  llint h,w;
  cin >> n >> h >> w;
  llint a[n],b[n];
  for(int i=0;i<n;i++)cin >> a[i] >> b[i];
  int ans=0;
  for(int i=0;i<n;i++){
    if(a[i]>=h && b[i]>=w)ans++;
  }
  cout << ans << endl;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}
#define MREP(i,m) for(auto i=(m).begin(); i != (m).end(); ++i) // auto key = i->first;auto value = i->second;

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;
I MAX = LONG_MAX;
I MIN = LONG_MIN;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  I n;
  cin >> n;
  V v(n);
  VIN(v);
  SORT(v);
  I t=0;
  REP(i,n){
    I a = v.at(i);
    for(I j=i+1;j<n-1;j++){
      I b = v.at(j);
      I c = lower_bound(ALL(v), a+b) - v.begin();
      //cout << a << " " << b << " " << c << endl;
      c = c - 1 - j;
      t += c;
    }
  }
  cout << t << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
int main(){
	
	int n; cin>>n;
	vector<pair<long double,long double>> v;
	long double x,y;
	for(int i = 0; i < n; i++){
		cin>>x>>y;
		v.push_back({x,y});
	}
	long double co = 0.0;
	vector<long double> dist;
	sort(v.begin(),v.end());
	do {
		long double ans = 0.0;
		for(int i = 1; i < n; i++){
			long double d  = (v[i-1].first-v[i].first) * (v[i-1].first-v[i].first);
			long double e = (v[i-1].second-v[i].second) * (v[i-1].second-v[i].second);
			ans += sqrt(e+d);
		}
		dist.push_back(ans);
		co += 1;
	} while (next_permutation(v.begin(),v.end()));
	long double avg = 0.0;
	for(auto xx : dist) avg += xx;
	cout<<setprecision(12)<<avg/co<<"\n";
}


Measured memory_bytes: 1400
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
 
#define int                     long long
#define file(s)                 freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a)          for(int i = (b); i >=(a); i--)
#define forn(i, a, b)           for(int i = (a); i <= (b); i++)
#define speed                   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
typedef long long ll;
typedef double db;
typedef long double ldb;
 
const ldb pi = 3.14159265358979323846264;
const int maxn = 2e5 + 1;
const int mod = 1e9 + 7;

string s, t, ans;
int dp[3001][3001];
pair < int , int > p[3001][3001];

main(){
    //file("");
    speed;
    cin >> s >> t;
    s = ' ' + s;
    t = ' ' + t;
    for(int i = 1; i < s.size(); i++){
        for(int j = 1; j < t.size(); j++){
            if(s[i] == t[j]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
                p[i][j] = {i - 1, j - 1};
            }
            else {
                if(dp[i][j - 1] > dp[i - 1][j])p[i][j] = {i, j - 1};
                if(dp[i - 1][j] > dp[i][j - 1])p[i][j] = {i - 1, j};
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); 
            }
        }
    }
    int n = s.size() - 1;
    int m = t.size() - 1;
    int i = n, j = m;
    while(i > 0 && j > 0){
        if(s[i] == t[j]){
            ans += s[i];
            i--;
            j--;
        }
        else if(dp[i - 1][j] > dp[i][j - 1]){
            i--;
        }
        else{
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
    return 0; 
}


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

int main(){
  int i,j,cnt=0;
  string s;
  cin>>s;
  if(s=="zyxwvutsrqponmlkjihgfedcba"){
    cout<<-1;
    return 0;
  }
  int a[26];
  for(i=0;i<26;i++)a[i]=0;
  for(i=0;i<s.size();i++)a[s[i]-'a']++;
  if(s.size()!=26){
    for(i=0;i<26;i++){
      if(a[i]==0){
        cout<<s+(char)('a'+i);
        return 0;
      }
    }
  }
  cnt=s.size()-1;
  string t=s;
  while(1){
    a[s[cnt]-'a']--;
    s=s.substr(0,cnt);
    for(i=0;i<26;i++){
      if(a[i]==0){
        if(s+(char)(i+'a')>t){
          cout<<s+(char)(i+'a');
          return 0;
        }
      }
    }
    cnt--;
  }
}

Measured memory_bytes: 256
N, Y = list(map(int, input().split()))
Y //= 1000
for x in range(0, Y//10+1):
    for y in range(0, (Y-10*x)//5+1):
        z = N-x-y
        if (9*x + 4*y) == Y-N and z >= 0:
            print(x, y, N-x-y)
            exit()
print(-1, -1, -1)


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

#define FOR(i, a, b) for (int i = (a); i < static_cast<int>(b); i++)
#define FORR(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) FOR (i, 0, n)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
template <typename T>
void print(const vector<vector<T>> matrix);
template <typename T>
void print(const vector<T> vec);
template <typename Arg>
void print(const Arg arg);
template <typename Head, typename... Args>
void print(const Head head, const Args... args);
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
using ll = long long;

typedef pair<int, int> P;

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

    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> L(M), R(M), p(Q), q(Q);

    rep (i, M)
        cin >> L[i] >> R[i];
    rep (i, Q)
        cin >> p[i] >> q[i];

    vector<int> v(N + 1);
    vector<vector<int>> table(N + 1, vector<int>(N + 1));

    rep (i, M) {
        for (int j = 1; j <= L[i]; j++) {
            table[j][R[i]]++;
        }
    }

    rep (i, Q) {
        int cnt = 0;
        for (int j = 1; j <= q[i]; j++) {
            cnt += table[p[i]][j];
        }
        print(cnt);
    }

    return 0;
}

//---------------------------------------------
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    repall (i, vec)
        cout << i << ' ';
    cout << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(i64 i = 0; i < N; i++)
#define Rep(i, k, N) for(i64 i = k; i < N; i++)
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define Cout(s) cout << s << endl
string Yes(bool b) {if(b){return "Yes";} else {return "No";}}
string YES(bool b) {if(b){return "YES";} else {return "NO";}}

int main(){
    i64 N;
    cin >> N;
    vector<i64> A(N);
    rep(i, N) cin >> A[i];

    map<i64, i64> mp;
    rep(i, N) mp[i+1-A[i]]++;

    i64 ans = 0;
    rep(i, N) ans += mp[A[i] + i + 1];

    Cout(ans);
}


Measured memory_bytes: 27400
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d,l,r;
  cin >> a >> b >> c >> d;
  l = a + b;
  r = c + d;
  
  if (l > r) {
    cout << "Left";
  }
  
  else if (r > l) {
    cout << "Right";
  }
  
  else {
    cout << "Balanced";
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1e9+7;

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

	string s1;
	string s2;
	cin>>s1;
	cin>>s2;

	bool x = 0;
	bool y = 0;
	ll ans = 1;
	int idx = 0;
	if(s1[0]!=s2[0]){
	 idx+=2;
	 ans = 6;
	 y = 1;
	}
	else{
	x = 1;
	idx+=1;
	 ans = 3;
	}

	while(idx<n){
		if(s1[idx]!=s2[idx] && y){
			ans*=3%M;
			idx+=2;
		}
		else if(s1[idx] == s2[idx] && y){
			y = 0;
			x = 1;
			ans*=1%M;
			idx+=1;
		}
		else if(s1[idx]!=s2[idx] && x){
			y = 1;
			x = 0;
			ans*=2%M;
			idx+=2;
		}
		else if(s1[idx]==s2[idx] && x){
			ans*=2%M;
			idx+=1;
		}
	}
	cout<<ans%M;
}

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

using namespace std; 

int main() {
  
  int x; cin >> x;
  
  vector<int> vec(x);
  for(int i=0; i<x; i++){
    cin >> vec.at(i);
  }
  
  vector<int> vec_s = vec;
  sort(vec_s.begin(), vec_s.end());
  
  for(int i=0; i<x; i++){
    if (vec.at(i) < vec_s.at(x/2)){
      cout << vec_s.at(x/2) << endl;
    } else {
      cout << vec_s.at(x/2-1) << endl;
    }
  }  
  
  
  

}

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

#define lli	long long int

int main(void) {
	int n, W; cin >> n >> W;
	vector<int> w(n+1), v(n+1);
	for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

	vector< vector<lli> > dp(n+1, vector<lli>(W+1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			dp[i][j] = max(dp[i-1][j], (j >= w[i]) ? (dp[i-1][j-w[i]] + v[i]) : 0);
		}
	}

	cout << dp[n][W];

	return 0;
}


Measured memory_bytes: 80256
#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

using ll = long long int;

int main(){
    
    ll N;
    string S[64];
    
    cin >> N;
    for(ll i = 0; i < N; ++i){
        cin >> S[i];
    }
    
    int cnt[64][26] = {0};
    int mcnt[26];
    
    for(ll i = 0; i < N; ++i){
        for(char c : S[i]){
            cnt[i][c - 'a'] += 1;
        }
    }
    
    for(ll j = 0; j < 26; ++j){
        mcnt[j] = 1000000;
        for(ll i = 0; i < N; ++i){
            mcnt[j] = min(mcnt[j], cnt[i][j]);
        }
    }
    
    string ans = "";
    
    for(ll j = 0; j < 26; ++j){
        for(ll k = 0; k < mcnt[j]; ++k){
            ans.push_back(j + 'a');
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef unsigned long long ull;
typedef long long ll;

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define speedhack() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define form(i, n) for (size_t i = 0; i < size_t(n); ++i)
#define forn(i, n) for (size_t i = 1; i <= size_t(n); ++i)

template<class T> using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod(ll a, ll b) { return (a%b+b)%b; }
ll gcd(ll x, ll y) { return __gcd(x, y); }
ll lcm(ll x, ll y) { return x * 1ll * y / gcd(x, y); }
 
const ll MAXN = 1e18;
const ll SIZE = 2e5 + 5;
const ll MOD  = 1e9 + 7;


ll n, k;
int a[SIZE];
vector<int> c;
bool used[SIZE];



void dfs (int v) {
	used[v] = true;
	c.push_back(v);
	if (!used[a[v]])
		dfs (a[v]);
}

int main() { speedhack()

	cin >> n >> k;
	forn (i, n)
		cin >> a[i];
	
	dfs (1);

	if ((int)c.size() - 1 < k && a[c.back()] == c.back())
		cout << c.back();
	else if ((int)c.size() - 1 >= k)
		cout << c[k];
	else {
		k -= ((ll)c.size() - 1);
		reverse (all(c));
		while (c.back() != a[c[0]])
			c.pop_back();
		reverse (all(c));
		n = c.size();
		int rem = ((k % n) == 0) ? n : (k % n);
		cout << c[rem - 1];
	}
	return 0;
}


Measured memory_bytes: 11044
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W,c;
  string S,Sall="",Snew="";
  cin >> H >> W;
  for (int i=0;i<H;i++){
    cin >> S;
    Sall += S;
  }
  for (int i=0;i<H*W;i+=W){
    for (int j=0;j<W;j++){
      //cout << "i:" << i << ",j:" << j << endl;
      if (Sall.at(i+j)=='#'){
        cout << "#";
        //continue;
      }else if (Sall.at(i+j)=='.'){
        c=0;
        for (int di=-W;di<=W;di+=W){
          for (int dj=-1;dj<=1;dj++){
            if (i+j+di+dj>=0 && i+j+di+dj<H*W && j+dj>=0 && j+dj<W){
              //cout << i << j << di << dj << endl;
              if (Sall.at(i+j+di+dj)=='#'){
                c+=1;
              }
            }
          }
        }
        cout << c;
        //Sall.at(i+j) = c;
      }
    }
    cout << endl;
  }
  /*for (int i=0;i<H*W;i+=W){
    for (int j=0;j<W;j++){
      cout << Sall.at(i+j);
    }
    cout << endl;
  }*/
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549

"""
import sys
from sys import stdin
from itertools import accumulate
input = stdin.readline




def main(args):
    n, m = map(int, input().split())
    distances = [int(input()) for _ in range(n-1)]
    inns = list(accumulate(distances))
    moves = [int(input()) for _ in range(m)]

    inns.insert(0, 0)
    pos = 0
    total_distance = 0
    for m in moves:
        new_pos = pos + m
        total_distance += abs(inns[new_pos] - inns[pos])
        pos = new_pos

    print(total_distance % 100000)


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 16520
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try(Scanner scan = new Scanner(new InputStreamReader(System.in))){
			int N = scan.nextInt();
			int M = scan.nextInt();
			
			int[] box = new int[N+1];
			Arrays.fill(box, 1);
			box[0] = 0;

			boolean[] red = new boolean[N+1];
			red[1] = true;
			
			for(int i = 0; i < M; i++){
				int x = scan.nextInt();
				int y = scan.nextInt();
				
				box[x]--;
				box[y]++;
				
				if(red[x] == true){
					red[y] = true;
				}
				if(box[x] == 0){
					red[x] = false;
				}
			}
			
			int ans = 0;
			for(int i = 1; i <= N; i++){
				if(red[i] == true){
					ans++;
				}
			}
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 22256
def area(p,q):return p[0]*q[1]-p[1]*q[0]
 
n=int(input())
point=[]
x_1,y_1=[int(i) for i in input().split(" ")]
 
for i in range(n-1):
    x,y=[int(k) for k in input().split(" ")]
    point.append([x-x_1,y-y_1])
a=0
for i in range(n-2):a+=area(point[i],point[i+1])
print(a*0.5)

Measured memory_bytes: 7740
#include<stdio.h>
#include<string.h>
#define LEN 100
#define END "END_OF_TEXT"
void lower(char[]);
int main(void)
{
  char w[LEN],t[LEN];
  int count=0;
  scanf("%s",w);
  for(;;)
    {
      scanf("%s",t);
      if(strcmp(END,t)==0) break;
      lower(t);
      if(strcmp(w,t)==0) count++;
    }
  printf("%d\n",count);
  return 0;
}
void lower(char str[])
{
  int i;
  int len=strlen(str);
  for(i=0;i<len;i++)
    {
      if(str[i]>='A'&&str[i]<='Z') str[i]+='a'-'A';
    }
}


Measured memory_bytes: 2060
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if (a == b && b == c){
            System.out.println("1");
        }else if (a != b && b == c ){
            System.out.println("2");
        }else if (a == b){
            System.out.println("2");
        }else if (a == c){
            System.out.println("2");
        }else{
            System.out.println("3");
        }
    }
}


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

signed main(){
    int a,b,c,k;
    vector<int> d(3);
    cin >> a >> b >> c >> k;
   if(abs(a - b) > 1e18){
   cout << "Unfair" << endl;
   return 0;
   }
   else
   {
       if(k % 2 == 0)
       cout << a - b << endl;
       if(k % 2 == 1)
       cout << -(a - b) << endl;
   }
   
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int a=0;
	int b=0;
	int c=0;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);

	if (a < b&&b < c) {
		printf("%d %d %d\n",a,b,c);
	}
	if (b < a&&a < c) {
		printf("%d %d %d\n",b,a,c);
	}
	if (c < a&&a < b) {
		printf("%d %d %d\n",c,a,b);
	}
	if (a < c&&c < b) {
		printf("%d %d %d\n",a,c,b);
	}
	if (b < c&&c < a) {
		printf("%d %d %d\n",b,c,a);
	}
	if (c < b&&b < a) {
		printf("%d %d %d\n",c,b,a);
	}
	if (a == b && b == c) {
		printf("%d %d %d\n", a,b,c);
	}
	if (a == b && b < c) {
		printf("%d %d %d\n", c,b,a);
	}

	if (a == c && b < c) {
		printf("%d %d %d\n",b,c,a);
	}

	if (c == b && a < c) {
		printf("%d %d %d\n", a,b,c);
	}

	if (c == b && b < a) {
		printf("%d %d %d\n", c,b,a);
	}

	if (a == b && c > b) {
		printf("%d %d %d\n", a,b,c);
	}

	if (a == c && b > c ) {
		printf("%d %d %d\n",a,c,b);
	}


	 return 0;
}


Measured memory_bytes: 2100
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            var Hi = Sarray();
            var max = 0;
            var cnt = 0;
            for (var i = 0; i < N - 1; ++i)
            {
                if (Hi[i] >= Hi[i + 1])
                    ++cnt;
                else
                    cnt = 0;
                max = Max(max, cnt);
            }

            WriteLine(max);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 29404
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define io std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const double pi=acos(-1);
const ll P = 998244353, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
const double eps=1e-5;
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int maxn=2e5+10;
int a[maxn];
int n;
ll check(int x)
{ ll ans=0;
  for(int i=1;i<=n;i++)
  { 
        ans+=abs(a[i]-x);
  }
  return ans;
}
int _find(int l,int r)
{
    if(l>=r) return l;
    int midl=(l+r)>>1,midr=(midl+r)>>1;
    if(check(midl)>check(midr)) return _find(midl,r);
    return _find(l,midr);
}
int main()
{
  cin>>n;
  int l=-1e9,r=1e9;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    a[i]-=i;
  }
  int xx=_find(l,r);
  cout<<min(check(xx),check(xx+1))<<endl;
}

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

using namespace std;

typedef long long ll;

void solve() {
	int n; cin >> n; int ans = -n;
	while(cin >> n) {
        ans += n;
	}
	cout << ans;
}

int main() {
    //freopen("input.txt", "r", stdin);
    solve();
}


Measured memory_bytes: 256
/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define inf 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define cub(x) ((x)*(x)*(x))
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
	int x=0,f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=1e5;
ll A[N+10],B[N+10];
map<ll,int>Mp;
int main(){
	int n=read();
	for (int i=1;i<=n;i++){
		ll x,y=1;
		scanf("%lld",&x);
		for (ll j=2;cub(j)<=x;j++)	while (x%cub(j)==0)	x/=cub(j);
		map<ll,int>::iterator it=Mp.find(x);
		if (it==Mp.end())	Mp.insert(map<ll,int>::value_type(x,1));
		else	it->Se++;
		A[i]=x;
		for (ll j=2;cub(j)<=x;j++){
			if (x%j==0){
				y*=(x%sqr(j)==0)?j:sqr(j);
				while (x%j==0)	x/=j;
			}
		}
		y*=(sqr((ll)sqrt(x))==x)?(ll)sqrt(x):sqr(x);
		B[i]=y;
	}
	int Ans=0;
	map<ll,int>::iterator it=Mp.find(1);
	if (it!=Mp.end())	Ans++,it->Se=0;
	for (int i=1;i<=n;i++){
		int res=0;
		map<ll,int>::iterator x=Mp.find(A[i]);
		map<ll,int>::iterator y=Mp.find(B[i]);
		if (x!=Mp.end())	res=max(res,x->Se),x->Se=0;
		if (y!=Mp.end())	res=max(res,y->Se),y->Se=0;
		Ans+=res;
	}
	printf("%d\n",Ans);
	return 0;
}

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

int main(){
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, pair<int, int>>> event;
    for (int i = 0; i < N; i++) {
        int s, t, x;
        cin >> s >> t >> x;
        event.push_back({s-x, {1, x}});
        event.push_back({t-x, {-1, x}});
    }
    sort(event.begin(), event.end());
    set<int> stop;
    auto it = event.begin();
    for (int i = 0; i < Q; i++) {
        int d;
        cin >> d;
        while (it != event.end() && (*it).first <= d) {
            int p = (*it).second.first;
            int q = (*it).second.second;
            if (p == 1) stop.insert(q);
            else stop.erase(q);
            it++;
        }
        if (!stop.empty()) cout << *stop.begin() << endl;
        else cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 16620
Input = input().split()
X = Input[0]
X = int(X)
N = Input[1]
N = int(N)
if N != 0:
    P = input().split()
    Z = 0
    A = 0
    while Z < 1:
        B = X + A
        C = X - A
        B = str(B)
        C = str(C)
        if not(C in P):
            D = C
            Z = 1
            break
        if not(B in P):
            D = B
            Z = 1
            break
        A += 1
else:
    D = X

print(D)

Measured memory_bytes: 9104
#include<bits/stdc++.h>
using namespace std;
//回文かどうかの判定
bool turn(string s,int a,int b){
  vector<char> right;
  vector<char> left;
  for (int i = a; i <= b; i++)
  {
    left.push_back( s.at(i));
    right.push_back(s.at(b-i));
  }
  if(left==right){
    return true;
  }else{
    return false;
  }
}
int main(){
  string s;
  cin >> s;
  int N = s.size();
  int tmp1 = (N - 2) / 2;
  int tmp2 = (N + 2) / 2;

  if (turn(s,0,tmp1)&& turn(s,tmp2,N-1))
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    c=[[] for _ in range(4)]
    for i in range(1,4):
        c[i] = [0]+list(map(int, input().strip().split()))
        
    def diff(i,j,k):
        return c[k][i] - c[k][j]
    if diff(3,2,1)==diff(3,2,2)==diff(3,2,3) and diff(2,1,1)==diff(2,1,2)==diff(2,1,3):
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Measured memory_bytes: 61548
#include <stdio.h>
#include <math.h>

int main() {
    int a, b, ang;
    double S, L, h, rad;
    scanf("%d %d %d", &a, &b, &ang);
    rad = ang * M_PI / 180;
    S = a * b * sin(rad) / 2.0;
    L = a + b + sqrt((a * a) + (b * b) - (2 * a * b * cos(rad)));
    h = 2 * S / a;
    printf("%f\n", S);
    printf("%f\n", L);
    printf("%f\n", h);
    return 0;
}



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

using namespace std;

using int64 = long long;

int main() {
  int A, B;
  cin >> A >> B;
  for(int i = 1; i <= 3; i++) {
    if((A * B * i) % 2 == 1) {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
}

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

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

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

int sx,sy,gx,gy;
int H,W;
vector<string> S;

ll solve(){
    vector<vector<int>> dist(H,vector<int>(W,-1));
    deque<pint> que;
    dist.at(sy).at(sx) = 0;
    que.push_front(pint(sy,sx));
    while(!que.empty()){
        auto cur = que.front();
        que.pop_front();
        int y = cur.first, x = cur.second;
        //移動A
        for(int dir = 0; dir < 4; dir++){
            int ny = y + dy[dir], nx = x + dx[dir];
            if(nx<0 || ny<0 || nx >= W || ny >= H)continue;
            if(S.at(ny).at(nx)=='#')continue;
            if(dist.at(ny).at(nx)==-1){
                dist.at(ny).at(nx) = dist.at(y).at(x);
                que.push_front(pint(ny,nx));
            }else if(dist.at(ny).at(nx)>dist.at(y).at(x)){
                dist.at(ny).at(nx) = dist.at(y).at(x);
                que.push_front(pint(ny,nx));
            }
        }
        //移動B
        for(int ny = y - 2; ny <= y + 2; ny++){
            for(int nx = x - 2; nx <= x + 2; nx++){
                if(nx<0 || ny<0 || nx >= W || ny >= H)continue;
                if(S.at(ny).at(nx)=='#')continue;
                if(dist.at(ny).at(nx)==-1){
                    //未知の領域
                    dist.at(ny).at(nx) = dist.at(y).at(x) + 1;
                    que.push_back(pint(ny,nx));
                }else if(dist.at(ny).at(nx)>dist.at(y).at(x)+1){
                    dist.at(ny).at(nx) = dist.at(y).at(x)+1;
                    que.push_front(pint(ny,nx));
                }
            }
        }
    }
    return dist.at(gy).at(gx);
}

int main(){
    cin>>H>>W>>sy>>sx>>gy>>gx;
    sy--;sx--;gy--;gx--;
    S.resize(H);
    for(int i = 0; i < H; i++)cin>>S.at(i);
    cout<<solve()<<endl;
}

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

class Main {
	public static void main (String[] args) throws IOException {
		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);
		String[] strAry = br.readLine().split(" ");
		int a = Integer.parseInt(strAry[0]);
		int b = Integer.parseInt(strAry[1]);
		int c = Integer.parseInt(strAry[2]);
		int count = 0;
		for (int i = a; i <= b; i++) {
			if ((c % i) == 0) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 24264
h, w = gets.split.map(&:to_i)
strs = (1..h).map { |i| gets.chomp }

def get_new_str(strs, i)
  new_str = ''
  strs[i].each_char.with_index do |s, j|
    if s == '#'
      new_str << s
    else
      new_str << get_bomb_count(strs, i, j).to_s
    end
  end
  new_str
end

class NilClass
  def [](i)
    nil
  end
end

def get_bomb_count(strs, i, j)
  a =
    if i == 0 && j == 0
      [strs[i][j+1],
       strs[i+1][j],
       strs[i+1][j+1]]
    elsif i == 0
      [strs[i][j-1],
       strs[i][j+1],
       strs[i+1][j-1],
       strs[i+1][j],
       strs[i+1][j+1]]
    elsif j == 0
      [strs[i-1][j],
       strs[i-1][j+1],
       strs[i][j+1],
       strs[i+1][j],
       strs[i+1][j+1]]
    else
      [strs[i-1][j-1],
       strs[i-1][j],
       strs[i-1][j+1],
       strs[i][j-1],
       strs[i][j+1],
       strs[i+1][j-1],
       strs[i+1][j],
       strs[i+1][j+1]]
    end
  a.compact.reject { |n| n=='.' }.length
end

ans = []
strs.each_with_index do |str, i|
  a = get_new_str(strs, i)
  ans << a
end
puts ans

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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

ll gcd(ll a, ll b)
{
    if (a < b)
        gcd(b, a);
    if (b == 0)
        return a;
    int r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    int n, nn;
    int tmp = 0;
    cin >> n;
    nn = n;
    while (n)
    {
        tmp = (tmp * 10) + (n % 10);
        n /= 10;
    }
    // cout << tmp << endl;
    if (nn == tmp)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256