Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2368
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2368
Simulador
Por OBI - Olimpíada Brasileira de Informática 2009 
Brazil
Timelimit: 1
Um novo processador, denominado Faíska, está sendo desenvolvido para a empresa SBC. Este novo processador tem apenas duas instruções: inversão e soma, descritas a seguir.
- Inversão: dados dois endereços de memória X e Y , a operação inverte(X,Y) inverte a posição de palavras da memória de forma que
- a palavra no endereço X troca de posição com a palavra de memória da posição Y;
- a palavra no endereço X + 1 troca de posição com a palavra de memória da posição Y − 1;
- a palavra no endereço X + 2 troca de posição com a palavra de memória da posição Y − 2;
- e assim por diante, até que X ≥ Y.
- Soma: dados dois endereços de memória X e Y, a operação soma(X,Y) imprime a soma das palavras de memória entre os endereços X e Y (inclusive).
Por exemplo, se a memória contém inicialmente, a partir da primeira posição de memória (endereço igual a 1) os valores [1,2,3,4,5,6,7,8], a operação inverte(3,7) deixa a memória igual a [1,2,7,6,5,4,3,8]. Então, nesse estado, a execução de soma(1,3) produz a saída 10.
Sua tarefa é escever um programa que, dada uma sequência de instruções do Faíska, simule a execução e produza o mesmo resultado que o Faíska produziria.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).
A primeira linha da entrada contém dois números inteiros N e M, representando respectivamente o número palavras na memória (1 ≤ N ≤ 109) e o número de instruções do programa (1 ≤ M ≤ 1000). Cada uma das M linhas seguintes contém uma instrução do Faíska. Cada instrução é composta de um caratere descrevendo a instrução (‘I’ para inversão e ‘S’ para soma), seguido de um espaço, seguido de dois inteiros indicando os argumentos da instrução.
Inicialmente a configuração da memória é tal que cada palavra tem como conteúdo o seu próprio endereço. Em outras palavras, o conteúdo inicial da memória é [1,2,3,. . .,N]. Há pelo menos uma instrução soma em cada caso de teste.
Saída
Seu programa deve imprimir, na saída padrão, uma sequência de números inteiros, um em cada linha, indicando a saída gerada pelo Faíska.
| Exemplos de Entrada | Exemplos de Saída |
|
10 2 I 1 5 S 3 7 |
19 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
struct range {
ll ini, fim;
ll A, B;
range(ll _A, ll _B, ll add = 0) {
A = _A;
B = _B;
ini = add + 1;
fim = ini + abs(A - B);
}
};
vector < range> left, mid, right, S;
ll N, M;
void inverte(ll a, ll b) {
for (ll i = 0; i < S.size(); i++) {
if (S[i].fim < a) {
left.push_back(S[i]);
} else if (S[i].ini > b) {
right.push_back(S[i]);
} else {
if (S[i].A < = S[i].B) {
ll avanca = max(a - S[i].ini, 0LL);
ll recua = max(S[i].fim - b, 0LL);
range temp1(S[i].A, S[i].A + avanca - 1);
range temp2(S[i].A + avanca, S[i].B - recua);
range temp3(S[i].B - recua + 1, S[i].B);
if (S[i].A < = S[i].A + avanca - 1) left.push_back(temp1);
if (S[i].A + avanca <= S[i].B - recua) mid.push_back(temp2);
if (S[i].B - recua + 1 < = S[i].B) right.push_back(temp3);
} else {
ll avanca = max(a - S[i].ini, 0LL);
ll recua = max(S[i].fim - b, 0LL);
range temp1(S[i].A, S[i].A - avanca + 1);
range temp2(S[i].A - avanca, S[i].B + recua);
range temp3(S[i].B + recua - 1, S[i].B);
if (S[i].A >= S[i].A - avanca + 1) left.push_back(temp1);
if (S[i].A - avanca >= S[i].B + recua) mid.push_back(temp2);
if (S[i].B + recua - 1 >= S[i].B) right.push_back(temp3);
}
}
}
for (ll i = 0; i < mid.size(); i++) {
swap(mid[i].A, mid[i].B);
}
reverse(mid.begin(), mid.end());
S.clear();
for (ll i = 0; i < left.size(); i++) {
S.push_back(left[i]);
}
for (ll i = 0; i < mid.size(); i++) {
S.push_back(mid[i]);
}
for (ll i = 0; i < right.size(); i++) {
S.push_back(right[i]);
}
S[0].ini = 1;
S[0].fim = S[0].ini + abs(S[0].B - S[0].A);
for (ll i = 1; i < S.size(); i++) {
S[i].ini = S[i - 1].fim + 1;
S[i].fim = S[i].ini + abs(S[i].B - S[i].A);
}
left.clear();
mid.clear();
right.clear();
}
ll soma(ll a, ll b) {
ll resp = 0;
for (ll i = 0; i < S.size(); i++) {
if (S[i].fim < a) {
continue;
} else if (S[i].ini > b) {
continue;
} else {
if (S[i].A < = S[i].B) {
ll avanca = max(a - S[i].ini, 0LL);
ll recua = max(S[i].fim - b, 0LL);
ll Ax = S[i].A + avanca;
ll Ay = S[i].B - recua;
resp += ((Ax + Ay) * (Ay - Ax + 1)) / 2LL;
} else {
ll avanca = max(a - S[i].ini, 0LL);
ll recua = max(S[i].fim - b, 0LL);
ll Ax = S[i].A - avanca;
ll Ay = S[i].B + recua;
resp += ((Ax + Ay) * (Ax - Ay + 1)) / 2LL;
}
}
}
return resp;
}
int main() {
scanf("%lld %lld", &N, &M);
range temp(1LL, N);
temp.ini = 1LL;
temp.fim = N;
S.push_back(temp);
while (M--) {
char op;
scanf(" %c", &op);
if (op == 'I') {
ll a, b;
scanf("%lld %lld", &a, &b);
inverte(a, b);
// for(ll i = 0; i < S.size(); i++){
// printf("INI %lld FIM %lld A %lld B
//%lld\n",S[i].ini,S[i].fim,S[i].A,S[i].B);
// }
} else if (op == 'S') {
ll a, b;
scanf("%lld %lld", &a, &b);
printf("%lld\n", soma(a, b));
}
}
return 0;
}
Input
I 1 5
S 3 7
Output