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

void sort(int m[]);

int main(void){
	int i,n,m[3];
	char s[128];

	sscanf(fgets(s,sizeof(s),stdin),"%d",&n);

	for(i=0;i<n;i++){
		fgets(s,sizeof(s),stdin);
		sscanf(s,"%d %d %d",m,m+1,m+2);

		sort(m);

		if(pow(m[0],2) == pow(m[1],2) + pow(m[2],2)){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
	return(0);
}

void sort(int m[]){

	int i,j,t;

	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(m[i]>m[j]){
				t = m[i];
				m[i] = m[j];
				m[j] = t;
			}
		}
	}
}

Measured memory_bytes: 0
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main (){
	int a1,a2,a3,a4,b;
	while(~scanf("%d",&b)){
		a1 = b / 1000;
		a2 = (b - 1000*a1) / 100;
		a3 = (b - 1000*a1 - 100 * a2) / 10;
		a4 = b % 10;
		if((a1 + a2 + a3 + a4) == 7 ){
			printf("%d+%d+%d+%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 + a2 + a3 - a4) == 7 ){
			printf("%d+%d+%d-%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 + a2 - a3 + a4) == 7 ){
			printf("%d+%d-%d+%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 + a2 - a3 - a4) == 7 ){
			printf("%d+%d-%d-%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 - a2 + a3 + a4) == 7 ){
			printf("%d-%d+%d+%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 - a2 + a3 - a4) == 7 ){
			printf("%d-%d+%d-%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 - a2 - a3 + a4) == 7 ){
			printf("%d-%d-%d+%d=7\n",a1,a2,a3,a4);
			return 0;
		}
		if((a1 - a2 - a3 - a4) == 7 ){
			printf("%d-%d-%d-%d=7\n",a1,a2,a3,a4);
			return 0;
		}
	}
	return 0;
}
		

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF 1e18
#define dump(x) cerr<<#x<<"="<<x<<endl
#define int long long

using ll = long long;
const ll mod = LLONG_MAX;

int K,N;
int a[51];
signed main(){
  cin>>K>>N;
  rep(i,K){
    cin>>a[i];
  }
  sort(a,a+K);
  reverse(a,a+K);
  int ans=0;
  for(int i=0;i<N;i++){
    ans+=a[i];
  }
  cout<<ans<<endl;
}


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

using namespace std;
#define ll long long int
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"

int32_t main()
{
   IOS;
    string s;
    ll n,k,i,flag=0;
    cin>>s;
    for(i=0;i<s.size()-1;i++)
    {
        if(s[i]==s[i+1])
        {
            flag+=1;
            break;
        }
    }
    if(flag)
    {
        cout<<"Bad";
    }
    else
    {
        cout<<"Good";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    ll n,k;
    cin>>n>>k;
    k--;
    vector<ll> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }

    ll ans=1000000000;
    for(int i=0;i<n-k;i++){
        ll dif=min(abs(x[i+k]),abs(x[i]))+abs(x[i+k]-x[i]);
        if(ans>dif){
            ans=dif;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    string s,t;
    cin >> s >> t;
    for(int i=0;i<s.size();i++){
        s.insert(s.begin(),s.back());
        s.pop_back();
        if(s==t){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

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

using namespace std;

int main(){
  int n,l;
  string s[100];
  cin>>n>>l;
  for(int i = 0;i<n;i++){
    cin>>s[i];
  }
  sort(s,s+n);
  for(int i = 0;i<n;i++){
    cout<<s[i];
  }
  cout<<endl;
  

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=51,INF=1<<30;

int main(){
    
    int N;cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++) cin>>A[i];
    
    int left=0,right=INF;
    
    while(right-left>1){
        int mid=(left+right)/2;
        bool ok=true;
        
        vector<pair<int,int>> S;
        S.push_back({1,A[0]});
        for(int i=1;i<N;i++){
            if(A[i-1]<A[i]){
                auto p=S.back();
                if(p.first==1){
                    S.pop_back();
                    S.push_back({1,p.second+A[i]-A[i-1]});
                }else S.push_back({1,A[i]-A[i-1]});
            }else{
                int sum=A[i-1];
                while(S.size()&&sum-S.back().second>=A[i]){
                    sum-=S.back().second;
                    S.pop_back();
                }
                
                while(S.size()&&S.back().first==mid){
                    sum-=S.back().second;
                    S.pop_back();
                }
                
                if(S.size()==0){
                    ok=false;
                    break;
                }
                
                if(sum>A[i]){
                    auto p=S.back();
                    sum-=S.back().second;
                    S.pop_back();
                    
                    if(A[i]-1-sum>0){
                        S.push_back({p.first,A[i]-1-sum});
                        sum+=A[i]-1-sum;
                    }
                    
                    S.push_back({p.first+1,1});
                    sum++;
                    
                    if(sum<A[i]) S.push_back({1,A[i]-sum});
                    
                    sum=A[i];
                }else{
                    auto p=S.back();
                    sum-=S.back().second;
                    S.pop_back();
                    
                    if(p.second>1){
                        S.push_back({p.first,p.second-1});
                        sum+=p.second-1;
                    }
                    
                    S.push_back({p.first+1,1});
                    sum++;
                    
                    if(sum<A[i]) S.push_back({1,A[i]-sum});
                }
                
            }
        }
        
        if(ok) right=mid;
        else left=mid;
    }
    
    cout<<right<<endl;
}



Measured memory_bytes: 1024
n = int(input())
pp = list(map(int,input().split()))
three = [pp[0],pp[1],pp[2]]
cou = 0
th = 0

for i in range(n-2):
    three[0] = pp[i]
    three[1] = pp[i+1]
    three[2] = pp[i+2]
    th = three[1]
    three.sort()
    if three[1] == th:
        cou += 1
   
print(cou)


Measured memory_bytes: 3064
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = set(table)
    return table

# file read
a, b, c = map(int, input().split())

elm = sorted(list(divisor(a) & divisor(b)), reverse = True)
print(elm[c-1])

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

using namespace std;

int main()
{
    long long N, K;
    double probability = 0;
    cin >> N >> K;
    long long hoge = 0;
    long long fuga = int(log2(K)) + 1;
    for (int i = 1; i <= N; i++) {
        //probability += pow(0.5, (int(log2(K / i)) + 1));
        //hoge += pow(2, (int(log2(K)) + 1) - (int(log2(K / i)) + 1));
        int k = i;
        int cnt = 0;
        while (true) {
            if (k >= K) {
                hoge += pow(2, fuga - cnt);
                break;
            }
            k *= 2;
            cnt++;
        }
    }
    probability = double(hoge) / (pow(2, fuga) * N);
    cout << setprecision(12) << probability << endl;
}

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

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

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

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
int C[10011];
VI G[10011];
int par[10011];
int ans[10011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }
    REP (i, N) scanf("%d", C+i);
    sort(C, C+N);
    LL sum = 0;
    REP (i, N-1) sum += C[i];

    VI ord; ord.reserve(N);
    ord.push_back(0);
    REP (i, N) {
	int v = ord[i];
	EACH (e, G[v]) if (*e != par[v]) {
	    par[*e] = v;
	    ord.push_back(*e);
	}
    }

    REP (i, N) ans[ord[i]] = C[N-1-i];
    printf("%lld\n", sum);
    rprintf("%d", ans, ans+N);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 1024
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut ab = buf.trim()
        .split_whitespace()
        .map(|c| c.parse::<f32>().unwrap());
    let mut avl = (ab.next().unwrap() + ab.next().unwrap()) / 2.0 + 0.9;
    let mut avl = avl as u32;
    println!("{}", avl);
}


Measured memory_bytes: 4352
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define chmin(x,y) x = min(x, y)
#define chmax(x,y) x = max(x, y)
#define V vector
vector<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
vector<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

int main () {
    int n; cin >> n;
    ll d; cin >> d;
    int ans = 0;
    rep(i, n) {
        ll x, y; cin >> x >> y;
        if (x*x + y*y <= d*d) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int main(){
  ll n,m,ans;
  cin >> n >> m;
  
  if (2*n >= m) {cout<<m/2; return 0;}
  
  ll l = 0,r = m/2;
  while (l < r){
        ll mid = (l + r)/2;
        ll N = mid,M = mid*2,t = 0;
        if (N > n) t = N - n;
        
        if (m >= M + t*2) {ans = mid; l = mid + 1;}
        else {r = mid - 1;}
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <cstdio>
#include <math.h>
#include <utility>
#include <list>
#include <functional>
using namespace std;

#define ll long long
#define vecint vector<int>
#define Pii pair<int, int>

#define REP(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define print(a) cout << a << endl

#define MOD 1000000007
#define NIL -1

ll a[100000];
int n;


void solve1(){
  ll ans1=0;
  ll sum0=a[0];
  ll sum1;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans1+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans1++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }

  ll ans2=0;
  sum0=-1*a[0]/abs(a[0]);
  ans2+=abs(a[0])+1;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans2+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans2++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }

  print(min(ans1,ans2));
  return;
}

void solve2(){
  ll ans1=0;
  ll sum0;
  ll sum1;
  ll ans2=0;
  ll ans;
  a[0]=1;
  sum0=a[0];
  ans1++;
  ans2++;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans1+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans1++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }
  sum0=-1*a[0]/abs(a[0]);
  ans2+=abs(a[0])+1;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans2+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans2++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }
  ans=min(ans1,ans2);
  ans1=0;ans2=0;


  a[0]=-1;
  sum0=a[0];
  ans1++;
  ans2++;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans1+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans1++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }
  sum0=-1*a[0]/abs(a[0]);
  ans2+=abs(a[0])+1;
  REP(i,1,n){
    sum1=sum0+a[i];
    if(sum1*sum0<0){
    }else if(sum1*sum0>0){
      ans2+=abs(sum1)+1;
      sum1=-1*sum0/abs(sum0);
    }else{
      ans2++;
      sum1=-1*sum0/abs(sum0);
    }
    sum0=sum1;
  }
  ans=min(ans,min(ans1,ans2));

  print(ans);
  return;
}

int main(){
  cin>>n;
  rep(i,n){
    cin>>a[i];
  }
  if(a[0]!=0)solve1();
  else solve2();
  return 0;
}


Measured memory_bytes: 1024
import sys
input = sys.stdin.readline


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


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetReverse():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[::-1]):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(len(S) - 1 - i)
        last = i
    return reversed(ret)


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    reverse_ans = GetReverse()

    return sorted(list(set(base_ans) & set(reverse_ans)))


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a + 1)


Measured memory_bytes: 50208
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main(){
    int K;
    cin >> K;
    int cnt = 0;
    int kake = 1;
    for(int i = 1; i <= 1000000; i++) {
        cnt = cnt+7*kake;
        cnt %= K;
        if(cnt == 0) {
            cout << i << endl;
            return 0;
        }
        kake *= 10;
        kake %= K;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 3616
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	m := getNextInt(scanner)

	xx := make([]int64, n)
	yy := make([]int64, m)
	for i := 0; i < n; i++ {
		xx[i] = getNextInt64(scanner)
	}
	var xs, ys int64
	xc := make([]int64, n-1)
	mod := int64(1e9 + 7)
	for i := 0; i < n-1; i++ {
		xc[i] = int64(i+1) * int64(n-1-i)
		xs = (xs + ((xx[i+1]-xx[i])*xc[i])%mod) % mod
	}
	for i := 0; i < m; i++ {
		yy[i] = getNextInt64(scanner)
	}
	yc := make([]int64, m-1)
	for i := 0; i < m-1; i++ {
		yc[i] = int64(i+1) * int64(m-1-i)
		ys = (ys + ((((yy[i+1]-yy[i])*yc[i])%mod)*xs)%mod) % mod
	}

	fmt.Fprintln(writer, ys)
	writer.Flush()
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    lint A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << min(A, B) + min(C, D)<< "\n";
}

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

#define int long long
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 Monoid> struct SegmentTree{
    using Func = function<Monoid(Monoid, Monoid)>;

    int size;
    vector<Monoid> seg;
    const Func merge;
    const Monoid def;

    SegmentTree(int n, Monoid d, const Func f): merge(f), def(d){
        for(size = 1; size <= n; size <<= 1);
        seg.assign(size*2, def);
    }

    Monoid& operator[] (int i) { return seg[i+size]; };
    void build(){ for(int i = size-1;i >= 0;i--) seg[i] = merge(seg[i*2], seg[i*2+1]); } 

    void update(int i, Monoid val){
        seg[i += size] = val;
        while(i >>= 1) seg[i] = merge(seg[i*2], seg[i*2+1]);
    }

    void add(int i, Monoid val){ update(i, val+seg[i+size]); }

    Monoid get(int a, int b){
        Monoid l = def, r = def;
        for(a += size, b += size; a < b; a >>= 1, b >>= 1){
            if(a & 1) l = merge(l, seg[a++]);
            if(b & 1) r = merge(seg[--b], r);
        }
        return merge(l, r);
    }
};

typedef pair<int, int> P;

int get(P num, int x){
	return num.second + (x-num.first); 
}

int a[200010], b[200010];
P np = {-1, -1};

P mer(P a, P b){
	if(a == np) return b;
	if(b == np) return a;
	int c = max(a.first, b.first);
	return get(a, c) < get(b, c) ? a : b;
}

signed main(){
	int h, w;
	cin >> h >> w;


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

	SegmentTree<P> seg(w+1, np, mer);
	set<int> st;
	for(int i = 0;i < w;i++){
		st.insert(i);
		seg.update(i, {0, 0});
	}
	
	for(int i = 0;i < h;i++){
		P now = seg[b[i]];

		auto l = st.lower_bound(a[i]);
		auto r = st.lower_bound(b[i]);
		while(l != r){
			int j = *l;
			P x = seg[j];
			if(x != np){
				x.second += (i+1-x.first) + b[i]-j;
				x.first = i+1;
				now = mer(now, x);
			}
			seg.update(j, np);
			auto old = l;
			l++;
			st.erase(old);
		}
		st.insert(b[i]);
		seg.update(b[i], now);
		auto ans = seg.get(0, w);
		if(ans == np){
			cout << -1 <<endl;
		}else{
			cout << get(ans, i+1) << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 23792
#include<stdio.h>

#define MAX 500000

int count = 0;

void Merge(int a[],int left,int mid,int right);
void MergeSort(int a[],int left,int right);

int main(){
  int a[MAX],n,i;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    scanf("%d",&a[i]);
  }

  MergeSort(a,0,n);

  for(i = 0; i < n; i++){

    if(i == n-1){
      printf("%d\n",a[i]);
      printf("%d\n",count);
      break;
    }
    printf("%d ",a[i]);
  }

  return 0;
}



void Merge(int a[],int left,int mid,int right){

  int n1 = mid-left, n2 = right-mid, l[n1],r[n2],i,j,k;


  for(i = 0; i < n1; i++){
    l[i] = a[left+i];
  }

  for(i = 0; i < n2; i++){
    r[i] = a[mid+i];
  }

  l[n1] = 1000000000;
  r[n2] = 1000000000;

  i = 0;
  j = 0;

  for(k = left; k < right ;k++){
    if(l[i] <= r[j]){
      a[k] = l[i];
      i++;
      count++;
    }

    else{
      a[k] = r[j];
      j++;
      count++;
    }

  }
}



void MergeSort(int a[],int left,int right){

  int mid;

  
  if(left+1 < right){
    mid = (left+right)/2;
    MergeSort(a,left,mid);
    MergeSort(a,mid,right);
    Merge(a,left,mid,right);
  }

}



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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ZERO(a) memset(a,0,sizeof(a))

int box[100001];
bool p[100001];

int main() {
    int n,m; scanf("%d%d",&n,&m);
    ZERO(p);
    FOR(i,1,n+1) box[i] = 1;
    p[1] = true;

    rep(i,m) {
        int x,y; scanf("%d%d",&x,&y);
        if(p[x]) p[y] = true;
        if(box[x] == 1) p[x] = false;
        box[x]--; box[y]++;
    }

    int ans=0;
    FOR(i,1,n+1) ans += p[i];
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <string>

using namespace std;

int main(){
	string x;
	int N,count[4]={0};
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> x;
		if(x == "AC")
			count[0]++;
		else if(x == "WA")
			count[1]++;
		else if(x == "TLE")
			count[2]++;
		else
			count[3]++;
	}

	cout << "AC x " << count[0] << endl;
	cout << "WA x " << count[1] << endl;
	cout << "TLE x " << count[2] << endl;
	cout << "RE x " << count[3] << endl;

	
	return 0;
}


Measured memory_bytes: 3632
N = int(input())


Z = 'abcdefghijklmn'
def solve(N):
    if N == 1:
        return [(1, "a")]
    result = []
    for n, s in solve(N-1):
        for i in range(n+1):
            result.append((max(n, i+1), s+Z[i]))
    return result

for s in sorted(s for i, s in solve(N)):
    print(s)


Measured memory_bytes: 21592
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for _ in range(N)]

dp = [[0] * (W+1) for i in range(N+1)]
# for w, v in L:
for i in range(1, W+1):
    for j in range(1, N+1):
        w = L[j-1][0]
        v = L[j-1][1]
        if i - w >= 0: 
            dp[j][i] = max(dp[j-1][i-w] + v, dp[j][i])
        dp[j][i] = max(dp[j][i], dp[j-1][i])

print(dp[N][W])




Measured memory_bytes: 124124
#include <stdio.h>

int main(void)
{
    int tester[4] = {0}, in[4] = {0}, i, flag = 0;

    for (i = 0; i <= 3 && flag == 0; i++)
    {
        scanf("%d", &in[i]);

        switch (in[i])
        {
        case 1:
            if (tester[0] == 1)
            {
                flag = 1;
            }
            tester[0] = 1;
            break;

        case 9:
            if (tester[1] == 1)
            {
                flag = 1;
            }
            tester[1] = 1;
            break;

        case 7:
            if (tester[2] == 1)
            {
                flag = 1;
            }
            tester[2] = 1;
            break;

        case 4:
            if (tester[3] == 1)
            {
                flag = 1;
            }
            tester[3] = 1;
            break;

        default:
            flag = 1;
            break;
        }
    }

    if (flag)
    {
        printf("NO\n");
    }
    else
    {
        printf("YES\n");
    }
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

#define FOR(idx, begin, end) for(int idx = (begin); idx < (end); ++idx)
#define DBG(x) cerr << #x << ": " << x << "\n"

using namespace std;
typedef long long lint;
const int MOD = 1000000007;

int main() {

	cin.tie(0);

	int A[3];
	cin >> A[0]>> A[1] >> A[2];

	sort(A, A + 3);

	if (A[0] == 5 and A[1] == 5 and A[2] == 7) cout << "YES";
	else cout << "NO";

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
int r, g, b, n;
long long int ans;
void dfs(int, bool);

int main(void){
	scanf("%d%d%d%d", &r, &g, &b, &n);
	dfs(0, false);
	printf("%lld\n", ans);
		
	return(0);
}

void dfs(int cur, bool isG){
	if((cur==n)||((!((n-cur)%b))&&(n-cur>0))){++ans;}
	if(cur>=n){return;}	
	if(!isG){dfs(cur+r, false);}
	dfs(cur+g, true);
}

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

using namespace std;

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

int n;
vector<int> a;
int ans;

void dfs(int d, vector<int> &v){
	if(d == n){
		ll x = 1;
		rep(i, n){
			x *= (a[i] + v[i] - 1);
		}

		if(x % 2 == 0) ans++;
		return;
	}

	for(int i = 0; i < 3; i++){
		v.push_back(i);
		dfs(d+1, v);
		v.pop_back();
	}
}

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

	cin >> n;
	ans = 0;

	a.resize(n);
	rep(i, n) cin >> a[i];
	
	vector<int> v;
	dfs(0, v);
	cout << ans << endl;
}


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

using namespace std;

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

int main(){
    int i;
    //入力
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t; 
    //処理
    //出力
    for(i=0;i<n;i++){
       cout<<s[i];
       cout<<t[i];
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;
string S, T;
bool checked(int i, int sl, int tl){
    bool flg = true;
    rep(j,i,i + tl){
        if(S[j] != T[j - i] && S[j] != '?'){
            flg = false;
        }
    }
    return flg;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> S >> T;
    int sl = S.size();
    int tl = T.size();
    if(tl > sl){
        print("UNRESTORABLE");
        return 0;
    }
    string ans = "";
    rep(i,0,sl - tl + 1){
        if(checked(i, sl, tl)){
            string tt = "";
            rep(j,0,sl){
                if(j < i || j >= i + tl){
                    tt += S[j];
                }else{
                    tt += T[j - i];
                }
                
            }
            string tt2 = "";
            rep(j,0,sl){
                if(tt[j] == '?'){
                    tt2 += 'a';
                }else{
                    tt2 += tt[j];
                }
            }
            if(ans == ""){
                ans = tt2;
            }else if(strcmp(ans.c_str(), tt.c_str()) > 0){
                ans = tt2;

            }
        }
        

    }
    if(ans == ""){
        print("UNRESTORABLE");
    }else{
        print(ans);
    }

}


Measured memory_bytes: 256
N = gets.to_i
S = gets.chomp.chars
Q = gets.to_i
qu = []
Q.times{
  qu << gets.chomp.split(" ")
}

s = Hash.new{|h, k| h[k] = []}
(0...N).each{|i|
  s[S[i]] << (i+1)
}

qu.each{|f, a, b|
  if f == '1' then
    a_i = a.to_i
    if S[a_i-1] != b then
      idx = s[S[a_i-1]].bsearch_index{|x| x >= a_i}
      s[S[a_i-1]].delete_at(idx)
      S[a_i-1] = b
      idx = s[b].bsearch_index{|x| x >= a_i}
      idx.nil? ? s[b] << a_i : s[b].insert(idx, a_i)
    end
  else
    l, r = [a.to_i, b.to_i]
    ans = 0
    (0..25).each{|i|
      sl = s[(97+i).chr].bsearch{|x| x >= l}
      ans += 1 if (not sl.nil?) && sl <= r
    }
    puts ans
  end
}


Measured memory_bytes: 53564
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
// const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,x,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);
 
using Edge = tuple<int, string>;

const string inf = "#";
 
int n, start, goal;

// to, cost
using Edge = tuple<int, string>;
vector<vector<Edge>> edge;
 
vector<string> dist;
 
bool bellman_ford(){
    dist = vector<string>(n, inf);
    dist[start] = "";

    rep(loop, 7 * n){
        rep(v, n) for(auto & e : edge[v]){
            if(dist[v] == inf) continue;

            int nv; string cost;
            tie(nv, cost) = e;

            if(dist[nv] == inf or dist[nv] > cost + dist[v]){
                dist[nv] = cost + dist[v];
                if(nv == goal and loop >= n) return true;
            }
        }
    }

    return false;
}
 
int main(void){
    for(int m; cin >> n >> m >> goal >> start, n;){
        edge = vector<vector<Edge>>(n);

        rep(loop, m){
            int a, b; string label;
            cin >> a >> b >> label;

            edge[b].push_back(tie(a, label));
        }

        if(bellman_ford()){
            cout << "NO" << endl;
        }
        else{
            cout << (dist[goal] != inf ? dist[goal]:"NO") << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3564
# coding: utf-8
# Your code here!
S = input()

flag = True
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "L":
            flag = False
    if i % 2 == 1:
        if S[i] == "R":
            flag = False

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38256
#include<iostream>
#include<string>
#include<set>
using namespace std;

int main() {
	int n, ans=0, len, glen; bool f;
	string s, gs; set<int> fidx, sidx;
	cin >> n >> s;
	len = (signed)s.length();
	for(int i=0; i<n; ++i) {
		cin >> gs;
		glen = (signed)gs.length();
		if(glen==1) {
			if(gs.find(s[0], 0)!=string::npos) ans++;
		}else {
			f = false;
			fidx.clear(); sidx.clear();

			// find first character or second character of s in gs
			for(int j=0; j<glen; ++j) if(gs[j]==s[0]) fidx.insert(j);
			for(int j=0; j<glen; ++j) if(gs[j]==s[1]) sidx.insert(j);

			for(set<int>::iterator f_it=fidx.begin(); f_it!=fidx.end()&&!f; ++f_it) {
				for(set<int>::iterator s_it=sidx.lower_bound(*f_it); s_it!=sidx.end()&&!f; ++s_it) {
					int k = (*s_it)-(*f_it);
					if((*f_it)+k*(len-1)+1>glen) break;
					for(int l=2; l<len; ++l) {
						if(s[l]!=gs[(*f_it)+k*l]) break;
						if(l==len-1) {
							ans++; f=true;
							break;
						}
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
 
#define    pi          acos(-1) 
#define    all(x)      (x).begin(),(x).end()
#define    fill(x,y)   memset(x, y, sizeof(x))
#define    gcd(x,y)    __gcd(x,y)
#define    lcm(x,y)    (x*(y/gcd(x,y))
#define    trace(x)    cout << #x << " = " << x << endl
#define    bug         cout << "Bug check" << endl
#define    endl        '\n'
 
using namespace std;
 
int main(){
	//freopen("in.txt","r", stdin);
	//freopen("out.txt","w", stdout);
 
	//ios::sync_with_stdio(0);
	//cin.tie(0);

	int n,r;
	cin >> n >> r; 
	if(n>=10){
		cout << r << endl;
	} 
	else{
		cout << r+100*(10-n) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG



int main() {
  ll K, X;
  cin >> K >> X;
  if (K*500>=X) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3592
A = [3, 5, 7]
B = [3, 5, 7]
for i in range(9):
    C = []
    for b in B:
        C.append(10*b+3)
        C.append(10*b+5)
        C.append(10*b+7)
    A += C
    B = C

n = int(input())
c = 0

for a in A:
    if a > n:
        break
    if set(str(a)) == {'3', '5', '7'}:
        c += 1
print(c)

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

int main(){
    int n;
    cin >> n;
    int v[n],c[n];
    for(int i = 0; i < n; ++i)cin >> v[i];
    for(int i = 0; i < n; ++i)cin >> c[i];
    int sum = 0;
    int x;
    for(int i = 0; i < n;++i){
        x = v[i] - c[i];
        if(x > 0)sum = sum + x;
    }
    cout << sum;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <assert.h>
#include <sstream>
#include <type_traits>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pF first
#define pS second
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define GCD(a,b) __gcd((a),(b))
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> >
#define vll vector <long long>
#define allof(x) (x).begin(), (x).end()
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define printArr(a,l) cout<<#a<<": ";for(int i=0;i<(l);i++){cout<<a[i]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(int i=0;i<(r);i++){for(int j=0;j<(c);j++){cout<<a[i][j]<<" ";}cout<<endl;}
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector<string>vec_splitter(string s){s+=',';vector<string>res;while(!s.empty()){res.push_back(s.substr(0,s.find(',')));s=s.substr(s.find(',')+1);}
return res;}
void debug_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(vector<string>args,int idx,int LINE_NUM,Head H,Tail...T){if(idx>0)cerr<<", ";else cerr<<"Line("<<LINE_NUM<<") ";stringstream ss;ss<<H;cerr<<args[idx]<<" = "<<ss.str();debug_out(args,idx+1,LINE_NUM,T...);}
#ifdef LOCAL_DBG
#define dbg(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

int main () {
	fastCin;
	int n;
	cin >> n;
	ll a[200005] = {0}, s[200005] = {0};
	for (int x = 1; x <= n; x++) {
		cin >> a[x];
	}
	s[n] = a[n];
	for (int x = n-1; x >= 1; x--) {
		s[x] = a[x] + s[x+1];
	}
	ll ans = 0, mod = 1e9+7;
	for (int x = 1; x <= n-1; x++) {
		ans += (a[x] * (s[x+1]%mod))%mod;
		ans %= mod;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 6328
N,K = map(int, input().split())
A = [int(i) for i in input().split()]
D = {}
for i in A:
    if i in D:
        D[i] += 1
    else:
        D[i] = 1
B = list(D.values())
B.sort(reverse=True)
print(N-sum(B[:min(len(B), K)]))

Measured memory_bytes: 34788
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define mod ((ull)(1e9)+7)
#define MAX ((ull)(1e9)+1)

int main(){
	string s;
	cin >> s;
	int cnt=0;
	for(int i=0; i<s.length(); i++){
		if(i%2==0 && s[i]=='0') cnt++;
		if(i%2==1 && s[i]=='1') cnt++;
	}
	cout << min(cnt, (int)s.length()-cnt) << endl;
 	return 0;
}

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

// template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
// template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

int main(){
    int H,W; cin>>H>>W;
    vector<string> S(H);
    rep(i,H)cin>>S[i];
    vector<vector<ll>> dp(H,vector<ll>(W,0));
    dp[0][0] = 1;
    rep(i,H){
        rep(j,W){
            if(S[i][j]=='#')continue;
            if(i>0&&S[i-1][j]=='.') (dp[i][j] += dp[i-1][j])%=MOD;
            if(j>0&&S[i][j-1]=='.') (dp[i][j] += dp[i][j-1])%=MOD;
        }
    }
    cout<<dp[H-1][W-1]%MOD<<endl;
}

Measured memory_bytes: 12964
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

using namespace std;
using ll = long long;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

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

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

bool isAllVisit(const vector<bool>& visit) {
    for (auto&& v : visit) {
        if (!v)return false;
    }
    return true;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}


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

    string S;
    cin >> S;

    char now = S[0];
    int ans = 0;
    FOR(i, 1, S.length()) {
        if (now != S[i]) {
            ans++;
            now = S[i];
        }
    }

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

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

#define MAX_N 100000
#define MAX_K 1000

using namespace std;

struct coord
{
    int x, y, c;
};

coord v[MAX_N + 1];

int rest[MAX_K + 1][2][2];

int n, k;

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

    char ch;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i].x >> v[i].y >> ch;
        v[i].c = (ch == 'W');
    }

    int i, j;
    int rez = 0;
    for(i = 0; i < k; i ++)
    {
        for(j = 0; j <= k; j ++)
            rest[j][0][0] = rest[j][1][0] = rest[j][1][1] = rest[j][0][1] = 0;

        int cr = 0;
        int culcr;
        for(j = 1; j <= n; j ++)
        {
            if(v[j].y % (k << 1) >= i && v[j].y % (k << 1) <= i + k - 1)
                culcr = ((v[j].x / k) & 1);

            else
                culcr = 1 - ((v[j].x / k) & 1);

            rest[v[j].x % k][culcr][v[j].c] ++;

            if(v[j].c == culcr)
                cr ++;
        }

//        if(cr == 3 || n - cr == 3)
       // cout << "AVEM " << i << " " << cr << "\n";
       // cout << rest[0][0][0] << " " << rest[0][0][1] << "\n";
       // cout << rest[0][1][0] << " " << rest[0][1][1] << "\n\n";

        rez = max(rez, cr);
        rez = max(rez, n - cr);

        for(j = 0; j < k - 1; j ++)
        {
            cr -= rest[j][0][0];
            cr += rest[j][1][0];

            cr -= rest[j][1][1];
            cr += rest[j][0][1];


        //if(cr == 3 || n - cr == 3)
       // cout << "AVEM " << i << " " << j << " " << cr << "\n";

            rez = max(rez, cr);
            rez = max(rez, n - cr);
        }
    }

    cout << rez << "\n";

    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstring>

using namespace std;

int main(int argc, char* argv[])
{
    int m, f, r, s;

    while(cin >> m >> f >> r) {
        if (m == -1 && f == -1 && r == -1) break;
        s = m + f;
        if (m == -1 || f == -1 || s < 30) { 
            cout << 'F' << endl;
        } else if (s >= 80) {
            cout << 'A' << endl;
        } else if (s >= 65 && s < 80) {
            cout << 'B' << endl;
        } else if (s >= 50 && s < 65 || s >= 30 && s < 50 && r >= 50) {
            cout << 'C' << endl;
        } else if (s >= 30 && s < 50) {
            cout << 'D' << endl;
        } 
    }


    return 0;
}



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
int a,b,c;
int main()
{
    a=read(),b=read();c=6-a-b;cout<<c<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 1005
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
using namespace std;

char s[maxn];
int main(){
	//freopen("home.in", "r", stdin);
	scanf("%s", s);
	int m = strlen(s);
	bool vis[4];
	rep(i, 0, 3) vis[i] = 0;
	rep(i, 0, m - 1) {
		if (s[i] == 'N') vis[0] = 1;
		else if (s[i] == 'W') vis[2] = 1;
		else if (s[i] == 'E') vis[3] = 1;
		else vis[1] = 1;
	}	
	if ((vis[0] ^ vis[1]) || (vis[2] ^ vis[3])) printf("No");
	else printf("Yes");
	return 0;
}

Measured memory_bytes: 128