akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define intl long long int

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    intl i,j,n;
    cin>>n;
    map<string,intl> mp;
    for(i=0;i<n;i++){
        string s;
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<"\n";
    cout<<"WA x "<<mp["WA"]<<"\n";
    cout<<"TLE x "<<mp["TLE"]<<"\n";
    cout<<"RE x "<<mp["RE"]<<"\n";
}

Measured memory_bytes: 3664
#include<iostream>
#include<cstdlib>
using namespace std;
int main() {
  int a,b,k,n=0;
  int count = 0;
  cin >> a >> b;
  if(a<b){
    n = b;
  }else{
    n = a;
  }
  for(k=0;k<=n;k++){
  if((abs(a-k))==(abs(b-k))){
    count = 1;
    break;
  }
  }
    if(count == 1){
      cout << k << endl;
    }else{
      cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int X,Y,Z,a;
  scanf("%d %d %d",&X,&Y,&Z);
  a=X;
  X=Y;
  Y=a;
  a=X;
  X=Z;
  Z=a;
  printf("%d %d %d\n",X,Y,Z);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=2e5+100;
vector <int> g[N];
ll vis[N];
ll val[N];
ll mi=1e9+100;
ll id=0;
ll dfs(ll v){
    vis[v]=1;
    if (mi>val[v]){
        mi=val[v];
        id=v;
    }
    for (int i=0;i<g[v].size();i++){
        ll u=g[v][i];
        if (!vis[u]){
            dfs(u);
        }
    }
}
int32_t main(){
    ll n,m;
    cin >> n >> m;
    for (int i=0;i<n;i++){
        cin >> val[i];
    }
    for (int i=0;i<m;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    if (m==n-1){
        cout << 0;
        return 0;
    }
    ll ans=0;
    ll p1=0;
    for (int i=0;i<n;i++){
        mi=1e9;
        if (vis[i]){
            continue;
        }
        dfs(i);
        vis[id]=2;
        ans+=val[id];
        p1++;
    }
    vector <int> a;
    for (int i=0;i<n;i++){
        if (vis[i]==1){
            a.pb(val[i]);
        }
    }
    sort(a.begin(),a.end());
    p1-=2;
    if (a.size()<p1){
        cout << "Impossible";
        return 0;
    }
    for (int i=0;i<p1;i++){
        ans+=a[i];
    }
    cout << ans;
}


Measured memory_bytes: 12028
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	var N int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &N)

	as := make([]int, N+2)
	as[0] = 0
	as[N+1] = 0
	for i := 1; i <= N; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d", &as[i])
	}

	sum := 0
	for i := 0; i < len(as)-1; i++ {
		sum = sum + abs(as[i+1]-as[i])
	}

	ds := make([]int, N)
	for i := 0; i < len(as)-2; i++ {
		if as[i] < as[i+1] && as[i+2] < as[i+1] ||
			as[i] > as[i+1] && as[i+2] > as[i+1] {
			ds[i] = 2 * min(
				abs(as[i+1]-as[i]),
				abs(as[i+1]-as[i+2]),
			)
		} else {
			ds[i] = 0
		}
	}

	var buffer bytes.Buffer
	for _, d := range ds {
		buffer.WriteString(strconv.Itoa(sum - d))
		buffer.WriteString("\n")
	}
	fmt.Println(buffer.String())

}

func abs(n int) int {
	if n >= 0 {
		return n
	}
	return -n
}

func min(ns ...int) int {
	ret := math.MaxInt64
	for _, n := range ns {
		if n < ret {
			ret = n
		}
	}
	return ret
}


Measured memory_bytes: 9728
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	bool a[27];
	memset(a,false,sizeof(a));
	for(int i=0;i<s.size();i++)
		a[s[i]-96]=true;
	bool f=false;
	for(int i=1;i<=26;i++)
		if(!a[i])
		{
			char x=i+96;
			cout<<x;
			f=true;
			break;
		}
	if(!f)
		cout<<"None";
	return 0;
}

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

int main()
{
 int n,m;
  
  scanf("%d%d",&n,&m);
  
  int a[51]={},b[51]={};
  int i,j;
  int ans[51]={};
  
  for(i=1;i<=m;i++)
  {
    scanf("%d %d",&a[i],&b[i]);
  }
  
  for(i=1;i<=m;i++)
  {
    for(j=1;j<=n;j++)
    {
      if(a[i]==j)
      {
        ans[j]++;
      }
    }
  }
  
   for(i=1;i<=m;i++)
  {
    for(j=1;j<=n;j++)
    {
      if(b[i]==j)
      {
        ans[j]++;
      }
    }
  }
  
  for(i=1;i<=n;i++)
  {
    printf("%d\n",ans[i]);
  }
  return 0;
}

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

