akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
using namespace std;

void Main() {
    // input
    u_int64_t N;
    cin >> N;
    u_int64_t nums[N+1];
    u_int64_t A[N+1];
    for (u_int64_t i = 0; i <= N; i++) {
        nums[i] = 0;
    }
    
    for (u_int64_t i = 1; i <= N; i++) {
        u_int64_t num_A;
        cin >> num_A;
        nums[num_A]++;
        A[i] = num_A;
    }


    // translate
    u_int64_t comb = 0;
    for (u_int64_t i = 1; i <= N; i++) {
        // cout << "i: " << nums[i] << endl;
        comb += nums[i] * (nums[i] - 1) / 2;
    }


    // output
    for (u_int64_t i = 1; i <= N; i++) {
        cout << comb - nums[A[i]] + 1 << endl;
    }

}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 6684
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#include <functional>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long long llong;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
		cerr << (*i) << " ";
    }
    cerr << "\n";
}
int n;
ll l;
ll t[510000];
ll v[510000];


int bd(pair<ld, ld> a, pair<ld, ld> b) {
    return a.first * b.second - a.second * b.first >= 0;
}

deque<pair<ld, ld> > dq;

int main() {
    scanf("%d%lld", &n, &l);
    for (int i = 0; i < n; ++i)
        scanf("%lld%lld", t + i, v + i);
    pair<ld, ld> md = make_pair(0, 0);
    dq.push_front(md);
    for (int i = 0; i < n; ++i) {
        md.first += v[i];
        md.second += v[i] * t[i];
        pair<ld, ld> pr = dq.back();
        while (!dq.empty() && dq.back().first + md.first >= l) {
            pr = dq.back();
            dq.pop_back();
        }
        pair<ld, ld> pr2 = make_pair(0, 0);
        if (!dq.empty())
            pr2 = dq.back(), pr2.first += md.first, pr2.second += md.second;
        pr.first += md.first;
        pr.second += md.second;
        pr.first -= pr2.first;
        pr.second -= pr2.second;
        ld hv = l - pr2.first;
        ld k = hv / pr.first;
        pr = make_pair(pr2.first + pr.first * k, pr2.second + pr.second * k);
        printf("%.10Lf\n", pr.second / pr.first);
        pr.first -= md.first;
        pr.second -= md.second;
        dq.push_back(pr);
        while (dq.size() >= 2 && bd(make_pair(dq[0].first + md.first, dq[0].second + md.second), make_pair(dq[1].first + md.first, dq[1].second + md.second)))
            dq.pop_front();
        dq.push_front(make_pair(-md.first, -md.second));
    }
	return 0;
}




Measured memory_bytes: 34748
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <set>


int main()
{
	std::string s;
	std::cin >> s;
	char s1, s2 = '1';
	std::set<char> st;
	std::string result;
	for(int i = 0; i < 4; i++) {
		st.insert(s[i]);
	}
	if (st.size() != 2) {
		result = "No";
	}
	else if(std::count(s.cbegin(),s.cend(),s[0])==2){
		result = "Yes";
	}
	else {
		result = "No";
	}
	std::cout << result;
	std::cin >>s;
    return 0;
}



Measured memory_bytes: 256
N = 104743
p = [1]*(N + 1)
for i in range(4, N + 1, 2): p[i] = 0
a = [2]
for i in range(3, N + 1, 2):
    if p[i] == 1:
        a.append(a[-1] + i)
        for j in range(3*i, N + 1, 2*i): p[j] = 0

while True:
    n = int(input())
    if n == 0: break
    print(a[n - 1])

Measured memory_bytes: 7764
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n, d; std::cin >> n >> d;
    std::cout << (n + 2*d) / (2*d + 1) << std::endl;
    return 0;
}


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

