Cerinta completa

Given two numbers and . indicates the number of elements in the array and indicates number of queries. You need to perform two types of queries on the array .

You are given queries. Queries can be of two types, type 1 and type 2.

  • Type 1 queries are represented as 1 i j : Modify the given array by removing elements from to and adding them to the front.

  • Type 2 queries are represented as 2 i j : Modify the given array by removing elements from to and adding them to the back.

Your task is to simply print of the resulting array after the execution of queries followed by the resulting array.

Note While adding at back or front the order of elements is preserved.

Input Format

First line consists of two space-separated integers, and .
Second line contains integers, which represent the elements of the array.
queries follow. Each line contains a query of either type 1 or type 2 in the form

Constraints


Output Format

Print the absolute value i.e. in the first line.
Print elements of the resulting array in the second line. Each element should be seperated by a single space.

Sample Input

8 4
1 2 3 4 5 6 7 8
1 2 4
2 3 5
1 4 7
2 1 4

Sample Output

1
2 3 6 5 7 8 4 1

Explanation

Given array is .
After execution of query , the array becomes .
After execution of query , the array becomes .
After execution of query , the array becomes .
After execution of query , the array becomes .
Now is i.e. and the array is

Limbajul de programare folosit: cpp14

Cod:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int Random() { return rand() << 15 | rand(); }

struct item {
    int prior, value, cnt;
    item *left, *right;
    item(int val = 0): value(val), prior(Random()), cnt(0), left(nullptr), right(nullptr) {}
};

int n, m;
item *tr;

int Count(item * p) { return p? p->cnt: 0; }

void Update(item * p) { if (p) p->cnt = Count(p->left) + Count(p->right) + 1; }

void Merge(item* &p, item *l, item *r)
{
    if (!l || !r) p = l? l: r;
    else if (l->prior > r->prior) Merge(l->right, l->right, r), p = l;
    else Merge(r->left, l, r->left), p = r;
    Update(p);
}

void Split(item *p, item* &l, item* &r, int key, int add = 0)
{
    if (!p) { l = r = nullptr; return; }
    int curkey = add + Count(p->left);
    if (key <= curkey) Split(p->left, l, p->left, key, add), r = p;
    else Split(p->right, p->right, r, key, curkey + 1), l = p;
    Update(p);
}

void Print(item *tr)
{
    if (tr) {
        Print(tr->left);
        printf("%d ", tr->value);
        Print(tr->right);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        int a; scanf("%d", &a);
        Merge(tr, tr, new item(a));
    }
    while (m--) {
        int typ, l, r; scanf("%d %d %d", &typ, &l, &r); l--, r--;
        item *p1, *p2; Split(tr, tr, p2, r + 1); Split(tr, p1, tr, l);
        if (typ == 1) { Merge(tr, tr, p1); Merge(tr, tr, p2); }
        else { Merge(tr, p2, tr); Merge(tr, p1, tr); }
    }
    if (n == 1) printf("0n");
    else {
        item *p1, *p2; Split(tr, tr, p2, n - 1); Split(tr, p1, tr, 1);
        printf("%d\n", abs(p1->value - p2->value));
        Merge(tr, p1, tr); Merge(tr, tr, p2);
    }
    Print(tr);
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464652998

Link challenge: https://www.hackerrank.com/challenges/array-and-simple-queries/problem

Array and simple queries