int main() {

  int N, A, B, X, Y, C, D;
  cin >> N;
  A = N / 10;
  B = N % 1000;
  
  X = A % 10;
  Y = B % 10;
  
  C = X + 10*X + 100*X;
  D = Y + 10*Y + 100*Y;
  
  if (A == C || B == D) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}



Measured memory_bytes: 256
#include<stdio.h>
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,j,n) for((i)=(j) ; (i)<(n) ; (i)++)
#define pl(format,var) p(format "\n",var)
#define p(format,var) printf(format,var)
#define asizeof(array) (sizeof(array)/sizeof(array[0]))

int main(){
	int i,j,k,n;
	char line[80];
	int a,b,c;
	
	fgets(line, sizeof(line), stdin);
	sscanf(line, "%d", &n);
	
	rep2(i,n){
		fgets(line, sizeof(line), stdin);
		sscanf(line, "%d %d %d", &a, &b, &c);
		a = a*a;
		b = b*b;
		c = c*c;
		if(a==b+c || b==a+c || c==b+a)
			printf("YES\n");
		else
			printf("NO\n");
	}

  return 0;
}

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

using namespace std;

typedef long long ll;

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> cand;
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    if (a == 1) cand.push_back(b);
    if (b == N) cand.push_back(a);
  }
  sort(cand.begin(), cand.end());
  bool ok = false;
  for (int i = 1; i < cand.size(); ++i) {
    if (cand[i - 1] == cand[i]) {
      ok = true;
      break;
    }
  }
  cout << (ok ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int gcd(int x,int y){
	if(y == 0)return x;
	return gcd(y,x%y);
}
signed main(){
	//    4/n = 1/a + 1/b + 1/c
	// 1/c =   (4*a*b - n*b - n*a) /(a*b*n)
	int n;cin >> n;
	for(int a = 1;a <= 3500;a++)for(int b = 1;b <= 3500;b++){
		int ue = 4*a*b - n*b - n*a;
		if(ue < 0 )continue;
		int shita = a*n*b;
		int g = gcd(ue,shita);
		shita /= g;
		if(ue == g){
			int c = shita;
			cout << a << " " << b << " " << c << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int a,b,n;
  cin>>a>>b>>n;
  long long int ans=0;
  if(n<b-1){
    ans=(a*n)/b;
  }else{
    ans=((a*(b-1)))/b;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using ll = long long;
using lint = long long;
typedef pair<int,int> P;
const lint inf=1e18+7;
const int MOD=1000000007;
void solve(int n,int x){
    vector<int> res(2*n+5,0);
    if(x==2){
        res[n]=x;
        res[n+1]=1;
        int cur=3;
        rep1(i,2*n-1){
            if(res[i]!=0)continue;
            res[i]=cur;
            ++cur;
        }
    }
    else{
        res[n]=x;
        res[n+1]=2*n-1;
        res[n-1]=1;
        res[n+2]=2;
        int cur=3;
        rep1(i,2*n-1){
            if(res[i]!=0)continue;
            if(cur==x)++cur;
            res[i]=cur;
            ++cur;
        }
    }
    rep1(i,2*n-1){
        cout<<res[i]<<"\n";
    }
}
signed main(){
  int n,x;cin>>n>>x;
  if(n==2&&x==2){
      cout<<"Yes"<<"\n";
      rep1(i,2*n-1){
          cout<<i<<"\n";
      }
  }
  else if(n==2&&x!=2){
      cout<<"No"<<"\n";
  }
  else{
      if(x==1||x==2*n-1){
          cout<<"No"<<"\n";
      }
      else{
          cout<<"Yes"<<endl;
          solve(n,x);
      }
  }
  return 0;
}

Measured memory_bytes: 3072
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int K; cin >> K;
  ll A[100100]; rep(i, K) cin >> A[i];
  reverse(A, A + K);
  ll mini = 2, maxi = 2;
  rep(i, K) {
      if(maxi < A[i]) {
          cout << -1 << endl;
          return 0;
      }
      mini = max(A[i], mini);
      mini = (ll)((mini + A[i] - 1)/ A[i]) * A[i];
      maxi = (ll)(maxi / A[i]) * A[i] + A[i] - 1;
      if(mini > maxi) {
          cout << -1 << endl;
          return 0;
      }
  }
  cout << mini << " " << maxi << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int a,b,c;
int d;
int main(){
  cin >> a >> b >> c >> d;
  if(abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define pb push_back
# define ll long long
# define fi first
# define se second
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define mkp make_pair
//# define time cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

using namespace std;

int q , w , e , z ;

int main()
{
	speed;

    int a , b , c , d ;
    cin >> a >> b >> c >> d ;
    int k = max( a , c ) ;
    int u = min( b , d ) ;
    int j = u - k ;
    if( j < 0 ){
        cout << 0 ;
    }
    else{
        cout << j ;
    }

	time;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
const double PI = acos(-1.0);
const double EPS = (1e-9);
typedef long long ll;
typedef unsigned long long ull;
#define flush fflush(stdout), cout.flush()
#define all(v) ((v).begin()),((v).end())
#define rall(v) ((v).rbegin()),((v).rend())
#define clr(v,line) memset(v,line,sizeof(v))
#define rep(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lcm(a,b) (a*(b/__gcd(a,b)))
#define P 1000000007
#define endl '\n'
const int dx[] = {1,-1,0,0,1,-1,1,-1};
const int dy[] = {0,0,1,-1,1,-1,-1,1};
const int dxhorse[] = {-2,-2,-1,-1,1,1,2,2};
const int dyhorse[] = {1,-1,2,-2,2,-2,1,-1};
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 <<endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

void file() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
void fast()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
}

string s;


int main(int argc, char const *argv[])
{

	cin>>s;

	std::vector<string> v = {"dream", "erase", "dreamer", "eraser"};
	
	string cpy = s;

	sort(all(v));

	do{
		int tot = 0;

		for (int t = 0; t < v.size(); ++t)
		{
			for (int i = 0; i < s.size(); ++i)
			{
				if(s.substr(i,(int)v[t].size()) == v[t])
				{
					s.erase(i,(int)v[t].size());
					tot+=(int)v[t].size();
					i--;
				}
			}
		}

		if(tot==(int)cpy.size())
			return cout<<"YES",0;
		s = cpy;

	} while(next_permutation(all(v)));

	cout<<"NO";

}	

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x1,y1,x2,y2,x3,y3,x4,y4; cin >> x1 >> y1 >> x2 >> y2;
    cout << x2 + (y1 - y2) << " " << y2 - (x1 -x2) << " " << x1 + (y1 - y2) << " " << y1 - (x1 - x2) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<random>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


int main() {
	init();
	
	int X; cin >> X;
	ll cnt = 0, i = 0;
	while (cnt < X) {
		++i;
		cnt += i;
	}
	cout << i << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <cmath>
#include <numeric>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long LL;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  REP(i, N) { cin >> A[i]; }
  sort(A.begin(), A.end(), greater<int>());
  int sum = accumulate(A.begin(), A.end(), 0);
  cout << (A[M-1] * M * 4 >= sum ? "Yes" : "No") << endl; 
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

// Union-Find
struct UF {
	int n, c;
	vector<int> p;

	UF(int n): n(n), c(n), p(n, -1) {}

	// xが属する集合とyが属する集合の併合
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return false;
		if (p[x] > p[y]) swap(x, y);
		p[x] += p[y];
		p[y] = x;
		c--;
		return true;
	}
	
	// xが属する集合の親
	int find(int x) { return (p[x] < 0 ? x : p[x] = find(p[x])); }

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

	// xが属する集合の大きさ
	int size(int x) { return -p[find(x)]; }
	
	// 連結成分の個数
	int count() { return c; }
};

int N;
int A[100010];
pair<int, int> ps[100010];

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

    cin >> N;
    bool zero = true;
    REP(i, N) {
        cin >> A[i];
        ps[i] = {A[i], i};
        zero &= (A[i] == 0);
    }
    sort(ps, ps + N);
    reverse(ps, ps + N);
    int h = -1;
    UF uf(N);
    int ans = 0;
    REP(i, N) {
        if (ps[i].first != h) {
            ans = max(ans, uf.count() - N + i);
            h = ps[i].first;
        }
        int p = ps[i].second;
        if (p - 1 >= 0 && A[p - 1] >= ps[i].first) uf.unite(p - 1, p);
        if (p + 1 < N && A[p + 1] >= ps[i].first) uf.unite(p + 1, p);
    }
    if (ps[N - 1].first > 0) ans = max(ans, uf.count());
    cout << ans << endl;
}


Measured memory_bytes: 5972
#include <bits/stdc++.h>
#define fly ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define ll long long

using namespace std;

int main(int argc, char const *argv[]) {
  fly;
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << max(a*c, max(b*c, max(a*d, b*d))) << endl;
  return 0;
}


Measured memory_bytes: 3652
D, N = map(int, input().split())


if D==2:
    dp = [10000*i for i in range(1,10010)]
    print(dp[N-1] if N!=100 else dp[N])
elif D==1:
    dp = [100*i for i in range(1,10010)]
    print(dp[N-1] if N!=100 else dp[N])
else:
    print(N if N!=100 else 101)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pi 3.14
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<long long,int> pli;
typedef pair<int,long long> pil;
const int INF=1000000007;
const int MOD=1000000007;
const int nmax=10123;

char in[20],s[7][20]={"SUN","MON","TUE","WED","THU","FRI","SAT"};

int main()
{
    scanf("%s",in);
    for(int i=0;;++i){
        if(strcmp(in,s[i])==0){
            printf("%d\n",7-i);
            break;
        }
    }
    return 0;
}


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

int main()
{
  string str;
  int ans = 0;

  while (cin >> str){
    int num = 0;
    for (int i = 0; i < str.size(); i++){
      if (isdigit(str[i])){
        num *= 10;
        num += str[i] - '0';
      }
      else {
        ans += num;
        num = 0;
      }
    }
    ans += num;
  }
  cout << ans << endl;

  return (0);
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

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

  ll anspm=0;
  ll diff=0;
  vector<ll>sum(n);
  sum[0]=a[0];
  for(int i=1;i<n;i++)sum[i]=sum[i-1]+a[i];
  for(int i=0;i<n;i++){
    if(i%2){
      if(sum[i]+diff>=0)anspm+=1+sum[i]+diff,diff-=1+sum[i]+diff;
    }
    else{
      if(sum[i]+diff<=0)anspm+=1-(sum[i]+diff),diff+=1-(sum[i]+diff);
    }
  }


  ll ansmp=0;
  diff=0;
  for(int i=0;i<n;i++){
    if(i%2){
      if(sum[i]+diff<=0)ansmp+=1-(sum[i]+diff),diff+=1-(sum[i]+diff);
    }
    else{
      if(sum[i]+diff>=0)ansmp+=1+sum[i]+diff,diff-=1+sum[i]+diff;
    }
  }

  cout<<min(anspm,ansmp)<<endl;
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) ((a).begin(),(a).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
 
ll gcd(ll a, ll b){
  return b?gcd(b,a%b):a;
}
 
ll extgcd(ll a, ll b, ll& x, ll& y){
  ll d = a;
  if(b!=0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }else{
    x = 1; y = 0;
  }
  return d;
}
 
ll mod_inverse(ll a, ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m) % m;
}
 
pii linear_congruence(const vi& A, const vi& B, const vi& M){
  ll x = 0, m = 1;
  rep(i,A.size()){
    ll a = A[i]*m, b = B[i] - A[i] * x, d = gcd(M[i],a);
    if(b%d != 0)return make_pair(0,-1);
    ll t = b/d * mod_inverse(a/d, M[i]/d) % (M[i]/d);
    x = x+m*t;
    m *= M[i]/d;
  }
  return make_pair( (x%m + m) % m , m);
}
 
int main(){
  ll n,m,d;
  cin >> n >> m >> d;
  vi a(m);
  rep(i,m)cin >> a[i];
 
  rep(i,d){
    vi r, aa, e;
    rep(j,m){
      ll  tmp;
      cin >> tmp;
      if(tmp<0)continue;
      r.push_back(tmp);
      aa.push_back(a[j]);
      e.push_back(1);
    }
    if(r.size()==0)continue;
     
    pii ans = linear_congruence(e,r,aa);
    ll b = ans.first, mod = ans.second;
    if(mod<0){
      cout << -1 << endl;
      return 0;
    }
 
    ll tmp = (n/mod+100) * mod + b;
    while(tmp<n)tmp += mod;
    while(n<tmp)tmp -= mod;
    if(tmp<0){
      cout << -1 << endl;
      return 0;
    }
    n = tmp;
 
  }
 
  cout << n << endl;
}

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

 void solve()
 { 
   
   string str;
   cin>>str;int s=0;
   for (int i = 0; i < str.length(); ++i)
   {
       int cnt= int(str[i]-'0');
       s+=cnt;

   }

   if(s%9!=0)cout<<"No\n";
   else cout<<"Yes\n";

}

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

    solve();
}

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

using namespace std;

long long dp[223456][3];


struct FenwickTreeMax {
    long long bit[223456];
    int n;
    const long long INF = (int)1e9;

    FenwickTreeMax(int n) {
        this->n = n;
	for(int i = 0; i < n+10; i++) bit[i] = 0;
    }

    long long getmax(int r) {
        long long ret = -INF;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret = max(ret, bit[r]);
        return ret;
    }

    void update(int idx, long long val) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] = max(bit[idx], val);
    }
};

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

	for(int i = 0; i < n; i++) cin >> a[i];
	FenwickTreeMax ft(n+10);
	
	dp[0][0] = 0;
	dp[0][1] = a[0];
	ft.update(h[0],dp[0][1]);

	for(int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i][1] = ft.getmax(h[i]) + a[i];
		ft.update(h[i],dp[i][1]);
	}

	cout << max(dp[n-1][0], dp[n-1][1]) << endl;
}


Measured memory_bytes: 8064
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
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 pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n;
    cin >> n;
    VI a(n);
    REP(i,n) cin >> a[i];
    REP(i,n){
        if (i > 0) cout << " ";
        cout << a[n-1-i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3068
text = raw_input().split()
Max = 1
for i in text:
    if len(i) > Max:
        Maxstr = i
        Max = len(i)
Max = 1
for i in text:
    t = text.count(i)
    if t > Max:
        Maxcount = i
        Max = t

print Maxcount,Maxstr

Measured memory_bytes: 4216
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

# 誤読はクソ雑魚
for i in range(N):
    a = A[i]
    b = [0]*M
    for j in range(M):
        b[a[j]-1] = M-j
    A[i] = b

select = [set() for i in range(M)]
cur = [[1]*(M+1) for i in range(N)]
mp = [[M+1]*(M+1) for i in range(N)]
I = [M]*N
for i in range(N):
    mpi = mp[i]
    Ai = A[i]
    for j in range(M):
        mpi[Ai[j]] = j
    select[mpi[M]].add(i)

ans = N
cnt = 0
for t in range(M+1):
    ma = max(map(len, select))
    ans = min(ans, ma)
    rm = []
    for i in range(M):
        if len(select[i]) == ma:
            rm.append(i)
    target = set()
    for i in rm:
        for j in range(N):
            cur[j][A[j][i]] = 0
        target |= select[i]
        select[i] = []
        cnt += 1
    if cnt == M:
        break
    for i in target:
        p = I[i]
        c = cur[i]
        while c[p] == 0:
            p -= 1
        I[i] = p
        select[mp[i][p]].add(i)
print(ans)

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

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

  double rev_sum = 0;
  rep(i, n) {
    int a;
    cin >> a;

    rev_sum += 1.0 / a;
  }

  printf("%.10f\n", 1.0 / rev_sum);
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b;
  cin>>a>>b;
  if(a%3==0 || b%3==0 || (a+b)%3==0) cout<<"Possible"<<'\n';
  else cout<<"Impossible"<<'\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

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

  int n, limitW;
  cin >> n >> limitW;
  int w[n], v[n];
  rep(i, 0, n) cin >> v[i] >> w[i];

  int dp[n + 1][limitW + 1];
  rep(i, 0, n + 1) rep(j, 0, limitW + 1) dp[i][j] = 0;

  rep(i, 0, n) {
    rep(j, 0, limitW + 1) {
      if(j - w[i] >= 0) {
        dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
      } else {
        dp[i + 1][j] = dp[i][j];
      }
    }
  }

  int rsl = 0;
  rep(i, 0, limitW + 1) {
    rsl = max(rsl, dp[n][i]);
  }
  cout << rsl << endl;
}



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

using namespace std;

int N;
string s;

void solve()
{
  cin >> N >> s;
  int count=0;
  s.push_back('#');
  for(int i=0; i+1 < s.size(); i++)
  {
    if(s[i] != s[i+1])
      count++;
  }
  cout << count << endl;
}
  
int main()
{
  solve();
  return 0;
}
  
        
        

Measured memory_bytes: 3784
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		int N = Integer.parseInt(in.readLine());
		int[] v = new int[N];
		String[] tokens = in.readLine().split(" ");
		for (int i = 0; i < N; ++i) {
			v[i] = Integer.parseInt(tokens[i]);
		}
		Arrays.sort(v);
		double result = 0.0;
		result += (double) v[0];
		result += (double) v[1];
		result /= 2.0;
		for (int i = 2; i < N; ++i) {
			result += (double) v[i];
			result /= 2.0;
		}
		System.out.println(result);
	}
}