public class Main {
	private static void solve(){
		//Implement solution here.
		System.out.println(ni() >= 30 ? "Yes" : "No");
	}


	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		boolean hasNext = true;
		while(hasNext){
			solve();	
			try{
				br.mark(1);
				if(br.read() > 0){
					br.reset();			
					System.out.println("---");
				} else {
					hasNext = false;
				}
			}catch(Exception e){
				throw new RuntimeException(e);
			} 
		}
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 25428
#include <iostream>
#include <vector>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll MOD = 1000000007;
const ll INF = 1LL << 60;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll money = 1000;
    ll kabu = 0;
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i > 0)
        {
            ll store = 0;
            if (a[i] > a[i - 1])
            {
                store = money / a[i - 1];
            }
            money += (a[i] - a[i - 1]) * store;
        }
    }
    cout << money << endl;
}

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

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

    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    int ans = 0;
    rep(i, n) if ((k | a[i]) == k) ans += b[i];
    for (int bit = 31; bit >= 0; bit--)
    {
        if (!(k & (1 << bit)))
            continue;
        int sum = 0, num = k - (1 << bit);
        for (int i = bit - 1; i >= 0; i--)
            num |= (1 << i);
        rep(i, n) if ((num | a[i]) == num) sum += b[i];
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1920
#include<stdio.h>
#include<stdlib.h>
long int a[200000];
long int arai;
long int sunu;
long int ans;
long int temp;
int main(void){
    int n,i;
    arai=0;
    sunu=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%ld",&a[i]);
        if(i!=0){
            arai+=a[i];
        }
    }
    sunu=a[0];
    ans=labs(arai-sunu);
    for(i=1;i<n-1;i++){
        arai-=a[i];
        sunu+=a[i];
        temp=labs(arai-sunu);
        if(ans>temp){
            ans=temp;
        }
    }
    printf("%ld\n",ans);
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
const double PI=3.14159265358979323846;
const long long INF = 1LL << 60;

int main() {
	string S, T;
	cin >> S >> T;
	if (S.size()+1 != T.size()) {
		std::cout << "No" << '\n';
		return 0;
	}
	string x = T.substr(0, S.size());
	if (S != x) {
		std::cout << "No" << '\n';
		return 0;
	}
	std::cout << "Yes" << '\n';
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

    int n;
    cin >> n;
    vi a(n+1);
    vi b(n+1);
    vi c(n);
    rep1(i,n+1){
        cin >> a[i];
    }
    rep1(i,n+1){
        cin >> b[i];
    }
    rep1(i,n){
        cin >> c[i];
    }
    int ans = 0;
    rep1(i,n+1){
        ans += b[a[i]];
        if(a[i]==(a[i-1]+1) && (i-1)!=0){ans += c[a[i-1]];}
    }
    cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stdio.h>
#include<numeric>

using namespace std;


int gcd(int x, int y){
    if (x > y)
        return gcd(y, x);
    
    int m = 1;
    while(m != 0){
        m = y % x;
        y = x;
        x = m;
    }
    return y;
}
int mygcd(int x, int y){
    if (x > y)
        return mygcd(y, x);
    if (x == 0)
        return y;
    return gcd(x, y);
}
int main(){
    int n;
    cin >> n;
    int A[n];
    for (int i = 0; i < n; i++)
        cin >> A[i];

    int L[n+1]; int R[n+1];
    L[0] = 0;
    for (int i = 1; i <= n; i++){
        L[i] = mygcd(L[i - 1], A[i - 1]);
    }

    R[n] = 0;
    for (int i = n - 1; i >= 0; i--){
        R[i] = mygcd(R[i + 1], A[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int newGcd = mygcd(L[i - 1], R[i]);
        ans = max(ans, newGcd);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1408
// Justice will be served
// شهید حاج قاسم سلیمانی
 
#include<bits/stdc++.h>
using namespace std ;
 
int main() {
  int a , b ;
  cin >> a >> b ;
  if (a >= 0 && a <= 5)
    cout << 0 ;
  else if (a >= 6 && a < 13)
    cout << b / 2 ;
  else
    cout << b ;
}


Measured memory_bytes: 256
n=int(input())
s=[input() for i in range(n)]
s.sort()
dic=[0]*n
for i in range(n-1):
  if s[i]==s[i+1]:
    dic[i+1]=dic[i+1]+dic[i]+1
max=max(dic)
for i in range(n):
  if dic[i]==max:
    print(s[i])

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

int main() {
    long long n, x, l, sum = 0, ans = 1;
    cin >> n >> x;
    for(int i = 0; i < n; ++i) {
        cin >> l;
        sum += l;
        if(sum <= x) {
            ans++;
        } else {
            break;
        }
    }
    cout << ans << '\n';
}


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

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N;
    cin >> N;
    cout << N * N * N << endl;
}

Measured memory_bytes: 256
import sys
import math
import itertools 
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

A,B,N=nm()

ans=0
if(N<B):
    print(math.floor(A/B*N))
else:
    print(math.floor(A/B*(B-1)))


Measured memory_bytes: 9096
#include<stdio.h>

int main(void){
  int n , m;
  scanf("%d %d",&n,&m);
  
  int l , r;
  int max = 0 , min = 100001;
  for(int i = 0;i < m;i ++){
    scanf("%d %d",&l,&r);
    if(max < l){
      max = l;
    }
    if(r < min){
      min = r;
    }
  }
  
  if(min < max){
    printf("0\n");
  }
  else{
    printf("%d\n",min - max + 1);
  }
  
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	private static final long MOD = (long)Math.pow(10, 9) + 7;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		sc.close();

		long[][] pascal = new long[N+2][N+2];
		for(int i = 0;i < pascal.length;i++) {
			pascal[i][0] = 1;
		}
		for(int i = 0;i <= N;i++) {
			for(int j = 0;j <= i ;j++) {
				pascal[i+1][j+1] = (pascal[i][j] + pascal[i][j+1])%MOD;
			}
		}


		for(int i = 1;i <= K;i++) {
			long combi1 = pascal[N-K+1][i];
			long combi2 = pascal[K-1][i-1];
			System.out.println(combi1*combi2%MOD);
		}
	}
}

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

int n;
bool ans;
vector<int> b;
void mainDFS(int x,vector<int> &c);

void subSolve(int x,int r,vector<int> &c,int X){
	//?????????
	if( ans ) return;
	
	//???????????§??\?????????
	if( x == n ){
		if( r == 0 ){
			mainDFS(X+1,c);
		}
		return;
	}
	//????????????????????????
	if( c[x] == 0 && b[x] <= r ){
		c[x] = b[x];
		subSolve(x+1,r-b[x],c,X);
		c[x] = 0;
	}
	//???????????????
	subSolve(x+1,r,c,X);
}

void mainDFS(int x,vector<int> &c){
	if( x == n ){ ans = 1; return; }
	//?????????
	if( ans ) return;
	if( c[x] == 0 ){ return; }
	else{
		// ?¬??????????????????????????????¶????????????
		if( x + 1 < n && c[x+1] == 0 ){
			c[x+1] = b[x+1];
			subSolve(x+2,c[x]-b[x+1],c,x);
			c[x+1] = 0;
		}else{
			//???????????????
			mainDFS(x+1,c);
			//??\????????????
			subSolve(x+1,c[x],c,x);
		}		
	}
}
int main(){
	while( cin >> n && n ){
		b = vector<int>(n);
		for(int i = 0 ; i < n ; i++) cin >> b[i];
		sort(b.rbegin(),b.rend());
		vector<int> s(n,0);
		s[0] = b[0];
		ans = 0;
		mainDFS(0,s);
		if(ans) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

Measured memory_bytes: 1192
n = int(input())
a = list(map(int, input().split()))

ans = [""]*n

for i in range(n):
    x = a[i]
    b = ans[a[i] - 1]
    c = str(i+1)
    ans[a[i]-1] = str(i+1)

print(" ".join(ans))

Measured memory_bytes: 20892
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>

using namespace std;
typedef long long ll;

int main(){
  int a,b; cin>>a>>b;
  if(a%2!=0&&b%2!=0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int MOD=1e9+7;
const int INF32=1<<30;
const ll INF64=1LL<<60;

void solve(){
  ll n,d; cin >>n >>d;
  int cnt=0;
  for(int i=0; i<n; i++){
    ll x,y; cin >>x >>y;
    if(x*x+y*y<=d*d) cnt++;
  }
  cout <<cnt;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  solve();
return 0;}

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

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

  int A[n][m];
  int b[m];

  for(int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> A[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }

  int sum = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      sum += A[i][j] * b[j];
    }
    cout << sum << endl;
    sum = 0;
  }


  return 0;
}


Measured memory_bytes: 3156
// abc075_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int A, B, C;
    cin >> A >> B >> C;

    if (A == B){
        print(C);
    } else if (B == C){
        print(A);
    } else {
        print(B);
    }

    return 0;
}


Measured memory_bytes: 256
h, w, k = map(int, input().split())
S = []
for i in range(h):
  W = list(input())
  S.append(W)
Ans = []
#print(Ans)

stack = 0  #h
first_h = -1
flag = True
counter = 0
for i, W in enumerate(S):
  if "#" in W:
    Ans_w = []
    counter += 1
    First_w_flag = False
    
    flag = False
    if first_h == -1:
      first_h = i
      
    for j in range(w):
      if S[i][j] == "." and First_w_flag == False:
        Ans_w.append(counter)
      elif S[i][j] == "#" and First_w_flag == False:
        First_w_flag = True
        Ans_w.append(counter)
      elif S[i][j] == "." and First_w_flag == True:
        Ans_w.append(counter)
      else:
        counter += 1
        Ans_w.append(counter)
    Ans.append(Ans_w)
  elif flag == True:
    stack += 1
  else:
    Ans.append(Ans_w)
for i in range(stack):
  Ans = [Ans[0]] + Ans
for W in Ans:
  print(*W, sep=" ")

Measured memory_bytes: 49116
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        do{
            int res = 0;
            int a = input.nextInt();
            String op = input.next();
            int b = input.nextInt();
            res = calculate(a, op, b);
            if(op.compareTo("?") != 0)
                System.out.println(res);
            else
                break;
        }while(input.hasNext());
    }
    public static int calculate(int a, String op, int b){
        int result = 0;
        switch(op){
            case "+" :
                result = a + b;
                break;
            case "-" :
                result = a - b;
                break;
            case "/" :
                result = a / b;
                break;
            case "*" :
                result = a * b;
                break;
            default :
                break;
        }
        return result;
    }
}


Measured memory_bytes: 26292
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s[] = sc.next().split("");
    String t[] = sc.next().split("");
    Arrays.sort(s);
    Arrays.sort(t, Collections.reverseOrder());
    String ss = String.join("", s);
    String tt = String.join("", t);
    String ans[] = {ss, tt};
    Arrays.sort(ans);
    if (ss.equals(tt)){
      System.out.println("No");
      return;
    }
    System.out.println(ans[0].equals(ss) ? "Yes" : "No");
  }
}


Measured memory_bytes: 35996
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S, Q, K):

    for k in K:
        d = 0
        m = 0
        dm = 0
        ans = 0
        for i in range(N):
            if S[i] == 'D':
                d += 1
            elif S[i] == 'M':
                m += 1
                dm += d
            elif S[i] == 'C':
                ans += dm

            j = i-k+1
            if j < 0:
                continue

            if S[j] == 'D':
                d -= 1
                dm -= m
            elif S[j] == 'M':
                m -= 1
        print(ans)


