akhauriyash/Code-Regression huggingface dataset:
# n以下の非負整数が素数かどうかを示すリストを返す
def primes(n):
    is_prime = [False] * 2 + [True] * (n - 1)
    for i in [2] + list(range(3, int(n ** 0.5) + 1, 2)):
        if not is_prime[i]: continue
        for j in range(2 * i, n + 1 ,i):
            is_prime[j] = False
    return is_prime

N = 10 ** 5
Q = int(input())
is_prime = primes(N)
cum2017 = [0] * (N + 1) # 累積和
for i in range(1, N + 1):
    cum2017[i] = cum2017[i - 1]
    if i % 2 == 1 and is_prime[i] and is_prime[(i + 1) // 2]:
        cum2017[i] += 1

for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    print(cum2017[r] - cum2017[l - 1])

Measured memory_bytes: 10768
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    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...);
    }
#else
#define trace(...)
#endif

const ll N = 1e2 + 5;
ll i,j,n,ans;
string s;
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>s;
    rep(i,0,n){
        j = i;
        while(j < n && s[i] == s[j]) j += 1;
        i = j - 1;
        ans += 1;
    }
    cout<<ans;
    return 0;
} 

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

int main()
{
   int innerRating, displayRating, numContest;

   scanf("%d %d", &numContest, &displayRating);

   if (numContest >= 10)
   {
       printf("%d", displayRating);
   } else
   {
       innerRating = displayRating + (100*(10 - numContest));
       printf("%d", innerRating);
   }
    

    return 0;
}

Measured memory_bytes: 1636
n, m = map(int,input().split())
food = [i for i in range(1,m+1)]
for i in range(n):
     n = list(map(int,input().split()))
     n.pop(0)
     new_food = list()
     for j in food:
          if j in n:
               new_food.append(j)
     food = new_food
print(len(new_food))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define  all(x) (x).begin(),(x).end()
typedef long long ll;

typedef struct Card{
    char mark;
    int value;
} Card;

const Card INF = Card{'I', 1000000005};
vector<Card> L, R;

void merge(vector<Card>& m, int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i, n1) L[i] = m[left+i];
    rep(i, n2) R[i] = m[mid+i];
    L[n1] = R[n2] = INF;
    int i = 0, j = 0;
    for(int k = left; k < right; k++){
        if (L[i].value <= R[j].value){
            m[k] = L[i++];
        }else{
            m[k] = R[j++];
        }
    }
}

void mergeSort(vector<Card>& m, int left, int right){
    if (left+1 < right){
        int mid = (left + right) / 2;
        mergeSort(m, left, mid);
        mergeSort(m, mid, right);
        merge(m, left, mid, right);
    }
}

int partition(vector<Card>& q, int p, int r){
    int x = q[r].value;
    int i = p - 1;
    for(int j = p; j < r; j++){
        if (q[j].value <= x){
            i++;
            swap(q[i], q[j]);
        }
    }
    i++;
    swap(q[i], q[r]);
    return i;
}

void quitSort(vector<Card>& q, int l, int r){
    if (l < r){
        int i = partition(q, l, r);
        quitSort(q, l, i-1);
        quitSort(q, i+1, r);
    }
}

void print(vector<Card> q, int n){
    rep(i,n){
        cout << q[i].mark << " " << q[i].value << endl;
    }
}

int main(){
    int n;
    cin >> n;
    vector<Card> q(n), m(n);
    L = R = vector<Card>(n/2 + 2);
    rep(i,n){
        char mark;
        int value;
        cin >> mark >> value;
        q[i] = Card{mark, value};
        m[i] = Card{mark, value};
    }

    quitSort(q, 0, n-1);
    mergeSort(m, 0, n);
    bool ok = true;
    rep(i, n) if(q[i].mark != m[i].mark) ok = false;
    if (ok) cout << "Stable" << endl;
    else cout << "Not stable" << endl;
    print(q, n);
    return 0;
}


Measured memory_bytes: 5812
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;