Measured memory_bytes: 21332
#include<iostream>

int main(){
    int i;
    int count[1000]={0};
    char ch;
    
    while((ch = getchar()) != EOF){
        count[ch]++;
    }

    char moji='a';
    for(i=97;i<=122;i++){
        std::cout<<moji<<" : "<<count[i]+count[i-32]<<std::endl;
        moji++;
    }

    return 0;
}



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

int main()
{
  int n;
  cin>>n;
  vector<int> arr(n);
  vector<int> temp(n);
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
    temp[i] = arr[i];
  }
  sort(temp.begin(),temp.end());
  int l = temp[n-1];
  int sl = temp[n-2];
  for(int i=0;i<n;i++)
  {
    if(arr[i] == l)
      cout<<sl<<"\n";
    else
      cout<<l<<"\n";
  }
  return 0;
}

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

ll gcd(ll a, ll b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}


int main(){
  ll N,m=1;
  cin>>N;
  vector<ll> A(N);
  vector<ll> forward(N),back(N),ans(N);
  
  for(int i=0;i<N;i++)
    cin>>A.at(i);
  
  if(N==2){
    cout<<max(A.at(0),A.at(1))<<endl;
    return 0;
  }
  
  forward.at(0)=A.at(0);
  back.at(0)=A.at(N-1);
  for(int i=1;i<N;i++){
    forward.at(i)=gcd(forward.at(i-1),A.at(i));
    back.at(i)=gcd(back.at(i-1),A.at(N-i-1));
  }
  ans.at(0)=back.at(N-2);
  ans.at(N-1)=forward.at(N-2);
  for(int i=1;i<N-1;i++){
    ans.at(i)=gcd(forward.at(i-1),back.at(N-i-2));
  }
  
  sort(ans.begin(),ans.end());
  cout<<ans.at(N-1);
}


