C - Snake Queue
Source: atcoder
Difficulty: 300

Problem Statement
There is a queue of snakes. Initially, the queue is empty.
You are given
Q
queries, which should be processed in the order they are given. There are three types of queries:
Type
1
: Given in the form
1 l
. A snake of length
l
is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is
0
; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
Type
2
: Given in the form
2
. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let
m
be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by
m
.
Type
3
: Given in the form
3 k
. Output the head coordinate of the snake that is
k
-th from the front of the queue. It is guaranteed that there are at least
k
snakes in the queue at this time.
Constraints
1 \leq Q \leq 3 \times 10^{5}
For a query of type
1
,
1 \leq l \leq 10^{9}
For a query of type
2
, it is guaranteed that the queue is not empty.
For a query of type
3
, let
n
be the number of snakes in the queue, then
1 \leq k \leq n
.
All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Here,
\text{query}_i
is the
i
-th query in one of the following forms:
1
l
2
3
k
Output
Let
q
be the number of queries of type
3
. Print
q
lines. The
i
-th line should contain the answer to the
i
-th type
3
query.
Sample Input 1
7
1 5
1 7
3 2
1 3
1 4
2
3 3
Sample Output 1
5
10
1st query: A snake of length
5
is added to the queue. Since the queue was empty, the head coordinate of this snake is
0
.
2nd query: A snake of length
7
is added to the queue. Before adding, the last snake has head coordinate
0
and length
5
, so the newly added snake’s head coordinate is
5
.
3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are
0, 5
, so output
5
.
4th query: A snake of length
3
is added to the queue. Before adding, the last snake has head coordinate
5
and length
7
, so the new snake’s head coordinate is
12
.
5th query: A snake of length
4
is added to the queue. Before adding, the last snake has head coordinate
12
and length
3
, so the new snake’s head coordinate is
15
.
6th query: The snake at the front leaves the queue. The length of the snake that left is
5
, so the head coordinate of each remaining snake decreases by
5
. The remaining snake’s head coordinate becomes
0, 7, 10
.
7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are
0, 7, 10
, so output
10
.
Sample Input 2
3
1 1
2
1 3
Sample Output 2
It is possible that there are no queries of type
3
.
Sample Input 3
10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2
Sample Output 3
20
5

C++ solution:
#include <bits/stdc++.h>
using namespace std;




// -------# Short Code Defines #-----------------

#define endl '\n'

#define ll long long
#define ld long double

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



// -------# Constants #---------------------------

#define PI 3.1415926535897932384626433832795l 
#define mod 1000000007

const int N2 = 1e2 + 5;
const int N3 = 1e3 + 5;
const int N5 = 1e5 + 5;
const int N6 = 1e6 + 5;
const int INF = 1e9 + 5;
const ll INFLL = 1e18 + 5;

const int NCRN = 1e1 + 5;
const int SIEVEN = 1e1 + 5;

vector<pair<int, int> > directions_8 {{-1, -1}, {1, 1}, {1, -1}, {-1, 1}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
vector<pair<int, int> >directions_4 {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};




// ------# Useful Function #-----------

ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }

string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }



// -----------# Print Functions #--------------

void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }

#define printv(a) {for (auto u: a) cout << u << " "; cout << endl; }




// ---------------# Debug #---------------------


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif




// ----------# Modular Arithmetic #-------------

int mul(int a, int b) { return (1ll * a * b) % mod; };
int add(int a, int b) { return (a + b) % mod; };
int sub(int a, int b) { return ((ll)a - (ll)b + (ll)mod) % mod; }
int binExp(int a, int b) { int answer = 1; while(b) { if(b & 1) answer = mul(answer, a);b >>= 1; a = mul(a, a);} return answer; };
int divi(int a, int b) { return (mul(a, binExp(b, mod - 2))); };




// ----------# Number Theory #--------------------

ll gcd(ll a, ll b) { return(b ? __gcd(a,b) : a); };
ll lcm(ll a,ll b) { return (a / gcd(a,b) * b); };



// -------------# Prime Sieve #-------------------



// -------------# Combinatorics #-----------------


int FACT[NCRN];
int IFACT[NCRN];

void ncrInit() {
    FACT[0] = 1;
    for(int i = 1; i < NCRN; i ++) FACT[i] = mul(i, FACT[i - 1]);
    IFACT[NCRN - 1] = binExp(FACT[NCRN - 1], mod - 2);
    for(int i = NCRN - 2; i >= 0; i --) IFACT[i] = mul(IFACT[i + 1], i + 1);
    return;    
}

