akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long[] capa = new long[5];
        for (int i = 0; i < 5; i++)
        {
            capa[i] = sc.NextLong();
        }

        long min = capa.Min();

        long answer = 5;

        answer += (n - 1) / min;

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 13268
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read))
         ;; a . b
         (seq (make-array n :element-type '(cons uint32 uint32))))
    (dotimes (i n)
      (setf (aref seq i) (cons (read-fixnum) (read-fixnum))))
    (setf seq (sort seq #'> :key #'cdr))
    (let ((current #xffffffff))
      (sb-int:dovector (pair seq)
        (let ((a (car pair))
              (b (cdr pair)))
          (setq current (min current b))
          (decf current a)))
      (if (>= current 0)
          (write-line "Yes")
          (write-line "No")))))

#-swank(main)


Measured memory_bytes: 22500
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;

alias sread = () => readln.chomp();
alias Point2 = Tuple!(long, "y", long, "x");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

void maxAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) max(dst, src);
}

void main()
{
    auto aa = new bool[long][](3);
    foreach (n; [1, 3, 5, 7, 8, 10, 12])
        aa[0][n] = true;
    foreach (n; [4, 6, 9, 11])
        aa[1][n] = true;
    aa[2][2] = true;

    long x, y;
    scan(x, y);

    foreach (a; aa)
    {
        if (x in a && y in a)
        {
            writeln("Yes");
            return;
        }
    }
    writeln("No");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m;
int f;
int sol;
struct p
{
    int x,y,t;
}p0;
char g[55][55];
queue<p>Q;
void bfs(p p_)
{
    for(int i=0;i<4;i++)
    {
        p0=(p){p_.x+dx[i],p_.y+dy[i],p_.t+1};
        if(p0.x>=0&&p0.y>=0&&p0.x<n&&p0.y<m)
        {
            if(g[p0.x][p0.y]=='.')
            {
                g[p0.x][p0.y]='#';
                Q.push(p0);
                if(p0.x==n-1&&p0.y==m-1)
                {
                    sol=1;
                    f=p0.t;

                }

            }

        }
    }
}
main()
{
    while(cin>>n>>m)
    {
        sol=0;
        while(!Q.empty())Q.pop();
        int c=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='#')c++;
            }

        Q.push((p){0,0,0});
        while(!Q.empty()){bfs(Q.front());Q.pop();}
        if(sol==1)cout<<n*m-c-f-1<<endl;
        else cout<<-1<<endl;
        //sol==0 ? cout<<-1<<endl : cout<<n*m-c-f-1<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool check(int a,bool like[]){
    while(a>0){
        if(!like[a%10]) return false;
        a/=10;
    }
    return true;
}
int main(){
	int n,k;
	cin>>n>>k;
	int a[k];
	bool like[10];
	for(int i=0;i<10;i++){
		like[i]=true;
	}
	for(int i=0;i<k;i++){
		cin>>a[i];
		like[a[i]]=false;
	}
	for(int i = n;true;i++){
        if(check(i,like)){
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
N = input()
N = N[::-1]+"0"
ans = 0
up = 0
for i,n in enumerate(N):
    d = int(n)+up
    if 5 < d or (d == 5 and i < len(N)-1 and int(N[i+1]) >= 5):
        ans += (10-d)
        up = 1
    else:
        ans += d
        up = 0
print(ans)


Measured memory_bytes: 11176
#include <iostream>

int main()
{
  int a,b,c;

  std::cin>>a>>b>>c;

  if(a<b&&b<c)
    {
      std::cout<<"Yes"<<std::endl;
    }
  else
    {
      std::cout<<"No"<<std::endl;
    }
  return 0;
}



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

int main(){

    int H=1,W=1;
cin >> H >> W;


while(H>0&&W>0){

for (int a=1;a<=W;a++){
cout << '#';
}

cout << endl;

for(int n=2;n<=H-1;n++){
        cout << '#';
    for (int m=1;m<=W-2;m++){
        cout << '.';
    }
    for (int c=W-1;c<W;c++){
        cout << '#';
    }
cout << endl;
}

for (int a=1;a<=W;a++){
cout << '#';
}

cout << endl;
cout << endl;
cin >> H >> W;

}

return 0;

}


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

int main()
{
    int N;
    cin >> N;
    string str = to_string(N);
    int sum = 0;
    int i = 0;
    while (str[i] != '\0')
    {
        sum += str[i] - '0';
        i++;
    }
    if ((N % sum) == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>


typedef struct tree_t{
	int parent;
	int left;
	int right;
} TREE_T;

TREE_T *TREE;


int n;
int COUNT;

void Preorder(int soeji)
{
	printf(" %d", soeji);
	COUNT++;
	if(n == COUNT){
		printf("\n");
		return;
	}

	if(TREE[soeji].left != -1)
		Preorder(TREE[soeji].left);

	if(TREE[soeji].right != -1)
	Preorder(TREE[soeji].right);
}


void Inorder(int soeji)
{
	if(TREE[soeji].left != -1)
		Inorder(TREE[soeji].left);

	printf(" %d", soeji);
	COUNT++;
	if(n == COUNT){
		printf("\n");
		return;
	}

	if(TREE[soeji].right != -1)
		Inorder(TREE[soeji].right);
}


void Postorder(int soeji)
{
	if(TREE[soeji].left != -1)
		Postorder(TREE[soeji].left);

	if(TREE[soeji].right != -1)
		Postorder(TREE[soeji].right);

	printf(" %d", soeji);
	COUNT++;
	if(n == COUNT){
		printf("\n");
		return;
	}
}


int main()
{
	int id;
	int left, right;
	int root;
	int i;

	scanf("%d", &n);

	TREE = (TREE_T *)malloc(sizeof(TREE_T) * n);

	for(i = 0; i < n; i++)
		TREE[i].parent = -1;

	for(i = 0; i < n; i++){
		scanf("%d %d %d", &id, &left, &right);
		TREE[id].left = left;
		TREE[id].right = right;

		TREE[left].parent = id;
		TREE[right].parent = id;
	}

	// 根の番号を求める
	i = -1;
	while(TREE[++i].parent != -1);
	root = i;

	// 表示
	COUNT = 0;
	printf("Preorder\n");
	Preorder(root);

	COUNT = 0;
	printf("Inorder\n");
	Inorder(root);

	COUNT = 0;
	printf("Postorder\n");
	Postorder(root);

	return 0;
}


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

#define ll long long 
using namespace std;
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    ll a,b,c=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(a==0){
            c=0;
            break;
        }
        if(a>1000000000000000000/c)
        c=-1;
        if(c!=-1)
        c=c*a;
        
    }
    cout<<c;
    return 0;
}

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

using namespace std;

int64_t N, M;
vector<int64_t> a;

int64_t solve_brute() {
  vector<int64_t> a2;
  a2.reserve(N * N);
  for (int64_t n1 : a) {
    for (int64_t n2 : a) {
      a2.push_back(n1 + n2);
    }
  }
  sort(a2.rbegin(), a2.rend());
  return accumulate(a2.begin(), a2.begin() + M, 0LL);
}

int64_t solve() {
  vector<int64_t> integral(N + 1);
  for (int i = 0; i < N; ++i) {
    integral[i + 1] = integral[i] + a[i];
  }

  int64_t left = 0;
  int64_t right = a.back() * 2 + 1;
  int64_t cnt;
  while (left + 1 < right) {
    cnt = 0;
    auto mid = (left + right) / 2;
    for (int i = 0; i < N; ++i) {
      auto diff = mid - a[i];
      auto it =
          upper_bound(a.rbegin(), a.rend(), diff, greater<int64_t>{}).base();
      cnt += a.end() - it;
      if (M < cnt)
        break;
    }
    if (M <= cnt) {
      left = mid;
    } else {
      right = mid;
    }
  }

  cnt = 0;
  int64_t score = 0;
  for (int i = 0; i < N; ++i) {
    auto diff = left - a[i];
    auto it =
        upper_bound(a.rbegin(), a.rend(), diff, greater<int64_t>{}).base();
    cnt += a.end() - it;
    score += a[i] * (a.end() - it);
    score += integral.back() - integral[it - a.begin()];
  }

  score -= (cnt - M) * left;

  return score;
}

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

  cin >> N >> M;
  a.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());

  // cerr << solve_brute() << endl;
  cout << solve() << endl;
}


Measured memory_bytes: 1792
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
Arr.forEach(function(v){
   var cntA=0;
   var cntB=0;
   for(var i=0;i<v.length-2;i++){
      var str=v[i]+v[i+1]+v[i+2];
      if(str=="JOI")cntA++;
      if(str=="IOI")cntB++;
   }
   console.log(cntA);
   console.log(cntB);
});

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

using namespace std;

int main(){
	int a,b;
	std::cin>>a;
	std::cin>>b;
	if (a+b == 3){
		std::cout<<3;
	}
	else if(a+b == 4)
    {
        std::cout<<2;
    }
    else if(a+b == 5)
    {
        std::cout<<1;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        string[] cin = Console.ReadLine().Split();
        int n = int.Parse(cin[0]);
        int a = int.Parse(cin[1]);
        int b = int.Parse(cin[2]);
        Console.WriteLine(Math.Min(a * n, b));
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using hset = unordered_set<T>;
template<class Key, class T> using hmap = unordered_map<Key, T>;
 
map<char, int> news = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
 
int main() {
    int N, M, I, x, y;
    char d;
    hset<int> st;
    while (cin >> N) {
        st.clear();
        if (N == 0) break;
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            st.insert(y*21 + x);
        }
 
        cin >> M;
        x = 10; y = 10;
        for (int i = 0; i < M; i++) {
            cin >> d >> I;
            for (int j = 0; j < I; j++) {
                x += dx[news[d]];
                y += dy[news[d]];
                st.erase(y*21 + x);
            }
        }
        if (st.empty()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
 
    return 0;
}

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

int main() {
  int A, B, i, sum;
  cin >> A >> B;
  i = A;
  sum = 0;
  while (i <= B) {
    if (i%10 == i/10000 && i/10%10 == i/1000%10) sum++;
    i++;
  }
  cout << sum <<endl;
}

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

int main() {
  string S,T,U;
  int A,B;
  cin >> S >> T >> A >> B >> U ;
  if(U==S){
    cout << A-1 << " " << B << endl;
  }
  else{
   cout << A << " " << B-1 << endl;
  }
  }


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define sp cout<<"---------------------------------------------------"<<endl
int dp[110][110][310],w[110],v[110];
int main(){
      int n,m,i,j,k;
      cin>>n>>m;
      for(i=1;i<=n;i++)
        scanf("%d%d",&w[i],&v[i]);
      for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
          for(k=0;k<=3*i;k++){
          	dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
            if(k>=w[i]-w[1])
			  dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-(w[i]-w[1])]+v[i]);
		  }
	  int ans=0;
	  for(i=1;i<=n;i++)
	    for(j=0;j<=i*3;j++)
	      if((long long)i*w[1]+j<=(long long)m)
	        ans=max(ans,dp[n][i][j]);
	  cout<<ans<<endl;
	  return 0;
}


Measured memory_bytes: 12672
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <iostream>
#include <cassert>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; --i)
#define rvc(i, S) for (int i = 0; i < S.size(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> VI;

const int N=100005;
int n,m,in[N],qu[N],hd,tl,fa[N];
VI to[N];

int main(){
    cin>>n>>m;
    rep(i,1,n+m-1){
        int a,b;
        cin>>a>>b;
        to[a].pb(b);
        ++in[b];
    }
    rep(i,1,n)if(!in[i]){
        qu[hd=0]=i;
        tl=1;
        break;
    }
    while(hd!=tl){
        int x=qu[hd++];
        rvc(i,to[x]){
            --in[to[x][i]];
            if(in[to[x][i]]==0){
                fa[to[x][i]]=x;
                qu[tl++]=to[x][i];
            }
        }
    }
    rep(i,1,n)printf("%d\n",fa[i]);
    return 0;
}


Measured memory_bytes: 7424
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit
#include <cstdio>	// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define DEBUG 0

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
string FILE_NAME = "testcase.best_pizza";
string NAME;
string itos (int n )
{
	stringstream ss;
	ss << n;

	return ss.str();
}

int main()
{
//	cut here before submit 
#if DEBUG
	NAME = FILE_NAME;
	int CNT = 1;
	NAME += itos (CNT );
	while (freopen (NAME.c_str() , "r", stdin ) != NULL ) {
#endif
	int n, a, b;
	scanf ("%d", &n );
	scanf ("%d %d", &a, &b );
	int c;
	scanf ("%d", &c );
	vector<int> d (n, 0 );
	rep (i, n ){
		scanf ("%d", &d[i] );
	} // end rep
	sort (ALL (d ), greater<int>() );
	double res = (double)c/(double)a;
	int	sumc = a;
	int sumd = c;
	rep (i, n ){
		sumc += b;
		sumd += d[i];
		double curr = (double)sumd/(double)sumc;
		res = max (res, curr );
	} // end rep
	printf ("%d\n", (int)res );

#if DEBUG
	CNT++;	// cut here before submit
	NAME = FILE_NAME;
	NAME += itos (CNT );
	} // end loop; cut here before submit
#endif			
	return 0;
}

Measured memory_bytes: 1232
//
//  main.cpp
//  temp
//
//  Created by 松本拓真 on 2018/02/25.
//  Copyright © 2018年 TakumaMatsumoto. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int h,w;
const char white='.', black='#';
int dh[4]={1,0,-1,0};
int dw[4]={0,1,0,-1};

int main(int argc, const char * argv[]) {
    // insert code here...
    
    cin>>h;cin>>w;
    
    char grid[h][w];
    int map[h][w];
    int nW=0;
    for (auto i=0;i<h;i++) {
        for (auto j=0;j<w;j++) {
            cin>>grid[i][j];
            if (grid[i][j]==white) nW++;
            map[i][j]=-1;
        }
    }
    map[0][0]=1;
    pair<int, int> p(0,0);
    deque<pair<int,int>> que; que.push_back(p);
    while (!que.empty()) {
        auto Q = que.front(); que.pop_front();
        if (Q.first==h-1 && Q.second==w-1) break;
        for (auto i=0;i<4;i++) {
            int y=Q.first+dh[i], x=Q.second+dw[i];
            if (y>=0&&x>=0&&y<h&&x<w&&
                grid[y][x]==white&&
                map[y][x] == -1) {
                que.push_back(pair<int,int>(y,x));
                map[y][x]=map[Q.first][Q.second]+1;
            }
        }
    }
    
    auto goal = map[h-1][w-1];
    cout << (goal != -1 ? nW-goal : -1);
    
    
    return 0;
}



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


int main(){
int x;
cin >> x;
int ans ;

rep(i,x){
        if((i+1)*(i+2)/2 >= x){
        ans = i+1;
        break;
        }
    }



cout << ans << endl;
}

Measured memory_bytes: 256
while True:
    m,f,r = map(int,input().split())
    if m == f == r == -1:
        break
    elif m == -1 or f == -1:
        print('F')
        continue
    if m+f >= 80:
        print('A')
    elif 65 <= m+f <80:
        print('B')
    elif 50 <= m+f < 65:
        print('C')
    elif 30 <= m+f < 50:
        if r >= 50:
            print('C')
        else:
            print('D')
    else:
        print('F')


Measured memory_bytes: 5596
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define scanf_s scanf
#define printf_s printf

class Node {
public:
	int location;
	int p, l, r;
	Node() :p{ -1 }, l{ -1 }, r{ -1 }{

	}
};

class Point {
public:
	int id, x, y;
	Point() {}
	Point(int id, int x, int y) :id{ id }, x{ x }, y{ y }{

	}
	bool operator<(const Point& p)const {
		return id < p.id;
	}

	void print() { printf_s("%d\n", id); }
};

static const int MAX = 1000000;
static const int NIL = -1;

int N;
Point P[MAX];
Node T[MAX];
int np;

bool lessX(const Point& a, const Point& b) { return a.x < b.x; }


bool lessY(const Point& a, const Point& b) { return a.y < b.y; }


int makeKDTree(int l, int r, int depth) {
	if (!(l < r))return NIL;
	int mid = (l + r) / 2;
	int t = np++;
	if (depth % 2 == 0)sort(P + l, P + r, lessX);
	else sort(P + l, P + r, lessY);
	T[t].location = mid;
	T[t].l = makeKDTree(l, mid, depth + 1);
	T[t].r = makeKDTree(mid + 1, r, depth + 1);

	return t;
}

void find(int v, int sx, int tx, int sy, int ty, int depth, vector<Point>& ans) {
	int x = P[T[v].location].x;
	int y = P[T[v].location].y;

	if (sx <= x && x <= tx && sy <= y && y <= ty)ans.push_back(P[T[v].location]);

	if (depth % 2 == 0) {
		if (T[v].l != NIL) {
			if (sx <= x)find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
		}
		if (T[v].r != NIL) {
			if (x <= tx)find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
		}
	}
	else {
		if (T[v].l != NIL) {
			if (sy <= y)find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
		}
		if (T[v].r != NIL) {
			if (y <= ty)find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
		}
	}
}

int main() {
	int x, y;
	scanf_s("%d", &N);
	for (int i = 0; i < N; i++) {

		scanf_s("%d %d", &x, &y);
		P[i] = Point(i, x, y);
		T[i].l = T[i].r = T[i].p = NIL;
	}
	np = 0;
	int root = makeKDTree(0, N, 0);

	int q;
	scanf_s("%d", &q);
	int sx, tx, sy, ty;
	vector<Point> ans;
	for (int i = 0; i < q; i++) {
		scanf_s("%d %d %d %d", &sx, &tx, &sy, &ty);
		ans.clear();
		find(root, sx, tx, sy, ty, 0, ans);
		sort(ans.begin(), ans.end());
		for (int j = 0; j < ans.size(); j++) {
			ans[j].print();
		}
		printf_s("\n");
	}
	return 0;
}



Measured memory_bytes: 24436
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace AtCoderABC122
{
    class Program
    {
        public static void Main(string[] args)
        {
            string b = Console.ReadLine();
            if (b == "A") Console.WriteLine("T");
            if (b == "T") Console.WriteLine("A");
            if (b == "G") Console.WriteLine("C");
            if (b == "C") Console.WriteLine("G");
        }
    }
}

Measured memory_bytes: 11092
N = int(input().strip())
S = input().strip()

csum = {
  'R': [0]*(N+1),
  'G': [0]*(N+1),
  'B': [0]*(N+1)
}
for i, c in enumerate(S):
  for k in csum.keys():
    csum[k][i+1] = csum[k][i]
  csum[c][i+1] += 1

ans = 0
for j in range(1, N-1):
  for i in range(j):
    if S[i] == S[j]: continue
    s = set('RGB') - {S[i], S[j]}
    s = s.pop()
    diff = j-i
    cand = csum[s][-1] - csum[s][j]
    if j+diff < N and S[j+diff] == s: cand -= 1
    ans += cand
    
print(ans)


Measured memory_bytes: 74288
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
int kaijo(int n){
	int ans=1;
	for(int i=2;i<=n;i++){
		ans*=i;
		ans%=MOD;
	}
	return ans;
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
	return kaijo(a)*modpow(kaijo(a-b),MOD-2)%MOD*modpow(kaijo(b),MOD-2)%MOD;
}
int n,x,a[110];
int ans=1;
int now=0;
signed main(){
	cin>>n>>x;
	rep(i,n)cin>>a[i];
	rep(i,n){
		now+=a[i];
		if(now<=x)ans++;
	}
	cout<<ans<<endl;
	return 0;
}


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

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;

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

  string c;
  cin >> c;

  bool sorted = false;
  int check = n - 1;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (c.at(i) == 'W') {
      for (int j = check; j >= 0; j--) {
        if (j <= i) {
          sorted = true;
          break;
        }
        if (c.at(j) == 'R') {
          c.at(i) = 'R';
          c.at(j) = 'W';
          ans++;
          check = j - 1;
          break;
        }
      }
    }
    if (sorted) break;
  }

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

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

int main() {

    int a, b;
    cin >> a >> b;

    int c = min(a, b);
    int d = max(a, b);

    rep(i, d) {
        cout << c;
    }

    cout << endl;

    return 0;
}

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

int n, k;
int arr[100100], dp[100100];
bool vis[100100];

int func( int pos ) {
  if (pos == n) return 0;
  if (vis[pos]) return dp[pos];
  vis[pos] = 1;
  int res = INT_MAX;
  for (int i = 1; i <= k; ++i) {
    if (pos + i > n) break;
    res = min(res, func(pos + i) + abs(arr[pos] - arr[pos + i]));
  }
  return dp[pos] = res;
}

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

  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  cout << func(1) << endl;
  return 0;
}


Measured memory_bytes: 5888
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    int N;cin >> N;
    vector<LL> A(N+1);
    vector<LL> B(N);
    rep(i,N+1)cin >> A[i];
    rep(i,N)cin >> B[i];

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

    rep(i,N){
        LL tmp = A[i];
        if(B[i] - tmp >= 0){
            A[i] = 0;
            tmp = B[i] - tmp;
            A[i+1] = max(0LL,A[i+1]-tmp);
        }
        else{
            A[i] -= B[i];
        }
    }

    rep(i,N+1)ans -= A[i];

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;
int mod = 1000000007;

int extgcd(int a, int b, int &x, int &y) {
  int d = a;
  if (b != 0) {
    d = extgcd(b, a%b, y, x);
    y -= (a/b)*x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

int mod_inverse(int a, int m) {
  int x, y;
  extgcd(a, m, x, y);
  return (m + x%m)%m;
}

int n;
int main() {
  cin >> n;
  vector<int> a(n+1);
  bool used[n+1];
  int second;

  rep(i, n+1) {
    used[i] = false;
  }

  int dup;
  rep(i, n+1) {
    cin >> a.at(i);
    if (used[a.at(i)]) {
      second = i;
      dup = a.at(i);
    } else {
      used[a.at(i)] = true;
    }
  }

  int first;
  rep(i, n+1) {
    if (a.at(i) == dup) {
      first = i;
      break;
    }
  }

  int l = first;
  int r = n-second;
  int lr = l+r;

  vector<ll> combn1(n+2);
  vector<ll> combkm(n+2);
  vector<ll> mod_inv(n+2);
  for(int i=1; i<=n+1; i++) {
    mod_inv.at(i) = mod_inverse(i, mod);
  }

  combn1.at(0) = 1;
  combkm.at(0) = 1;
  for(int i=1; i<=n+1; i++) {
    combn1.at(i) = (combn1.at(i-1) * (n+2-i))%mod;
    combn1.at(i) *= mod_inv.at(i);
    combn1.at(i) %= mod;
    if (i>lr) {
      combkm.at(i) = 0;
    } else {
      combkm.at(i) = (combkm.at(i-1) * (lr+1-i))%mod;
      combkm.at(i) *= mod_inv.at(i);
      combkm.at(i) %= mod;
    }
  }

  for(int i=1; i<=n+1; i++) {
    ll ans = (combn1.at(i) - combkm.at(i-1) + mod)%mod;
    cout << ans << endl;
  }
}


Measured memory_bytes: 4096
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<complex>
#include<stack>
#include<cmath>
  
using namespace std;
  
#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

#define pb push_back

#define X real()
#define Y imag()
typedef complex<double> P;

class C:public P{
    public:
    double r;
    C(double x,double y,double r):P(x,y),r(r){}
    C(P p, double r):P(p),r(r){}
};


class L:public vector<P>{
	public:
	L(P a, P b){
		pb(a);pb(b);
	}
};


template<class T> T sq(T x){return x*x;}
double dot(P a, P b){return a.X*b.X + a.Y*b.Y;} 
double cross(P a,P b){return a.X*b.Y-a.Y*b.X;}
bool ccw(P a,P b,P c){return cross(b-a,c-a)>=0;}


P projection_LP(L a, P p){
	P e = (a[1]-a[0])/abs(a[1]-a[0]);
	double d = dot(p-a[0], e);
	return a[0]+d*e;
}

P refrection_LP(L a, P p){
	P b = projection_LP(a,p);
	P c = b-p;
	return p+c+c;
}

vector<P> crossP_CC(C a, C b){
	P d = b-a;
	P e = d/abs(d);
	
	double EPS = 0.0000001;
	if(abs(d)+EPS> a.r+b.r )return vector<P>();
	
	double x = abs(d)*a.r/(a.r+b.r);
	double y = sqrt(sq(a.r)-sq(x));
	
	
	P sp = a + x*e;
	vector<P> ret;
	ret.pb(sp + y*(e*P(0,1)));
	ret.pb(refrection_LP(L(a,b), ret[0]));
	return ret;
}

int main(){
	while(1){
		int n;
		cin>>n;
		if(n==0)break;
		
		vector<C> circle;
		
		rep(i,n){
			double a,b;
			scanf("%lf,%lf",&a,&b);
			circle.pb(C(P(a,b),1));
		}
		
		
		vector<P> cand;
		rep(i,n){
			reps(j,i+1,n){
				vector<P> res = crossP_CC(circle[i],circle[j]);
				rep(k,res.size()){
					cand.pb(res[k]);
				}
			}
		}
		rep(i,circle.size())cand.pb(circle[i]);
		
		int ans = 0;
		rep(i,cand.size()){
			int cnt = 0;
			rep(j,circle.size()){
				P d = cand[i]-circle[j];
				double EPS = 0.000000001;
				if(abs(d)-EPS<1)cnt++;
			}
			ans = max(ans,cnt);
		}
		
		printf("%d\n",ans);
	}
}

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

using namespace std;

#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 REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int N;
vector<V> cidx;
V c;
VL dp;

int main() {
    cin >> N;
    c.resize(N);
    cidx.resize(int(2 * 10e5));
    REP(i, N) {
        CINT(C);
        c[i] = C;
        cidx[C].push_back(i);
    }
    dp.resize(N + 1);
    dp[0] = 1;
    REP(i, N) {
        (dp[i + 1] += dp[i]) %= MOD;
        int color = c[i];
        int it =
            distance(cidx[color].begin(), lower_bound(All(cidx[color]), i));
        if(it > 0 && i - cidx[color][it - 1] > 1) {
            (dp[i + 1] += dp[cidx[color][it - 1] + 1]) %= MOD;
        }
    }
    cout << dp[N] << "\n";
    return 0;
}

Measured memory_bytes: 55680
// 未解決

#include <bits/stdc++.h>

#include <iostream>
using namespace std;

#define EACH(i, a) for (auto &&i : a)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RFOR(i, a, b) for (int i = (int)b - 1; i >= (int)a; --i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREPS(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(x) (x).begin(), (x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define debug(x) cout << #x << ": " << x << endl

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF (1L << 30)
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void pvp(T a, T b) {
  for (T i = a; i != b; ++i)
    cout << "(" << i->first << ", " << i->second << ") ";
  cout << endl;
}
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;
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}

using ll = long long;
#define int ll

//***** basic func *****//
int power_mod(int a, int b) {
  // return (a**b)%MOD (O(log b))
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res *= a;
      res %= MOD;
    }
    a *= a;
    a %= MOD;
    b >>= 1;
  }
  return res;
}

// int fact[510000], fact_inv[510000];  // n!, (n!)^-1 mod MOD
// // calc fact (in main routine)
// fact[0] = 1;
// REP(i, n) { fact[i + 1] = fact[i] * (i + 1) % MOD; }
// fact_inv[n] = power_mod(fact[n], MOD - 2);
// RREP(i, n) { fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD; }
// int comb_mod(int n, int r) {
//   return ((fact[n] * fact_inv[r]) % MOD * fact_inv[n - r] % MOD);
// }

//**********

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

  int N, C;
  int D[30][30];    // 0-origin
  int c[500][500];  // 0-origin
  cin >> N >> C;
  REP(i, C) {
    REP(j, C) { cin >> D[i][j]; }
  }
  REP(i, N) {
    REP(j, N) { cin >> c[i][j]; }
  }

  int c_count[3][30];  // pos 0, 1, 2
  MEMSET(c_count, 0);
  // debug(c_count[0][0]);

  REP(i, N) {
    REP(j, N) { c_count[(i + j) % 3][c[i][j] - 1] += 1; }
  }

  int ans = INF;

  REP(i, C) {
    REP(j, C) {
      REP(k, C) {
        if (i == j || j == k || k == i) {
          continue;
        } else {
          int temp_ans = 0;
          REP(l, C) {
            temp_ans += c_count[0][l] * D[l][i];
            temp_ans += c_count[1][l] * D[l][j];
            temp_ans += c_count[2][l] * D[l][k];
          }
          chmin(ans, temp_ans);
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
};


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

using namespace std;

int main(){
  int e[12];
  for(int i=0;i<12;++i) cin >> e[i];
  sort(e,e+12);
  bool flag=true;
  for(int i=0;i<3;++i) {
    if(!(e[4*i]==e[4*i+1]&&e[4*i+1]==e[4*i+2]&&
	 e[4*i+2]==e[4*i+3]&&e[4*i+3]==e[4*i])) flag=false;
  }
  cout << (flag?"yes":"no") << endl;
  
  return 0;
}



Measured memory_bytes: 3140
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int D, G;
	cin >> D >> G;
	vector<int> p(D), c(D);
	for (int i = 0; i < D; ++i) {
		cin >> p[i] >> c[i];
	}
	int ans = 1 << 30;
	for (int i = 0; i < 1 << D; ++i) {
		int sc = G, sol = 0;
		for (int j = 0; j < D; ++j) {
			if ((i >> j) & 1) {
				sol += p[j];
				sc -= p[j] * 100 * (j + 1) + c[j];
			}
		}
		for (int j = D - 1; j >= 0 && sc > 0; --j) {
			if ((i >> j) & 1) continue;
			if (sc <= p[j] * 100 * (j + 1)) {
				int num = (sc + 100 * (j + 1) - 1) / (100 * (j + 1));
				sc -= num * 100 * (j + 1);
				sol += num;
			}
			else {
				sol += p[j];
				sc -= p[j] * 100 * (j + 1);
			}
		}
		if (sc <= 0) ans = min(ans, sol);
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

ll dp[200][200];
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() { 
  int n;
  cin >> n;
  Fill(dp,INT_MAX);
  vl r(n+1),c(n);
  rep(i,n) cin >> r[i] >> r[i+1];
  rep(i,n) dp[i][i] = 0;
  

  for(int w = 1;w<n;w++){
    for(int i =0;i+w<n;i++){
      int j = i+w;
      for(int k=i;k<j;k++){
        ll prod = r[i]*r[k+1]*r[j+1];
        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+prod);
      }
    }
  }
  cout<<dp[0][n-1]<<endl;
  return 0;
}


Measured memory_bytes: 3416
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 区間加算にも対応した BIT
template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

using pll = pair<long long, long long>;
int N;
long long D, A;
vector<long long> X, H;

long long solve() {
    // モンスターを X が小さい順に
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return X[i] < X[j]; });
    vector<long long> nX(N), nH(N);
    for (int i = 0; i < N; ++i) nX[i] = X[ids[i]], nH[i] = H[ids[i]];
    X = nX, H = nH;

    // BIT で処理していく
    BIT<long long> bit(N+10);
    for (int i = 0; i < N; ++i) bit.add(i+1, i+2, H[i]); // 初期化
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        long long cur = bit.sum(i+1, i+2);
        if (cur <= 0) continue;

        // モンスター i を倒すのに必要な回数
        long long need = (cur + A - 1) / A;

        // X[i] を左端とした爆発が届く範囲を求める
        long long right = X[i] + D * 2;
        int id = upper_bound(X.begin(), X.end(), right) - X.begin();

        // 爆発させる
        bit.add(i+1, id+1, -need * A);
        res += need;
    }
    return res;
}

int main() {
    cin >> N >> D >> A;
    X.resize(N); H.resize(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> H[i];
    cout << solve() << endl;
}

Measured memory_bytes: 13512
n, k = (int(i) for i in input().split())  
s=str(input())
if k == n:
    r=s[0:(k-1)] + s[n-1].lower()
elif k == 1:
    r=s[0].lower() + s[1:n]
else:
    r=s[0:(k-1)] + s[k-1].lower() + s[k:n]
print(r)

Measured memory_bytes: 3060
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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;
}

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

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

	string n;
	ll k;
	cin >> n>>k;
	Array d(k, 0);
	Array b(10, true);
	REP(i, k) {
		cin >> d[i];
		b[d[i]]=false;
	}

	Array v;
	REP(i, 10) {
		if (b[i] == true) {
			v.push_back(i);
		}
	}

	Array flag(n.size(), false);
	Array ans(n.size(), 0);
	REP(i,n.size()) {		
		ll now = n[i] - '0';
		auto it = lower_bound(all(v), n[i] - '0');
		if (it==v.end()) {
			for (int j = i - 1; j >= 0; j--) {
				auto it = upper_bound(all(v), n[j] - '0');
				if (it != v.end()) {
					ans[j] = *it;
					for (int k = j; k < n.size(); k++) {
						ans[k] = v[0];
					}
					for (auto an : ans) {
						cout << an;
					}
					return 0;
				}
			}
			//cout << "b";
			cout << *(upper_bound(all(v), 0));
			//cout << "c";
			REP(i, n.size())cout << v[0];
			return 0;
		}
		else if(*it!=now){
			ans[i] = *it;
			//cout << "a"<<*it << endl;
			for (ll j = i + 1; j < n.size(); j++) {
				ans[j] = v[0];
			}
			break;
		}
		else {
			ans[i] = *it;
		}
	}

	for (auto an : ans) {
		cout << an;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define rrep(i,n) for (int i = (n - 1);i >= 0;i--)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    cout << max(a+b,max(a-b,a*b)) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<memory>
using namespace std;

struct Node
{
    int key;
    Node *next, *prev;
};

class LinkedList {
public:
    Node *nil;

    LinkedList() {
        nil = new Node; 
        nil->next = nil;
        nil->prev = nil;
    }

    ~LinkedList() {
        delete nil;
    }

    void printList() {
        Node *cur = nil->next;
        bool isFirst = true;
        while(true) {
            if (cur == nil) {
                break;
            }
            if (!isFirst) {
                printf(" ");
            }
            printf("%d", cur->key);
            cur = cur->next;
            isFirst = false;
        }
        printf("\n");
    }

    void insert(int key) {
        Node *newnode = new Node;
        newnode->key = key;
        newnode->next = nil->next;
        nil->next->prev = newnode;
        nil->next = newnode;
        newnode->prev = nil;
    }

    void deleteFirst() {
        deleteNode(nil->next);
    }

    void deleteLast() {
        deleteNode(nil->prev);
    }

    void deleteKey(int key) {
        deleteNode(findFirst(key));
    }

private: 
    Node* findFirst(int key) {
        Node *cur = nil->next;
        while (cur != nil && cur->key != key) {
            cur = cur->next;
        }
        return cur;
    }

    void deleteNode(Node *deleted) {
        if (deleted != nil) {
            deleted->prev->next = deleted->next;
            deleted->next->prev = deleted->prev;
            delete deleted;
        }
    }
};


int main() {
    int key, n, i;
    char command[20];
    scanf("%d", &n);
    
    unique_ptr<LinkedList> list(new LinkedList);
    for(i = 0; i < n; i++) {
        scanf("%s%d", command, &key);
        if (strcmp(command, "insert") == 0) {
            list->insert(key);
        } else if (strcmp(command, "delete") == 0) {
            list->deleteKey(key);
        } else if (strcmp(command, "deleteFirst") == 0) {
            list->deleteFirst();
        } else if (strcmp(command, "deleteLast") == 0) {
            list->deleteLast();
        }
    }

    list->printList();
}



Measured memory_bytes: 33840
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <numeric>
#include <iomanip>
#define ll long long
#define pi 3.14159265358979323846
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, 1, 0, -1};
/*
 vector<vector<ll>> g(n+1);
    for(ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll> dist(n+1, -1);
    queue<ll> que;
    que.push(1);
    dist[1] = 0;
    while(!que.empty()){
        ll v = que.front();
        que.pop();
        for(ll nv : g[v]){
            if(dist[nv]!=-1) continue;
            dist[nv] = dist[v]+1;
            que.push(nv);
        }
    }
*/
ll n;
vector<string> ans;
string c = "abcdefghijk";
void func(string s){
    ll MAX = 0;
    for(ll i = 0; i < n; i++){
        char a = s[i];
        ll b = a-96;
        MAX = max(MAX, b);
    }
    if(s.length()<n){
        for(ll i = 0; i <= MAX; i++){
            string t = s+c[i];
            func(t);
        }
    }
    if(s.length()==n)
        ans.push_back(s);
}
int main(){
    cin >> n;
    string t = "a";
    func(t);
    for(ll i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 7796