int main()
{
    //freopen("input.txt","r",stdin);
    int n,d;
    cin>>n>>d;
    d=d*2+1;
    if(n%d==0) cout<<n/d;
    else cout<<n/d+1;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

		int ans = 0;
		for (int i = 1; i <= N; i++) {
			int sum = 0, temp = i;
			while (temp > 0) {
				sum += temp % 10;
				temp /= 10;
			}
			if (A <= sum && sum <= B) {
				ans += i;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21716
#include <stdio.h>
#include <math.h>
int main(void){
	double x_1,x_2,y_1,y_2,suti,a;

	scanf("%lf %lf %lf %lf",&x_1,&y_1,&x_2,&y_2);
	
	suti=(y_2-y_1)*(y_2-y_1)+(x_2-x_1)*(x_2-x_1);

	a = sqrt(suti);

	printf("%lf\n",a);

	return 0;
}

Measured memory_bytes: 652
//============================================================================
// Name        : d.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>

using namespace std;

int main() {
	int n;cin>>n;
	long long ans=0;
	vector<vector<int>> v(10,vector<int>(10,-1));
	for(int i=1;i<10;i++){
		for(int j=1;j<10;j++){
			int count=0;
			for(int k=1;k<=n;k++){
				int back=k%10;
				int top=k;
				while(top>=10){
					top/=10;
				}
				if(i==top){
					if(j==back){
						count++;
					}
				}
			}
			v[i][j]=count;
		}
	}
	for(int i=1;i<=n;i++){
		int back=i%10;
		if(back==0)continue;
		int top=i;
		while(top>=10){
			top/=10;
		}
		ans+=v[back][top];
//		cout<<i<<' '<<v[back][top]<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
int cnt[111];
signed main(){
	int n;
	cin>>n;
	rep(i,n){
		int a;
		cin>>a;
		cnt[a]++;
	}
	int ans=0;
	for(int i=1;i<=100;i++)if(cnt[i])ans++;
	cout<<ans<<endl;
}


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

using namespace std;

int reduce(string s, char c) {
	int max_val = -1;

	int count = 0;
	for(int i = 0; i < s.length(); i++) {
		if (c == s.at(i)) {
			max_val = max(max_val,count);
			count = 0;
		} else {
			count++;
		}
	}
	return max(max_val,count);
}


int main() {
	string s;

	cin >> s;

	int min_val = 1000;

	for (char c = 'a'; c <= 'z'; c++) {
		min_val = min(reduce(s, c),min_val);
	}

	cout << min_val << endl;
 
	return 0;
}

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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr = ds.begin(); itr != ds.end(); ++itr)
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
#define PI 3.1415926536
typedef long long ll;
typedef pair<int, int> P;

int main() {
	int N;
	cin >> N;
	vector<int> a(N);
	vector<P> p;
	int top = 0;
	rep(i, N) {
		cin >> a[i];
		if (a[i] > top) {
			p.push_back(mp(i, a[i]));
			top = a[i];
		}
	}
	// 昇順
	sort(begin(a), end(a));

	int now = 0;
	vector<ll> num(p.size(), 0);
	int idx = 0;
	rep(i, N) {
		if (a[i] >= p[now].second) {
			num[now] += (ll)(now == 0 ? p[now].second : p[now].second - p[now - 1].second) * (N - i);
			now++;
			if (now >= p.size())break;
		}
		else {
			num[now] += max(0, now == 0 ? a[i] : a[i] - p[now - 1].second);
		}
	}
	now = 0;
	rep(i, N) {
		if (now < p.size() && i == p[now].first) {
			cout << num[now] << endl;
			now++;
		}
		else {
			cout << 0 << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3188
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (X, Y): (i64, i64) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };

    let ans = format!("{:b}", Y / X).len();

    println!("{}", ans);
}

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

using namespace std;

int main()
{
   int n,a=0,t=0,w=0,r=0;
   cin>>n;
   string k;
for(int i=0;i<n;i++){
    cin>>k;
if(k=="AC")
a++;
if(k=="TLE")
t++;
if(k=="RE")
r++;
if(k=="WA")
w++;}
cout<<"AC"<<" "<<"x"<<" "<<a<<endl;
cout<<"WA"<<" "<<"x"<<" "<<w<<endl;
cout<<"TLE"<<" "<<"x"<<" "<<t<<endl;
cout<<"RE"<<" "<<"x"<<" "<<r<<endl;

   return 0;
}

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

int main()
{
    string arr;
    cin >> arr;
    int sum=0;
    for(int i=0;i<arr.length();i++)
        sum+=arr[i]-'0';
    if(sum%9)
        cout << "No";
    else
        cout << "Yes";
 
}

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

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef long long ll; 
typedef long double ld; 
typedef pair<int,int> p32;   
typedef pair<ll,ll> p64;  
typedef pair<double,double> pd; 
typedef pair<ld,ld> pld; 
typedef vector<int> v32;  
typedef vector<ll> v64;  
typedef vector<pd> vpd;   
typedef vector<p32> vp32;  
typedef vector<p64> vp64;  
typedef vector<v32> vv32;  
typedef vector<v64> vv64;  

#define pb push_back
#define mp make_pair
#define prarr(a,n) cerr<<#a<<" : ";for(ll i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define prmat(mat,row,col) cerr<<#mat<<" :\n";for(ll i=0;i<row;i++) {for(ll j=0;j<col;j++) cerr<<mat[i][j]<<"\t";cerr<<endl;}
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
#define all(a) a.begin(),a.end()
#define sz(x) ((int)x.size())
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(NULL); cin.tie(NULL)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {ll idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ", "; dbs(str.substr(idx + 1), s...);}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
template <class T> void prall(T a) { prc(all(a)); }


const int inf=1000*1000*1000+9; 
const ll infl=1ll*inf*inf; 
int mod=1000*1000*1000+7;  
// ---------------------------------------------------------------------------- -------------- 

const int nax=1e5+5; 
v32 adj[nax]; 
int vis[nax]; 
void dfs(int u){
  vis[u]=1; 
  for(int v:adj[u]){
    if(vis[v]==0){
      dfs(v);
    }
  }
}

void solve(){
  int n,m; 
  cin>>n>>m; 
  for(int i=0;i<m;i++){
    int x,y,z; cin>>x>>y>>z;  
    adj[x].push_back(y); 
    adj[y].push_back(x); 
  }
  int c=0; 
  for(int i=1;i<=n;i++){
    if(vis[i]==0){
      dfs(i); 
      c++; 
    }
  }
  cout<<c<<endl; 
}

int main(){
	// clock_t beg=clock(); 
  fast_io; 
  int testcases=1; 
  // cin>>testcases; 
  cout << fixed << setprecision(13); 
  while(testcases--){
    solve(); 	
  }
	// clock_t end=clock(); 
	// fprintf(stderr, "%lf\n", (double)(end-beg)/(CLOCKS_PER_SEC));
}


Measured memory_bytes: 9216
#include <iostream>
 #include <cstdio> 
#include <cstring> 
using namespace std;
 int main(){
 char a[50],b[50],c[100]; 
while(cin>>a>>b){ 
int i,j; c[0]=a[0]; 
for(i=1,j=0;i<=100;i++)
{
 if(i%2!=0)
 {c[i]=b[j];j++;} 
else c[i]=a[j]; 
} 
cout<<c<<endl; 
}
 return 0;
 } 

Measured memory_bytes: 256
def judge(t500,t1000)
  rank = [\
          ["AAA",35.5, 71.0],\
          ["AA", 37.5, 77.0],\
          ["A",  40.0, 83.0],\
          ["B",  43.0, 89.0],\
          ["C",  50.0,105.0],\
          ["D",  55.0,116.0],\
          ["E",  70.0,148.0],\
          ["NA",999999.9,9999999.9]]
  rank.select{|r,t0,t1| t500<t0 and t1000<t1}.first.first
end
def main
  if true then
    fh=STDIN
  else
    fh=open"in1_0123.txt"
  end
  while fh.gets do
    t500,t1000=$_.chomp.split.map{|x| x.to_f}
    puts judge(t500,t1000)
  end
end

if $0 == __FILE__ then
  main
end

Measured memory_bytes: 8656
using System;
using System.Collections.Generic;

namespace AtCoderCpp
{
    // ABC-126
    class Program
    {
        static void Main(string[] args)
        {
            var input1 = Console.ReadLine().Split(' ');
            var N = int.Parse(input1[0]);
            var K = int.Parse(input1[1]);

            var input2 = Console.ReadLine().ToCharArray();
            input2[K - 1] = input2[K - 1].ToString().ToLower().ToCharArray()[0];

            foreach (var item in input2)
            {
                Console.Write(item);
            }
            Console.WriteLine();
        }
    }
}



Measured memory_bytes: 11092
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long N, std::vector<long long> x, std::vector<long long> y){
    vector<pll> pt(N);
    REP(i, N) {
        pt[i].first = x[i];
        pt[i].second = y[i];
    }
    ll ans = N;
    REP(i, N-1){
        for(ll j=i+1; j < N; j++){
            ll p = x[j]-x[i], q = y[j]-y[i];
            ll cnt = 0;
            set<pll> tmp(pt.begin(), pt.end());
            while(!tmp.empty()){
                ll refx = tmp.begin()->first, refy = tmp.begin()->second; 
                cnt ++;
                tmp.erase(tmp.begin());
                if(tmp.empty())
                    break;
                for(auto it = tmp.begin(); it != tmp.end(); ){
                    if(it->first - refx == p && (it->second - refy) == q){
                        refx = it->first; refy = it->second;
                        it = tmp.erase(it);
                    }
                    else{
                        ++it;
                    }
                }
            }
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(N, std::move(x), std::move(y));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int n,m;
	while(1){
		cin>>n>>m;
		if(n==0 && m==0)break;
		priority_queue<int,vector<int>,greater<int> > que;
		que.push(0);
		int num;
		rep(i,n+m){
			cin>>num;
			que.push(num);
		}
		int timemax=0;
		while(que.size()>1){
			num=que.top();
			que.pop();
			timemax=max(timemax,que.top()-num);
		}
		cout<<timemax<<endl;
	}
	return 0;
}

Measured memory_bytes: 1348
from collections import Counter

def chk():
    N = int(input())
    A=list(map(int,input().split(' ')))
    counter = Counter(A)

    flg = [0 for _ in range(10**6+1)]

    ans = 0
    for i in range(1,10**6+1):
        if counter[i] == 0:
            continue
        if flg[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1,((10**6)//i)+1):
            flg[i*j] = 1

    print(ans)

chk()


Measured memory_bytes: 44320
#include<bits/stdc++.h>
#define F 110000
using namespace std;vector<int> v[F];int a,b,x,y,r,i;int D(int t){int e=0;while(e*e<=r*r-t*t)e++;return e-1;}int main(){while(cin>>a>>b>>r&&a+b){for(int i=0;i<F;i++)v[i].clear();r*=4;for(i=0;i<a;i++){cin>>x>>y;v[x].push_back(y);}for(i=0;i<a;i++)sort(v[i].begin(),v[i].end());int n=0;while(b--){cin>>x>>y;for(i=max(0,x-r);i<=min(F-100,x+r);i++)n+=lower_bound(v[i].begin(),v[i].end(),y+D(x-i)+1)-lower_bound(v[i].begin(),v[i].end(),y-D(x-i));}cout<<n<<endl;}return 0;}

Measured memory_bytes: 6936
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
template <typename T>
struct dijkstra{
    using P = pair<T, ll>;
    const T inf = numeric_limits<T>::max();
    vector<vector<pair<ll,T>>> G;
    vector<ll> beforev;
    vector<T> dist;
    ll N, start;
    priority_queue<P, vector<P>, greater<P>> pq;

    dijkstra(ll n) : N(n) {
        G.resize(n), beforev.assign(n, -1), dist.assign(n, inf);
    }

    void add_edge(ll u, ll v, T cost){
        G[u].emplace_back(v, cost);
    }

    void init(ll s = 0){
        start = s;
        fill(beforev.begin(), beforev.end(), -1), fill(dist.begin(), dist.end(), inf);
        dist[start] = 0, pq.emplace(0, start);
        
        while(!pq.empty()){
            T c; ll from;
            tie(c, from) = pq.top(), pq.pop();
            if (dist[from] < c) continue;
            for(auto& e: G[from]){
                ll to; T cost;
                tie(to, cost) = e;
                if(dist[to]>dist[from]+cost){
                    dist[to] = dist[from] + cost;
                    beforev[to] = from;
                    pq.emplace(dist[to], to);
                }
            }
        }
    }

    vector<ll> get_route(ll goal){
        vector<ll> route;
        ll now = goal;
        while(now!=-1){
            route.emplace_back(now);
            now = beforev[now];
        }
        reverse(route.begin(), route.end());
        return route;
    }
};

int main() {
    init();
    ll N,M;
    cin >> N >> M;
    dijkstra<ll> G(N);

    rep(i, N - 1) G.add_edge(i + 1, i, 0);
    rep(i, M){
        ll l, r, c;
        cin >> l >> r >> c;
        G.add_edge(l - 1, r - 1, c);
    }

    G.init();

    cout << (G.dist[N - 1] == G.inf ? -1 : G.dist[N - 1]) << endl;
}

Measured memory_bytes: 13624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
int f[maxn] , a[maxn] , sz[maxn];
int getf(int x)
{
    return x == f[x] ? x : f[x] = getf(f[x]);
}
void mer (int a , int b)
{
    int fa = getf(a) , fb = getf(b);
    if (fa != fb){
        f[fb] = fa;
        sz[fa] += sz[fb];
        return ;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n , m; cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) f[i] = i , sz[i] = 1;
    for (int i = 1 ; i <= m ; i++){
        int x , y ; cin >> x >> y;
        mer(x , y);
    }
    int maxx = 0;
    for (int i = 1 ; i <= n ; i++)
        if (f[i] == i) maxx = max (maxx , sz[i]);
    cout << maxx << endl;
    return 0;
}


Measured memory_bytes: 5256
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include<vector>
#include<tuple>

using namespace std;
int main(){
  int H,W;
  cin >> H >> W;
  int h,w;
  cin >> h >> w;
  h = H - h;
  w = W - w;

  cout << h*w << endl;

}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main() {
	int a, c,d;
	char b;
	while (1) {
		scanf("%d %c %d", &a, &b, &c);
		if (b == '?') {
			break;
		}
		else if (b == '+') {
			printf("%d\n", d = a + c);
		}
		else if (b == '-') {
			printf("%d\n", d = a - c);
		}
		else if (b == '*') {
			printf("%d\n", d = a*c);

		}
		else if (b == '/') {
			printf("%d\n", d = a / c);
		}
	}
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

int main(){
	int n;
	lint a,b; scanf("%d%lld%lld",&n,&a,&b);
	vector<int> x(n);
	rep(i,n) scanf("%d",&x[i]);

	lint ans=0;
	rep(i,n-1) ans+=min(a*(x[i+1]-x[i]),b);
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 640
n,Y = map(int,input().split())
y2 = Y // 1000
for a in range(n+1):
    y = y2
    rest = y - a * 10
    if rest < 0:break
    for b in range(n+1-a):
        if rest -b * 5 < 0: break
        if n - a - b == rest - b * 5:
            print(a,b,n-a-b);exit()
print(-1,-1,-1)


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

template<int Modulo = MOD> struct Mint {
	Int val;
	constexpr Mint(Int v = 0) noexcept : val(v% Modulo) {
		if (val < 0) v += Modulo;
	}
	constexpr int getmod() { return Modulo; }
	constexpr Mint operator - () const noexcept { return val ? Modulo - val : 0; }
	constexpr Mint operator + (const Mint& r) const noexcept { return Mint(*this) += r; }
	constexpr Mint operator - (const Mint& r) const noexcept { return Mint(*this) -= r; }
	constexpr Mint operator * (const Mint& r) const noexcept { return Mint(*this) *= r; }
	constexpr Mint operator / (const Mint& r) const noexcept { return Mint(*this) /= r; }
	constexpr Mint& operator += (const Mint& r) noexcept {
		val += r.val;
		if (val >= Modulo) val -= Modulo;
		return *this;
	}
	constexpr Mint& operator -= (const Mint& r) noexcept {
		val -= r.val;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr Mint& operator *= (const Mint& r) noexcept {
		val = val * r.val % Modulo;
		return *this;
	}
	constexpr Mint& operator /= (const Mint& r) noexcept {
		Int a = r.val, b = Modulo, u = 1, v = 0;
		while (b) {
			Int t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = val * u % Modulo;
		if (val < 0) val += Modulo;
		return *this;
	}
	constexpr bool operator == (const Mint& r) const noexcept {
		return this->val == r.val;
	}
	constexpr bool operator != (const Mint& r) const noexcept {
		return this->val != r.val;
	}
	friend ostream& operator << (ostream& os, const Mint<Modulo>& x) noexcept {
		return os << x.val;
	}
	friend istream& operator >> (istream& is, Mint<Modulo>& x) noexcept {
		Int tmp; is >> tmp;
		x = Mint<Modulo>(tmp);
		return is;
	}
	friend constexpr Mint<Modulo> modpow(const Mint<Modulo>& a, Int n) noexcept {
		Mint res(1), tmp = a;
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};

using mint = Mint<>;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N;
	cin >> N;

	vector<Int> A(N);
	for (Int i = 0; i < N; i++) {
		cin >> A[i];
	}

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

	Int temp = A[0];
	Int cnt = 0;
	Int num = 0;
	vector<Int> card(N);
	for (Int i = 0; i < N; i++) {
		if (A[i] == temp) {
			cnt++;
		}
		if(A[i]!=temp){
			card[num] = cnt;
			temp = A[i];
			num++;
			cnt = 1;
		}
		if (i == N - 1) {
			card[num] = cnt;
		}
	}

	Int diff = 0;
	for (Int i = 0; i <= num; i++) {
		diff += card[i] - 1;
	}

	Int ans;
	if (diff % 2) {
		ans = num;
	}
	else {
		ans = num+1;
	}

	cout << ans << "\n";

}

Measured memory_bytes: 1792
//#pragma GCC optimize "trapv"
//-D_GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define ii pair<int,int>
#define Max 100000+5
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
#define pb push_back
int mod = 1000000007;
int mod1 = 998244353;
vector<int> g[Max];
bool vis[Max];
int d, x, y;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
void ex(int A, int B) {
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else {
        ex(B, A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}


void dfs(int u){

	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(vis[v]!=1)
			dfs(v);
	}
}



int power(int a,int b){
    if(b==1)return a;
    if(a>mod)a%=mod;
    int r=1;
    while(b){
        if(b&1)r=r%mod*a%mod;
        a=a%mod*a%mod;
        b/=2;
    }
    return r;
}
class uf{
    vector<int> v;
    vector<int> sz;
    
    
    public :
    uf(int n){
        v.resize(n+1);
        iota(v.begin()+1,v.end(),1);
        sz.resize(n+1,1);
        //1 to sz
    }
    int root(int b){
        while(v[b]!=b){
            b = v[b];
        }   
        return b;
    }
    void u(int a, int b){
        //combine a and b
        
        int ra=root(a);
        int rb=root(b);
        if(ra==rb)return ;
        if(sz[ra]<sz[rb]){
            v[ra] = v[rb];
            sz[rb]+=sz[ra];
        }else{
            v[rb]=v[ra];
            sz[ra]+=sz[rb];
        }
    }
    bool f(int a,int b){
        //same set
        return (root(a)==root(b));
    }
   
    
};
vector<int> matmul(vector<int> a,vector<int> b){
    vector<int> c(4,0);
    c[0] = (a[0]%mod*b[0]%mod + a[1]%mod*b[2]%mod)%mod;
    c[1] = (a[0]%mod*b[1]%mod + a[1]%mod*b[3]%mod)%mod;
    c[2] = (a[2]%mod*b[0]%mod + a[3]%mod*b[2]%mod)%mod;
    c[3] = (a[2]%mod*b[1]%mod + a[3]%mod*b[3]%mod)%mod;
    return c;
}
vector<int> id={1,0,0,1};

int32_t main(){
	IO
	//freopen("input.txt","r",stdin);
    	//freopen("output.txt","w",stdout);
	int t;
  cin>>t;
    map<string,int> m;
  	for(int i=1;i<=t;i++){
     string s;
      cin>>s;
      m[s]++;
    }
  	printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",m["AC"],m["WA"],m["TLE"],m["RE"]);
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    ll c = A + B;
    if (c % 2 == 1)
        cout << "IMPOSSIBLE" << endl;
    else
        cout << c / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
void get_unique(vector<T>& x) {
    x.erase(unique(x.begin(), x.end()), x.end());
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    string s, t;
    cin >> s >> t;
    int n = sz(s), m = sz(t);
    int ans = INF;
    for (int i = 0; i + m <= n; i++) {
        string x = s.substr(i, m);
        int cnt = 0;
        rep(j, m) cnt += (t[j] != x[j]);
        chmin(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int m = scan.nextInt();
			int[] dis = new int[n-1];
			for(int i = 0;i < n-1;i++){
				dis[i] = scan.nextInt();
			}
			long sum = 0;
			int now = 0;
			for(int i = 0;i < m;i++){
				int a = scan.nextInt();
				if(a > 0){
					for(int j = now;j < now+a;j++){
						sum += dis[j];
					}
				}else{
					for(int j = now-1;j >= now+a;j--){
						sum += dis[j];
					}
				}
				now += a;
			}
			System.out.println((sum>=100000)?sum%100000:sum);
		}
	}
}

Measured memory_bytes: 95516
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;

LL GCD(LL x, LL y){
        LL r=0;
        if( x<y ) swap(x, y);
        r = x % y;
        while(r!=0){
                x = y;
                y = r;
                r = x % y;
        }
        return y;
}

long long A[100002] = {0};

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

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

	if(N == 2){
		cout << max(A[1], A[2]) << endl;
		return 0;
	}

	long long d = A[1];
	vector<int> v;
	v.push_back(1);
	for(int i=2; i<=N; i++){
		long long u = GCD(d, A[i]);
		if(u < d){
			d = u;
			v.push_back(i);
		}
	}
    long long ans = 1;
	for(int k=0; k<v.size(); k++){
		long long d = 1;
		int index = v[k];
		int count = 0;
		for(int i=1; i<=N; i++){
			if(i == index) continue;
			count++;
			if(count == 1){
				d = A[i];
			}
			long long u = GCD(d, A[i]);
			if(count > 1) d = u;
		}
		if(ans < d) ans = d;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = y.pow(y, n);
  Mint pow(Mint a, long long n) const {
    Mint y(1);
    Mint b(a);
    while (n > 0) {
      if (n & 1) y *= b;
      b *= b;
      n >>= 1;
    }
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return pow(a, mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= i;
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

int main(){
  int N;
  std::cin >> N;
  std::vector<int > ans(10004, 0);
  for (int x=1; x<104; x++){
    for (int y=1; y<=104; y++){
      for (int z=1; z<=104; z++){
        int sum = x*x+y*y+z*z+x*y+y*z+z*x;
        if (sum<=10000) ans[sum]++;
      }
    }
  }
  for (int i=1; i<=N; i++){
    printf("%d\n", ans[i]);
  }
  return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include <algorithm>
#include <complex>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(7)<<(x)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace  std;
using ll = long long;
const ll mod = 1e9 + 7;
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int N = 1e5+5;

void solve(){

    vector<int>a(5);
    int cnt;
    for(int i=0;i < 5;i++) {
        cin >> a[i];
        if(a[i]==0)cnt = i+1;
    }
    cout << cnt << '\n';



}
int main() {
    fast;
    solve();


}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;
using LL=long long;


class RSQ {
	const int N = 0, sqrtN = 320;
	int B = 0;
	vector<LL> A, Sum;

	void UpdateSum(int i) {
		int l = i * sqrtN, r = (i + 1) * sqrtN;
		Sum[i] = accumulate(A.begin() + l, A.begin() + r, 0LL);
	}

public:
	RSQ(int _N) :N(_N), B((_N + sqrtN - 1) / sqrtN) {
		A.resize(sqrtN * B);
		Sum.resize(B);
	}
	void add(int i, LL x) {
		A[i] += x;
		UpdateSum(i / sqrtN);
	}
	//[s, t)
	LL get(int s, int t) {
		LL ret = 0;
		for (int i = 0; i < B; i++) {
			//Sum[i]の範囲 [l, r)
			int l = i * sqrtN, r = (i + 1) * sqrtN;

			if (r <= s || t <= l) {
				continue;
			} else if (s <= l && r <= t) {
				ret += Sum[i];
			} else {
				for (int j = max(s, l); j < min(t, r); j++) {
					ret += A[j];
				}
			}
		}
		return ret;
	}
};


int main() {
	int n, q; cin >> n >> q;
	RSQ rmq(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com == 0) {
			rmq.add(x - 1, y);
		} else if (com == 1) {
			cout << rmq.get(x - 1, y) << endl;
		}
	}
}


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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
typedef long long   ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(ll i=x;i<y;i++)
#define frr(i,x,y) for(ll i=x-1;i>=y;i--)
#define inf 1e18+1
const ll mod=998244353;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
VL arr,ans,d,a;
vector<VL> adj;

void dfs(ll v,ll p)
{
    
    int j=lower_bound(ALL(d),a.back())-d.begin();
    PLL tmp={-1,-1};
    if(d[j-1]<a.back()&&a.back()<d[j])
    {
        tmp={j,d[j]};
        d[j]=a.back();
        
    }
    // ll ct=-1;
    // fr(i,0,d.size())
    // {
    //     if(d[i]<inf)
    //     {
    //         ct=i;
    //     }
    // }
    ans[v]=lower_bound(ALL(d),inf)-d.begin()-1;
    for(auto u:adj[v])
    {
        if(u!=p)
        {
            d.pb(inf);
            a.pb(arr[u]);
            dfs(u,v);
            d.pop_back();
            a.pop_back();
        }
    }
    if(tmp.F!=-1)
    {
        d[tmp.F]=tmp.S;
    }
    return;
}
void solve()
{
    ll n;
    cin>>n;
    arr.assign(n,0);
    adj.assign(n,VL());
    ans.assign(n,0);
    fr(i,0,n)
        cin>>arr[i];
    fr(i,0,n-1)
    {
        ll x,y;
        cin>>x>>y;
        x--,y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    //VL d,a;
    d.pb(-inf);
    d.pb(inf);
    a.pb(arr[0]);
    dfs(0,-1);
    d.pop_back();
    a.pop_back();
    fr(i,0,n)
    {
        cout<<ans[i]<<"\n";
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 37552
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int main(){
    int a, p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] As = new int[N];
        for (int i=0; i<N; i++) {
            As[i] = sc.nextInt();
        }

        int[] left = new int[N+1];
        int[] right = new int[N+1];

        for (int i=0; i<N; i++) {
            left[i+1] = gcd(left[i], As[i]);
        }
        for (int i=N-1; i>=0; i--) {
            right[i] = gcd(right[i+1], As[i]);
        }

        int res = 0;
        for (int i=0; i<N; i++) {
            int l = left[i];
            int r = right[i+1];

            if (res < gcd(l, r)) {
                res = gcd(l, r);
            }
        }
        System.out.println(res);
    }
    
    public static int gcd(int a, int b) {
        return b > 0 ? gcd(b, a%b) : a;
    }
}


Measured memory_bytes: 49856
#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

#define REP(i, x, n) for(int i = x, i##_len=(n); i < i##_len; i++)
#define rep(i,n) REP(i,0,n)
#define PRI(p) cout<<(p)<<endl;
//#define DEBUG 3

void run() {
	int w, h, n;
	cin >> w >> h >> n;
	vector<vector<int>> p(4, vector<int>());

	p[0].push_back(0);
	p[1].push_back(w);
	p[2].push_back(0);
	p[3].push_back(h);
	
	rep(i, n) {
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1 || a == 2) {
			p[a-1].push_back(x);
		} else {
			p[a-1].push_back(y);
		}
	}

	int ans = 0;
	// x
	{
		int left = *max_element(p[0].begin(), p[0].end());
		int right = *min_element(p[1].begin(), p[1].end());
		if (left < right) ans = right - left;
	}
	// y
	{
		int down = *max_element(p[2].begin(), p[2].end());
		int up = *min_element(p[3].begin(), p[3].end());
		if (down < up) ans *= (up - down);
		else ans *= 0;
	}

	PRI(ans);
}

int main() {
#ifdef DEBUG
	ifstream in("input.txt");
	cin.rdbuf(in.rdbuf());
	rep(i, DEBUG) {
		cout << "--------------: i=" << i << endl;
		run();
	}
#else
	run();
#endif
	return 0;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count=0

for a in  range(0,A+1):
    for b in range(0,B+1):
        for c in range(0,C+1):
            total = 500*a + 100*b + 50*c
            if total == X:
                count = count+1

print(count)

Measured memory_bytes: 8972
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
 
#define endl '\n'
#define loop(i, m, n) for (ll i = m; i < n; i++)
#define loope(i, m, n) for (ll i = m; i <= n; i++)
#define epool(i, m, n) for (ll i = m; i >= n; i--)
#define mod 1000000007
#define mod2 998244353
#define vi vector<ll>
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define empf emplace_front
#define empb emplace_back
#define ret(x) return cout << x,0;
#define all(v) v.begin(),v.end()
const ll INF=1e18;
const double PI=4*atan(1);

#define SpeedForce                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;

ll mpow(ll base,ll exp);
void solve();
ll POW(ll base,ll exp);
ll gcd(ll a,ll b);

int32_t main(){
    SpeedForce
    ll i = 0,j = 0;

    int t;
    t=1;
    //cin >> t;
    while (t--){
        //cout << fixed << setprecision(10);
        solve();
    }
}

void solve(){
   ll x,n;
   cin >> x >> n;
   ll a[n];
   vector<int> v;
   loop(i,0,n){
       ll a;cin >> a;
       v.pb(a);
   }

    sort(all(v));
    if(find(all(v),x)==v.end()){
        cout << x << endl;
        return;
    }
    ll d=0;
    ll ans=0;
    loope(i,x,101){
        if(find(all(v),i)==v.end()){
            d=i-x;
            ans=i;
            break;
        }
    }

    epool(i,x,0){
        if(find(all(v),i)==v.end()){
            if(x-i<=d){
                ans=i;
            }
            break;
        }
    }

    cout << ans << endl;

}

ll POW(ll base,ll exp){
    ll result = 1;
    while (exp > 0){
        if (exp & 1)
            result = ((ll)result * base);
        base = ((ll)base * base);
        exp >>= 1;
    }
    return result;
}

ll mpow(ll base, ll exp){
    base %= mod;
    ll result = 1;
    while (exp > 0){
        if (exp & 1)
            result = ((ll)result * base) % mod;
        base = ((ll)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

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

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define REP(i, a, b) for (long long i = a; i <= b; ++i)
#define ll long long
using namespace std;

ll n, ans;
string s;

map < string, bool > a;

inline ll read(){
	ll s = 0, w = 1;
	char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) w *= ch == '-' ? -1 : 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
	return s * w;
}

inline void work(){
	n = read();
	REP(i, 1, n) cin >> s, a[s] < 1 ? ans++, a[s] = 1 : ans = ans;
	printf("%lld\n", ans);
}

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

Measured memory_bytes: 19248
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
class UnionFind {
  private:
    vector<int> parent;
    vector<int> height;
    vector<int> m_size;

  public:
    UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
        for(int i = 0; i < size_; ++i)
            parent[i] = i;
    }
    void init(int size_) {
        parent.resize(size_);
        height.resize(size_, 0);
        m_size.resize(size_, 0);
        for(int i = 0; i < size_; ++i)
            parent[i] = i;
    }
    int find(int x) {
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y)
            return;
        int t = size(x) + size(y);
        m_size[x] = m_size[y] = t;
        if(height[x] < height[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(height[x] == height[y])
            ++height[x];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) {
        if(parent[x] == x)
            return m_size[x];
        return size(parent[x] = find(parent[x]));
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> p(N);
    REP(i, N) cin >> p[i];
    vector<int> x(M), y(M);
    REP(i, M) cin >> x[i] >> y[i];
    UnionFind tree(N + 1);
    REP(i, M) tree.unite(x[i], y[i]);
    int cnt = 0;
    REP(i, N) {
        if(tree.same(p[i], i + 1)) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 2560
#include<stdio.h>
#include<string.h>
#include<math.h>
int a,s,d[501],f[501],g[501],h,size[101],ban[101];
int z,x,q;
int main(void)
{
	int i,j;
	while(1){
		scanf("%d %d",&a,&s);
		if(a==0&&s==0) break;
		for(i=0;i<a;i++){
			ban[i]=i;
			size[i]=1;
		}
		for(i=0;i<s;i++) scanf("%d %d %d",&d[i],&f[i],&g[i]);
		for(i=0;i<s-1;i++){
			for(j=i+1;j<s;j++){
				if(g[i]>g[j]){
					h=g[i]; g[i]=g[j]; g[j]=h;
					h=d[i]; d[i]=d[j]; d[j]=h;
					h=f[i]; f[i]=f[j]; f[j]=h;
				}
			}
		}
		q=0;
		for(i=0;i<s;i++){
			//if(d[i]>f[i]) h=d[i]; d[i]=f[i]; f[i]=h;
			z=d[i]; x=f[i];
			while(ban[z]!=z) z=ban[z];
			while(ban[x]!=x) x=ban[x];
			if(z!=x){
				q+=g[i];
				if(size[z]>size[x]) ban[x]=z;
				else ban[z]=x;
			}
		}
		printf("%d\n",q);
	}
	return 0;
}

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

int main() {

        int n, t, a;
        std::cin >> n;
        std::cin >> t >> a;

        std::vector<double> h(n);

        int hi = 0;
        for(auto& ha : h) {
                std::cin >> hi;
                ha = t - hi * 0.006;
        }

        int result = 0;
        double diff = std::abs(a - h[0]);
        for (auto i = 1; i < n; ++i) {
                double d = std::abs(a - h[i]);
                if (diff > d) {
                        diff = d;
                        result = i;
                }
        }
        std::cout << result + 1 << std::endl;
        return 0;
}

Measured memory_bytes: 256
N = int(input())
A, B = [], []
d = float('inf')
ind = -1
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    if a > b:
        if b < d:
            d = b
            ind = i

if d == float('inf'):
    print(0)
else:
    print(sum(A) - B[ind])

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

using namespace std;

#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;

int main(void){

    int n;
    cin >> n;

    int sum_odd = 0, sum_even = 0;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        if(a % 2){
            sum_odd++;
        }else{
            sum_even++;
        }
    }

    if(sum_odd % 2 == 0){
        cout << "YES" << "\n";
    }else{
        cout << "NO" << "\n";
    }

    return 0;
}


Measured memory_bytes: 3568