int ncr(int n, int r) { if(r > n) return 0; return (mul(FACT[n], mul(IFACT[n - r], IFACT[r]))); };
ll ncrll(ll n, ll r) { if(r > n) return 0; if(r == 0) return 1; r = min(r, n - r); ll a = 1, b = 1; while(r) { a = a * n; b = b * r; ll int g = gcd(a, b); a /= g; b /= g; n --; r --; } return a; }

int npr(int n, int r) { if(r > n) return 0; return (mul(FACT[n], IFACT[n - r])); };
ll nprll(ll n, ll r) { if(r > n) return 0; r = min(r, n - r); if(r == 0) return 1; ll ans = 1;while(r) { ans = ans * n; n --; r --; }; return ans; }



// ----------------------------------------------

// ---------------- Precomputation ---------------




void init() {
    
    
    
    
    return;
}

// -----------------------------------------------











void solve() {
    

    int q;
    cin >> q;

    vector<long long> prefix = {0};
    int removed = 0;

    while(q --) {
        int type; cin >> type;

        if(type == 1) {
            int l; cin >> l;
            prefix.push_back(prefix.back() + l);
        } else if(type == 2) {
            removed ++;
        } else {
            int k; cin >> k;
            cout << prefix[k + removed - 1] - prefix[removed] << endl;
        }
    }
    
    return; 
}



int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    init();

    int t = 1;
    // cin >> t;
    
    int currCase = 1;
    
    while(t --) {
        // cout << "-------# test : " << currCase << " #-------------" << endl;
        
        
        solve();
        
        currCase ++;
    }



return 0;
}

Go solution:
package main

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

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

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

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	Q := getI()

	remove := 0
	snake := []int{}
	for i := 0; i < Q; i++ {
		t := getI()
		switch t {
		case 1:
			x := getI()
			if len(snake) != 0 {
				x += snake[len(snake)-1]
			}
			snake = append(snake, x)
		case 2:
			remove = snake[0]
			snake = snake[1:]
		case 3:
			k := getI()
			if k == 1 {
				out(0)
			} else {
				k = max(0, k-2)
				out(snake[k] - remove)
			}
		}
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());

        long now = 0;
        int pastSnake = 0;
        List<Long> snake = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < q; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken();

            if (op.equals("1")) {
                long length = Long.parseLong(st.nextToken());
                snake.add(now);
                now += length;
            } else if (op.equals("2")) {
                pastSnake++;
            } else {
                int index = Integer.parseInt(st.nextToken());
                index--;
                sb.append(snake.get(pastSnake + index) - snake.get(pastSnake)).append("\n");
            }
        }

        System.out.print(sb);
    }
}

JavaScript solution:
function Main(input) {
  const l = input.trim().split('\n');
  const n = parseInt(l[0]);
  const q = l.slice(1).map(v => v.split(' ').map(v => parseInt(v)));

  const s = [0];
  let m = 0;
  let ans = [];
  for (let i = 0; i < n; i ++) {
    if (q[i][0] === 1) {
      if (s.length === 0) {
        s[0] = q[i][1];
      } else {
        s.push(s[s.length - 1] + q[i][1]);
      }
    }
    if (q[i][0] === 2) {
      m ++;
    }
    if (q[i][0] === 3) {
      ans.push(
        s[q[i][1] + m - 1] - s[m]
      );
    }
  }
  console.log(ans.join('\n'));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
q = int(input())
query = []
for i in range(q):
    query.append(list(map(int, input().split())))

head_pos = 0
snake_list = [0]
for i in range(q):
    if query[i][0] == 1:
        # 累積長
        snake_list.append(snake_list[-1] + query[i][1])

    elif query[i][0] == 2:
        # 先頭１つ後ろに
        head_pos += 1

    elif query[i][0] == 3:
        print(snake_list[head_pos + query[i][1]-1] - snake_list[head_pos])

Ruby solution:
Object.alias_method(:■, :method)

def gets(io) = (io.gets; io.readlines(chomp: true))
def output(e) = STDOUT.puts e

def main(query)
  sum = [0]
  query.each do |q|
    tmp = q.split.map(&:to_i)
    case tmp[0]
    when 1
      sum << sum[-1] + tmp[1]
    when 2
      sum.shift
    else
      output(sum[tmp[1] - 1] - sum[0])
    end
  end
end

(■(:gets) >> ■(:main)).(STDIN)