Measured memory_bytes: 3456
#include <iostream>
#include <vector>
#include<cmath>
using namespace std;
#define endl '\n'

using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a;
    cin >> a;
    if(a=="ABC"){
        cout << "ARC";
    }else{
        cout << "ABC";
    }

    return 0;
}

Measured memory_bytes: 3612
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
	 static List<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] p = new int[N];
        double ans=0;

        long[] q = new long[N];
        for(int i=0;i<N;i++) {
        	p[i]=sc.nextInt();
        }
        for(int i=0;i<K;i++) {
        	q[0]=q[0]+p[i];
        }
        for(int i=K;i<N;i++) {
        	q[i-K+1]=q[i-K]+p[i]-p[i-K];
        }
        long max=0;
        for(int i=0;i<N;i++) {
        	max=Math.max(max, q[i]);
        }
        ans=(max+K)/2.0;
        System.out.println(ans);

        sc.close();
    }


}

Measured memory_bytes: 82960
#include <iostream>
#include <map>
#include <functional>
using namespace std;

int main(){
	multimap<int, int, greater<int> > rank;
	while(1){
		int n, score;
		scanf("%d,%d", &n, &score);
		if(!n && !score) break;
		rank.insert( pair<int, int>(score, n) );
	}
	multimap<int, int, greater<int> >::iterator it = rank.begin();

	map<int, int> res;
	int buf = (*it).first;
	res.insert( pair<int, int>((*it).second, 1));
	it++;

	int i = 1;
	
	while(it != rank.end()){
		if(buf == (*it).first){
			res.insert( pair<int, int>((*it).second, i) );
		}else{
			res.insert( pair<int, int>((*it).second, ++i) );
			buf = (*it).first;
		}
		it++;
	}

	int group;
	while(cin >> group){
		cout << res[group] << endl;
	}
}