def main():
    N = read_int()
    S = read_str()
    Q = read_int()
    K = read_int_n()
    (slv(N, S, Q, K))


if __name__ == '__main__':
    main()


Measured memory_bytes: 73124
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int n;
    cin >> n;
    VL p(n), pos(n);
    REP(i,n){
        p[i] = in() - 1;
        pos[p[i]] = i;
    }
    ll ans = 0;
    multiset<ll> st({-1, -1, n, n});
    FORR(i,n-1,0){
        ll x = pos[i];
        auto itr = st.lower_bound(x);
        ll r1 = *itr;
        itr++;
        ll r2 = *itr;
        itr--;
        itr--;
        ll l1 = *itr;
        itr--;
        ll l2 = *itr;
        ll p1 = (r2 - r1) * (x - l1);
        ll p2 = (r1 - x) * (l1 - l2);
        ans += (p1 + p2) * (i + 1);
        st.insert(pos[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define repk(i,m,n) for(ll i=m;i<n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int INF=2*1e9;
map<ll,ll> m;
ll a[200005];
int main()
{
    ll n,ans=0,t;
    cin>>n;
    set<ll> s;
    rep(i,n)
    {
        cin>>a[i];
        m[a[i]]++;
        s.insert(a[i]);
    }
    t=s.size();
    rep(i,t)
    {
        ans+=m[*s.begin()]*(m[*s.begin()]-1)/2;
        s.erase(s.begin());
    }
    rep(i,n)
    {
        cout<<ans-(m[a[i]]-1)<<"\n";
    }
}


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

int N, M;
vector<vector<int>> g;
vector<int> ans;

void Bfs(int si) {
  queue<int> q;
  q.push(si);
  while (!q.empty()) {
    int i = q.front();
    q.pop();
    for (size_t ni = 0; ni < g[i].size(); ++ni) {
      if (ans[g[i][ni]] != -1) {
        continue;
      }
      q.push(g[i][ni]);
      ans[g[i][ni]] = i;
    }
  }
}

int main() {
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; ++i) {
    cin >> A[i] >> B[i];
  }

  g.resize(N + 1);
  for (int i = 0; i < M; ++i) {
    g[A[i]].push_back(B[i]), g[B[i]].push_back(A[i]);
  }

  ans.resize(N + 1, -1);
  Bfs(1);

  if (g[1].size() >= 1) {
    cout << "Yes" << endl;
    for (int i = 2; i <= N; ++i) {
      cout << ans[i] << endl;
    }
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 11732
H, W = map(int, input().split())
S = [0]*(H+1)
S[0] = '*'*(W+1)
for h in range(1,H+1):
    S[h] = '*' + input()

dps = [[0]*(W+1) for _ in range(H+1)]
mod = 10**9+7

def dp(h,w):
    if h==1 and w==1:
        return 1
    if S[h][w]=='.':
        return (dps[h-1][w]+dps[h][w-1])%mod
    return 0


def solve():
    for h in range(1,H+1):
        for w in range(1,W+1):
            dps[h][w] = dp(h,w)
    ans = dps[-1][-1]
    return ans
print(solve()) 

Measured memory_bytes: 52464
#include <cstdio>
#include <vector>
#include <algorithm>

#define all(v) (v).begin(), (v).end()
using namespace std;

int main()
{
    int no_of_cities, start_location;
    scanf("%d %d", &no_of_cities, &start_location);

    vector <int> locations(no_of_cities + 1);
    locations[0] = start_location;
    for(int i = 1; i <= no_of_cities; i++)
        scanf("%d", &locations[i]);

    sort(all(locations));

    vector <int> difference(no_of_cities);
    for(int i = 0; i < no_of_cities; i++)
        difference[i] = locations[i + 1] - locations[i];

    int gcd = difference[0];
    for(int i = 1; i < no_of_cities; i++)
        gcd = __gcd(gcd, difference[i]);

    printf("%d\n", gcd);
    return 0;
}


Measured memory_bytes: 1024
N = int(input())
A_list = list(map(int, input().split()))

A_list_choose = [j for j in A_list if j % 2 == 0]

flag = 0

for i in range(len(A_list_choose)):
    tmp = A_list_choose[i]
    if tmp%3==0 or tmp%5==0:
        continue
    else:
        flag = 1
        break

if flag==0:
    print('APPROVED')
else:
    print('DENIED')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 1e18
#define REPL(i,a,b) for(int i=a;i<a;++i)
#define REPLE(i,a,b) for(int i=a;i<=a;++i)
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;

#define M_PI 3.14159265358979323846

int a[120][2];
const int oo = 1e9+10;
const int mod = 7901;

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

ll memo[100005][100];
int N,W;

ll dp(int i, int c){
	if(i > N-1) return 0;
	if(memo[c][i] != -1)return memo[c][i];
	ll ans = -1;
	if(a[i][0] + c <= W){
		ans = dp(i+1, c+a[i][0])+a[i][1];
	}
	ans = max(ans, dp(i+1, c));
	memo[c][i] = ans;
	return memo[c][i];
}

void solve(){
	cin>>N>>W;
	for(int i = 0 ; i < N; ++i){
		for(int j = 0 ; j < 2 ; ++j){
			cin >> a[i][j];
		}
	}	
	memset(memo, -1, sizeof memo);
	cout << dp(0,0) << '\n';
}
int main(){   
    ios::sync_with_stdio(0);cin.tie(0);
	int t=1;
	while(t--){
		solve();
	}
}  








Measured memory_bytes: 81732
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x>0?x:-(x))
#define INF 1000000000

#define MOD 1000000007

void swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void swap2(double* a, double* b)
{
	double tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int gcd(int a, int b)  //最大公約数
{
	if (a < b)
		swap(&a, &b);

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

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

long power(long x, int n) { //x^n 計算量O(logn)
	long ans = 1;
	while (n > 0) {
		if ((n & 1) == 1) {
			ans = ans * x;
		}
		x = x * x; //一周する度にx, x^2, x^4, x^8となる
		n >>= 1; //桁をずらす n = n >> 1
	}
	return ans;
}

int combination(int n, int r)
{
	if (r == 0 || r == n)
		return (1);
	else if (r == 1)
		return (n);
	return (combination(n - 1, r - 1) + combination(n - 1, r));
}

int keta(int a, int n)
{
	if (n == 1)
		return a % 10;

	for (int i = 0; i < n - 1; i++)
		a /= 10;

	return a % 10;
}

int main()
{
	int N, M, L, K;
	char S[100];

	scanf("%s", S);

	N = strlen(S);

	for (int i = 0; i < (N - 1) / 2; i++)
	{
		if (S[i] != S[(N - 1) / 2 - i-1])
		{
			printf("No");
			return 0;
		}
	}

	

	for (int i = (N+3)/2; i < strlen(S); i++)
	{
		if (S[i] != S[strlen(S)-i-1])
		{
			printf("No");
			return 0;
		}
	}

	for (int i = 0; i < strlen(S); i++)
	{
		if (S[i] != S[strlen(S) - i-1])
		{
			printf("No");
			return 0;
		}
	}

	printf("Yes");
}


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

int main() {
  int N;
  cin >> N;
  int A[N];
  for (int i = 0 ;i < N; i++) cin >> A[i];
  int num[110] = {0};
  for (int i = 0; i < N; i++) {
    num[A[i]]++;
  }
  int ans = 0;
  for (int i = 0; i < 110; i++) {
    if (num[i]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
	int k, s;
	cin >> k >> s;
	long long int res = 0;
	for (int i = 0; i <= k; i++) {
		if (k + k + i < s) continue;
		if (i > s) continue;
		int l = max(s - i - k, 0);
		int h = min(k, s - i);
		if (l > h) continue;
		res += h - l + 1;
	}
	cout << res << endl;
}


Measured memory_bytes: 3544
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

template <typename T1, typename T2>
void func(T1& grid, T2& s, int ni, int nj, ll& cnt_w, ll& cnt_b) {
	if (s[ni][nj] == '.') { ++cnt_w; }
	if (s[ni][nj] == '#') { ++cnt_b; }
	int H = s.size();
	int W = s[0].size();

	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };
	for (int i = 0; i < 4; ++i) {
		int di = ni + dy[i];
		int dj = nj + dx[i];
		if ((di < 0) || (di >= H) || (dj < 0) || (dj >= W)) {
			continue;
		}
		if (s[ni][nj] == '.') {
			if (!grid[di][dj] && (s[di][dj] == '#')) {
				grid[di][dj] = true;
				func(grid, s, di, dj, cnt_w, cnt_b);
			}
		}
		if (s[ni][nj] == '#') {
			if (!grid[di][dj] && (s[di][dj] == '.')) {
				grid[di][dj] = true;
				func(grid, s, di, dj, cnt_w, cnt_b);
			}
		}
	}
}

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> s(H);
	for (int i = 0; i < H; ++i) { cin >> s[i]; }

	ll res = 0;
	vector<vector<bool>> grid(H, vector<bool>(W, false));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if ((s[i][j] == '#') && (!grid[i][j])) {
				grid[i][j] = true;
				ll cnt_w = 0, cnt_b = 0;
				func(grid, s, i, j, cnt_w, cnt_b);
				res += (cnt_w * cnt_b);
			}
		}
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 33024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const LL mod=1e9+7;
int read() {
	char ch=getchar();int x=0,f=1;
	while(ch<'0' || ch>'9')	{if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
	LL res=1;
	while(b) {
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int main() {
//	cout<<"Accepted!\n";
	int n,num[105];
	n=read();
	for(int i=1;i<=n;++i) {
		num[i]=read();
	}
	int minn=1e9+7;
	for(int i=1;i<=100;i++) {
		int sum=0;
		for(int j=1;j<=n;++j) {
			sum=sum+(num[j]-i)*(num[j]-i);
		}
		minn=min(minn,sum);
	}
	cout<<minn;
	return 0;
}


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

int main() {
  int n; cin >> n;
  int a[n];
  for(int i = 0;i < n; i++) {
      cin >> a[i];
  }
  sort(a,a+n);
  double ans = a[0];
  for(int i =1; i < n; i++) {
      ans = (ans + a[i]) / 2.0;
  }
  printf("%.6f", ans);
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC080A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, a, b, x;
            var word = Console.ReadLine().Split(' ');
            n = int.Parse(word[0]);
            a = int.Parse(word[1]);
            b = int.Parse(word[2]);
            if (b < (n * a))
                x = b;
            else
                x = a * n;
            Console.WriteLine(x);
            Console.ReadKey();

        }
    }
}

Measured memory_bytes: 11092
#pragma region include
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstdio>
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define MOD 1000000007
#define INF 1000000000
#define LLINF 4000000000000000000
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#pragma endregion

//#define __DEBUG__
#ifdef  __DEBUG__
#define dump(x) cerr << #x << " = " << (x) << " [" << __LINE__ << ":" << __FUNCTION__ << "] " << endl;
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    REP(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}
// map出力
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "{";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
    os << "{";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr;
        ++itr;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#endif

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, K; cin >> N >> K;
    VI v1(N),v2(N);
    vector<ll> sum(N+1);
    REP(i, N) {
        cin >> v1[i];
        v2[N - 1 - i] = v1[i];
    }
    sum[0] = 0;
    REP(i, N) {
        sum[i + 1] = sum[i] + v1[i];
    }
    ll val = 0;
    ll ans = 0;
    int aaa = max(N, K);
    int bbb = min(N, K);
    for (int a = 0; a <= bbb; a++) {
        for (int b = 0; b <= bbb - a; b++) {
            val = sum[a] - sum[N-b] + sum[N];
            vector<int> vec(aaa,INF);
            REP(i, a) {
                vec[i] = v1[i];
            }
            for (int i = 0; i < b; i++) {
                vec[i+a] = v2[i];
            }
            sort(ALL(vec));
            REP(i, K - a - b) {
                if (vec[i] < 0) {
                    val -= vec[i];
                }
                else {
                    break;
                }
            }
            ans = max(ans, val);
        }
    }
    cout << ans << endl;
    getchar(); getchar();
}

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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    m = n % 10;
    switch(m) {
    case 0:
        cout << "pon" << endl;
        break;
    case 1:
        cout << "pon" << endl;
        break;
    case 2:
        cout << "hon" << endl;
        break;
    case 3:
        cout << "bon" << endl;
        break;
    case 4:
        cout << "hon" << endl;
        break;
    case 5:
        cout << "hon" << endl;
        break;
    case 6:
        cout << "pon" << endl;
        break;
    case 7:
        cout << "hon" << endl;
        break;
    case 8:
        cout << "pon" << endl;
        break;
    case 9:
        cout << "hon" << endl;
        break;
    default:
        break;
    }
    return 0;
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

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

  int n; cin >> n;
  set<int> st;
  for(int i=0;i<n;++i) {
    int tmp; cin >> tmp;
    st.insert(tmp);
  }
  cout << (SZ(st) == n ? "YES" : "NO") << endl;


}


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

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

int main(){
    int W, H, C;
    cin >> W >> H >> C;
    int x = gcd(W, H);
    cout << (W/x)*(H/x)*C << endl;
    
    return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
						
#define fast_cin() ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long
				
int32_t main() {
	fast_cin();  
	int k; cin >> k;
	int num = 0;
	for (int i = 1; i <= k + 1; ++i) {
		num = num * 10 + 7;
		num %= k;
		if (num == 0) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    rep(i, 0, s.size()){
        if(s[i] == 'A'){
            l = i; break;
        }
    }
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == 'Z'){
            r = i; break;
        }
    }
    cout << r - l + 1 << endl;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, M, T;
  cin>>N>>M>>T;

  vector<unordered_map<_int,_int> > cnt(N);
  vector<P> rnk(N, P(0, 0));
  rnk[0] = P(0, -1);
  map<Int, Int> room;

  auto calc =[&](Int a, Int b, Int c){
    if(c == 0){
      Int start1 = room[b];
      Int end1 = a;

      room.erase(b);
      for(auto p:room){
        Int t, start2; tie(t, start2) = p;
        Int score = end1 - max(start1, start2);
        if(b < t){
          cnt[b][t] += score;
          _int val = cnt[b][t];
          Max(rnk[b], P(val, -t));
          Max(rnk[t], P(val, -b));
        }
        else{
          cnt[t][b] += score;
          _int val = cnt[t][b];
          Max(rnk[b], P(val, -t));
          Max(rnk[t], P(val, -b));

        }
      }
    }
    if(c == 1) {
      room[b] = a;
    }
  };


  for(Int i=0;i<M;i++){
    Int a, b, c;
    cin>>a>>b>>c; b--;
    if(a > T) continue;
    calc(a, b, c);
  }

  for(Int i=0;i<N;i++){
    if(!room.count(i)) continue;
    calc(T, i, 0);
  }

  for(auto ans:rnk){
    cout<<-ans.second+1<<endl;
  }





  return 0;
}



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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

int main() {
  int a, b;
  cin >> a >> b;
  if ((a + b) % 2 == 0) {
    cout << (a + b) / 2 << endl;
  } else {
    cout << (a + b) / 2 + 1 << endl;
  }
}


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

using namespace std;

void Solution()
{
    int month;
    int day;
    
    string week[7] = {
        "Wednesday", "Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday"
    };
    
    int mDays[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    while(cin>>month>>day)
    {
        int sum = 0;
        
        if (month == 0)
        {
            break;
        }
        
        for (int i = 0; i < month - 1; i++)
        {
            sum = mDays[i] + sum;
        }
        
        cout<<week[(sum + day) % 7]<<endl;
    }
}

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

Measured memory_bytes: 1200
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>
typedef long long LL;

int main() {
  std::map<char, int> m;
  for (int i = 0; i < 4; ++i) {
    char c; std::cin >> c;
    m[c]++;
  }

  for (auto p : m) {
    if (p.second != 2) {
      std::cout << "No" << std::endl;
      return 0;
    }
  }
  std::cout << "Yes" << std::endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#define REP(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;

signed main() {
	string ss; cin >> ss;
	string ts; cin >> ts;
	int n = ss.size(), m = ts.size();

	int s[n], t[m];
	REP(i, 0, m) t[i] = ts[i] - 'a';
	REP(i, 0, n) s[i] = ss[i] - 'a';
	vector<int> freq[27];
	REP(i, 0, n) freq[s[i]].push_back(i);
	
	REP(i, 0, m) 
		if (freq[t[i]].empty()) {
			cout << -1;
			return 0;
		}

	int prev = -1;
	long long ans = 0;
	REP(i, 0, m) {
		auto it = upper_bound(freq[t[i]].begin(), freq[t[i]].end(), prev);
		if (it != freq[t[i]].end())
			prev = *it;
		else {
			++ans;
			prev = freq[t[i]][0];
		}
	}
	ans *= n;
	ans += prev + 1;
	cout << ans;
}

Measured memory_bytes: 1984
#include <bits/stdc++.h>
#define ll long long
#define sf(n) scanf("%lld",&n)
#define pf(n) printf("%lld\n",n)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define pff(x,y) printf("%lld %lld\n",x,y)
#define REP(I,N) for(I=0;I<N;I++)
#define REPP(I,A,B) for(I=A;I<=B;I++)
#define MS0(X) memset(X,0,sizeof(X))
#define MS1(X) memset(X,-1,sizeof(X))
#define F first
#define S second
#define Mod 1000000007
#define pb push_back
#define RF freopen("riyad.txt","r",stdin)
#define WF freopen("out.txt","w",stdout)
#define YES printf("YES\n")
#define NO printf("NO\n")

using namespace std;

typedef unsigned long long Ull;
typedef pair < int , int > Pii;
typedef pair < ll , ll > Pll;


int main()
{
    //RF;
    //WF;
    ll i,tc,cs=1,n,m,k,cnt=0,j,q;
    cin>>n;
    double res;
    res = (double)n / 3.0;
    res = pow(res,3.0);
    printf("%0.9lf\n",res);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <numeric>
#include <vector>

using namespace std;
using ll = long long;

int main()
{
    int n;
    vector<ll> a;

    cin >> n;

    a.resize(n);

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

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

    ll l = a[n - 1];
    ll r = a[0];

    ll m = l / 2;

    for (int i = 0; i < n - 1; i++)
    {
        if(a[i] > m)
        {
            if(abs(a[i] - m) <= abs(r - m))
            {
                r = a[i];
            }
            break;
        }
        else
        {
            r = a[i];
        }
    }

    cout << l << " " << r << endl;

    return 0;
}

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

int main() {
    int N, X, D=0, j=2, count=1;
    cin >> N >> X;
    vector<int> L(N+1);
    for(int i=1; i<N+1; i++) {
        cin >> L[i];
    }

    while(D+L[j-1] <= X && j<N+2) {
        D += L[j-1];
        count++;
        j++;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
C = str(input())

ans = 0

rgt = 0
lft = N-1

while(rgt < lft):
    if C[rgt] == "W" and C[lft] == "R":
        ans += 1
        rgt += 1
        lft -= 1


    
    else:
        if C[rgt] == "R":
            rgt += 1
        if C[lft] == "W":
            lft -= 1
print(ans)


Measured memory_bytes: 9428
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int main(){
	vector<int>A(3);
	cin>>A[0]>>A[1]>>A[2];
	sort(A.begin(),A.end());
	cout<<A[2]-A[0]<<endl;
	return 0;
}

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

int main() {
  int N,Z,W,i,r;
  cin >> N >> Z >> W;
  vector<int> a(N);
  for(i=0; i<N; i++)
    cin >> a.at(i);
  if(N==1)
    r = abs(a.at(0)-W);
  else
    r = max(abs(a.at(N-1)-W), abs(a.at(N-2)-a.at(N-1)));
  cout << r << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
LL n,a,b;
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>a>>b;
  cout<<n/(a+b)*a+min(a,(n%(a+b)))<<'\n';

  return 0;
}

Measured memory_bytes: 256