DMOPC '21 Contest 7 P2 - Knitting Scarves

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int n, q;
    9    cin >> n >> q;
    10    vector<int> next(n + 1), pre(n + 1);
    11    for(int i = 1; i <= n; i++){
    12        if(i != n) next[i] = i + 1;
    13        else next[i] = 0;
    14        pre[i] = i - 1;
    15    }
    16    int head = 1;
    17    while(q--){
    18        int l, r, k;
    19        cin >> l >> r >> k;
    20        if(l == r){
    21            //detatch l
    22            int x = pre[l], y = next[l];
    23            if(x) next[x] = y; // set x - 1 = x + 1
    24            else head = y; 
    25            if(y) pre[y] = x; 
    26            //insert
    27            if(k == 0){ // move to front
    28                pre[l] = 0;
    29                next[l]= head;
    30                if(head) pre[head] = l;
    31                head = l;
    32            } else { // after k
    33                int next_k = next[k];
    34                next[k] = l;
    35                pre[l] = k;
    36                next[l] = next_k;
    37                if(next_k) pre[next_k] = l;
    38            }
    39        } else {
    40            //detached [l, r]
    41            int prev_l = pre[l], next_r = next[r];
    42            if(prev_l) next[prev_l] = next_r;
    43            else head = next_r;
    44            if(next_r) pre[next_r] = prev_l;
    45            //insert
    46            if(k == 0){
    47                pre[l] = 0;
    48                next[r] = head;
    49                if(head) pre[head] = r;
    50                head = l;
    51            } else {
    52                int next_k = next[k];
    53                next[k] = l;
    54                pre[l] = k;
    55                next[r] = next_k;
    56                if(next_k) pre[next_k] = r;
    57            }
    58        }
    59    }
    60    for(int i = head; i; i = next[i]){
    61        cout << i << (next[i] ? " " : "\n");
    62    }
    63    return 0;
    64}