Measured memory_bytes: 0
n = int(input())
s = input()
d = {'R':0, 'G':0, 'B':0}
for x in s:
    d[x] += 1
count1 = d['R']*d['G']*d['B']
maxdif = (n-1)//2
count2 = 0
for d in range(1,maxdif+1):
    for i in range(d,n-d):
        if s[i-d] != s[i] and s[i] != s[i+d] and s[i-d] != s[i+d]:
            count2 += 1
print(count1-count2)

Measured memory_bytes: 9212
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)

int N, M, A[112345], B[112345], C[112345], T[112345];

int main() {

	scanf("%d%d", &N, &M);
	rep(i, N) {
		scanf("%d", &A[i]);
	}
	sort(A, A + N);

	vector<pair<int, int>> s;
	rep(i, M) {
		scanf("%d%d", &B[i], &C[i]);
		s.push_back({ -C[i],-B[i] });
	}
	sort(s.begin(), s.end());

	rep(i, M) {
		C[i] = -s[i].first;
		B[i] = -s[i].second;
	}

	int b = 0, ii = -1;

	rep(i, N) {
		if (ii >= M) break;
		if (!b) {
			ii++;
			b = B[ii];
		}
		T[i] = C[ii];
		b--;
		if (A[i] < T[i]) A[i] = T[i];
	}

	ll ans = 0;
	rep(i, N) {
		ans += A[i];
	}

	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 2676
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;

#define pb(x) push_back(x)
#define ppb() pop_back()
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
#define FOR0(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i=(a);i>=(int)(b);i--)
#define sf(n) scanf("%d", &n)
#define sfc(x) scanf("%c", &x)
#define pf(x) printf("%d", x)
#define pff(x) printf("%lf", x)
#define pfc(x) printf("%c", x)
#define pfs(x) printf("%s", x)
#define sf2(a,b) scanf("%d %d", &a, &b)
#define sf3(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define sz size()
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
bool prime[500010];
void SieveOfEratosthenes(ll n)
{
    memset(prime,true, sizeof(prime));

    for (ll p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (ll i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}

ll power(ll x,ll y)
{
    if (y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);
}

int main(){
  fast
  ll n;
  cin>>n;
  ll a[n],b[n],c[n];
  FOR0(i,n)cin>>a[i];
  FOR0(i,n)cin>>b[i];
  FOR0(i,n){
    c[i]=a[i]-b[i];
  }
  sort(c,c+n);
  ll sum1=0,ind=-1;
  FOR0(i,n){
    if(c[i]>=0)break;
    ll term=-1*c[i];
    sum1+=term;
    ind=i;
  }
  ll sum2=0;
  ll count=0;
  for(ll i=n-1;i>=ind+1;i--){
    if(sum2>=sum1)break;
    sum2+=c[i];
    count++;
  }
  if(sum2<sum1)cout<<-1;
  else{
    cout<<count+ind+1;
  }
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

int main() {
  i64 N;
  cin >> N;
  dynarr<i64> B(N - 1);
  rep(i,0,N - 1) cin >> B[i];
  dynarr<pair<i64, i64>> vec;
  rep(i,0,N - 1) {
    vec.push_back({ B[i], i });
  }
  sort(all(vec));
  dynarr<i64> flag(N);
  i64 ans = 0;
  for(auto p : vec) {
    i64 i = p.second;
    i64 a = p.first;
    if(!flag[i]) {
      ans += a;
      flag[i] = 1;
    }
    if(!flag[i + 1]) {
      ans += a;
      flag[i + 1] = 1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>

#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include<atcoder/all>

using namespace std;

using namespace atcoder;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << endl
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << " \n"[i==(int)v.size()-1]
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 500050;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll LINF = 1e18 + 1;
constexpr int INF = 1e9 + 1;
void Yes(bool cond) { cout << (cond ? "Yes" : "No") << '\n'; }
void YES(bool cond) { cout << (cond ? "YES" : "NO") << '\n'; }

using mint = modint998244353;
struct S {
	mint a;
	int size;
};

struct F {
	mint a, b;
};

S op(S l, S r) { return S{ l.a + r.a,l.size + r.size }; }
S e() { return S{ 0,0 }; }
S mapping(F l, S r) {
	return { r.a*l.a + r.size*l.b,r.size };
}
F composition(F l, F r) {
	return F{ r.a*l.a, r.b*l.a + l.b };
}
F id() {
	return { 1,0 };
}

void solve() {
	int n, q; cin >> n >> q;
	vector<S>a(n);
	REP(i, n) {
		int x; cin >> x;
		a[i] = S{ x,1 };
	}
	lazy_segtree<S, op, e, F, mapping, composition, id>seg(a);
	REP(i, q) {
		int t; cin >> t;
		if (t == 0) {
			int l, r, c, d; cin >> l >> r >> c >> d;
			seg.apply(l, r, F{ c,d });
		}
		else {
			int l, r; cin >> l >> r;
			print(seg.prod(l, r).a.val());
		}
	}

}



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

	//int q;
	//cin >> q;
	//while (q--)
	solve();

}



Measured memory_bytes: 19612
#include<iostream>
#include<cmath>
#include<cstdio>
#include<complex>
using namespace std;

typedef complex<double> Point;

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)
#define EQV(a,b) ( EQ( (a).real() , (b).real() ) && EQ( (a).imag(), (b).imag() ) )

double abs(Point a,Point b) {
  return sqrt( (a.real()-b.real())*(a.real()-b.real()) + (a.imag()-b.imag())*(a.imag()-b.imag()) );
}

double cross(Point a,Point b) {
  return (a.real()*b.imag()- a.imag()*b.real());
}

// àÏ : aEb
double dot(Point a,Point b) {
  return (a.real()*b.real() + a.imag()*b.imag());
}

//¼üÌ½s»è
int is_parallel(Point a1,Point a2,Point b1,Point b2){
  return EQ( cross(a1-a2,b1-b2) , 0.0 );
}

// _a,bð[_Æ·éüªÆ_cÆÌ£
double distance_ls_p(Point a, Point b, Point c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

int main() {

  double D;
  while(true) {
    cin>>D;
    if(D==0) break;

    double vx,vy,px,py,st;
    cin>>px>>py>>vx>>vy;

    Point as = Point(px,py);
    Point g = Point(0,0);
    Point at = Point(px+vx,py+vy);
    if( !is_parallel( as, g, at, as ) ) goto NO;

    st = distance_ls_p( as, at, g );
    if( EPS <  abs( as, g ) - st ) {
      if( abs( as, g ) > D ) goto NO;
      printf("%.10lf\n", abs(as,g));
    } else if( abs( abs( as, g ) - st ) < EPS ){
      if( 2 - abs( as, g ) > D ) goto NO;
      printf("%.10lf\n", 2-abs(as,g) );
    }
    continue;

  NO:
    printf("impossible\n");
  }
}

Measured memory_bytes: 0
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let p: Vec<i32> = (0..n).map(|_| read()).collect();

    let ans = p
        .windows(3)
        .filter(|x| (x[0] < x[1] && x[1] < x[2]) || x[0] > x[1] && x[1] > x[2])
        .count();

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

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    char joi[1000001];
    char *p;
    int i, len;
    int rj, ro, ri;
    int level;
 
    scanf("%s", joi);
    len = strlen(joi);
 
    level = 0;
    for (i = 0; i < len; ){
        if (joi[i] == 'J'){
            for (rj = 0; joi[i + rj] == 'J'; rj++);
            for (ro = 0; joi[i + rj + ro] == 'O'; ro++);
            for (ri = 0; joi[i + rj + ro + ri] == 'I'; ri++);
 
            if (!(ri < ro || rj < ro)){
                level = fmax(level, ro);
            }
            i = i + rj + ro + ri;
        }
        else {
            i++;
        }
    }
 
    printf("%d\n", level);
 
    return (0);
}

Measured memory_bytes: 1520
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> h, dp(n);
    rep(i, n){
        int x;
        cin >> x;
        h.push_back(x);
    }

    dp[0] = 0;
    rep2(i, 1, n){
        int tmpmin = INT32_MAX;
        int tmpk = min(i, k);
        rep2(j, 1, tmpk+1){
            tmpmin = min(tmpmin, dp[i-j]+abs(h[i]-h[i-j]));
        }
        dp[i] = tmpmin;
    }
    cout << dp[n-1] << endl;
    return 0;
}

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

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

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

int main() {

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

	string S;
	cin >> S;

	int st = 0;
	bool flag = true;
	while (st < S.length()) {

		if (S.substr(st, 5) == "dream" && (S.substr(st + 5, 3) == "era" || S.substr(st + 5, 3) == "dre" || st + 5 == S.length())) st += 5;
		else if (S.substr(st, 7) == "dreamer" && (S.substr(st + 7, 2) == "er" || S.substr(st + 7, 2) == "dr" || st + 7 == S.length())) st += 7;
		else if (S.substr(st, 5) == "erase" && (S.substr(st + 5, 3) == "era" || S.substr(st + 5, 3) == "dre" || st + 5 == S.length())) st += 5;
		else if (S.substr(st, 6) == "eraser") st += 6;
		else {
			flag = false;
			break;
		}
	
	}

	if (flag) cout << "YES";
	else cout << "NO";

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#define MAXN 200000
using namespace std;

typedef long long int lli;

lli N, A[MAXN], K, ans = 1;
bool visit[MAXN];
vector<int> towns;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    for(int j = 0; j < N; ++j)
        cin >> A[j];
    int loop;
    for(int v = 0; ; v = A[v] - 1){
        if(visit[v]){
            loop = v;
            break;
        }
        visit[v] = true;
        towns.push_back(v);
    }
    lli cnt = 0;
    for(int v = 0; v != loop; v = A[v] - 1){
        ++cnt;
    }
    if(K < cnt)
        cout << towns[K] + 1;
    else
        cout << towns[(K - cnt) % (lli)(towns.size() - cnt) + cnt] + 1;
    return 0;
}

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

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
ll lcm(ll x, ll y) {
    return x / GCD(x, y) * y;//先に割り算をして掛けられる数を小さくして掛け算を行う
}

int main() {
   int N;
   cin >> N;
   vector<ll> a(N);

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

  
   for (int i = N - 1; i >= 0; i -= 2)
   {
       cout << a[i] << " ";
   }
   if (N % 2 == 1)
   {
        for (int i = 1; i < N; i += 2)
   {
      
       cout << a[i] << " ";
   }

   }else
   {
        for (int i = 0; i < N; i += 2)
   {
      
       cout << a[i] << " ";
   }
   
   }
   
   
  
   cout << endl;
   
     
    return 0;

}


Measured memory_bytes: 4700
#include<stdio.h>
int main(){
  int a,i,s,j,k,n,m;
  int jro[25];
  while(1){
    scanf("%d",&i);
    if(i==0){ break; }

    for(j=0;j<i;j++){
      scanf("%d",&jro[j]);
    }
    s=32;
    k=1;
    m=0;
    while(1){
      if(k%2==1){
	n=(s-1)%5;
      }
      else{
	n=jro[m];	
	m++;
	if(m==i){m=0;
	}
      }
      k++;
      s-=n;
      if(s>=0){
	printf("%d\n",s);
      }
      else{
	s=0;
	printf("%d\n",s);
      }
      if(s==0){break;}
    } 
  }
  return 0;
}

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

using namespace std;

int main()
{
    vector<string> deck;
    int i;
    for(i=0; i<3; i++){
        string s;
        getline(cin, s);
        deck.push_back(s);
    }

    string t = "abc";

    bool gameWon = false;
    i =0;
    size_t j[3] = {0};
    int winner;

    while(!gameWon){
        if(j[i] == deck[i].size()){
            gameWon = true;
            winner = i;
            break;
        }

        if(deck[i][j[i]] == t[0]){
            j[i]++;
            i = 0;
        } else if (deck[i][j[i]] == t[1]) {
            j[i]++;
            i = 1;
        } else {
            j[i]++;
            i = 2;
        }
    }

    if(winner == 0){
        cout << "A" <<endl;
    }else if(winner == 1){
        cout << "B" <<endl;
    }else {
        cout << "C"<< endl;
    }
}


Measured memory_bytes: 3636
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
const ll INF=1000000000000000001;
int main(){
    int n,k;cin >> n >> k;
    double ans=0;
    for(int i=1;i<=n;i++){
    if(i>=k){
        ans+=(double)1/n;
    }
    else {
        double lose=1.0/n;
        int cnt=0;
        int now=i;
        while(now<k){
         cnt++;
         now*=2;
        }
      lose=pow((double)1/2,cnt)*(double)1/n;
      ans+=lose;
    }
    }
    cout <<setprecision(12)<< ans << endl;
}

Measured memory_bytes: 256