[URI ONLINE JUDGE] – 1477 – Man, Elephant and Mouse

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1477

A very popular game in Nlogonia is called Man, Elephant and Mouse. It is typically played with only two players, and works as follows: each player secretly selects one of these three symbols, and after a countdown, both simultaneously reveal the symbol chosen through hand signals, extending in front his hands signaling the choice.

Man is represented by the closed hand, like the head of a man. The elephant is represented by the open hand showing five fingers, like the paw of the nlogonense elephant. Finally, the Rat is represented by the closed hand with the index finger and middle finger outstretched, as the ears of the little animal.

Figure 1: The three symbols of the game Man, Elephant and Mouse.

To determine the winner is very simple: the man always loses to the elephant (it is crushed under his paw), the elephant always loses to the mouse (because he is afraid of him and runs away) and the mouse always loses to the Man (which spreads traps to capture it). If two players use the same symbol, a tie occurs and the game is played again.

The inhabitants of Nlogonia, that are born strategists of Man, Elephant and Mouse, are using the following technique in the national championship, held every year: they always start playing man until the moment that this symbol cause tie with the most of their opponents. They then change its approach to the the winning symbol considering that they were using previously. Thus, players will switch to Elephant Man, then to Mouse, then they back again to Man.

To assist a famous foreign competitor in a game similar to this game Man, Elephant and Mouse, you will develop a program that counts how many players will use each symbol. Suppose all N players are arranged in a row and identified by their position, from 1 to N. Your program should handle with M commands of two types: change of symbol and count the frequency of these symbols. Both commands take a contiguous range of players in the queue to be considered.

Input

The input consists of several test cases. Each test case starts with a line containing two integers N (1 ≤ N ≤ 105) and M (0 ≤ M ≤ 106) which represent respectively the number of players in the tournament, and the number of operations.

The next M lines contain, each one, the description of an operation. Operations of  strategy changing will be represented by a line of the form “M A B” where A (1 ≤ A) and B (ABN) are integers. Players whose strategies are changed are those whose position in queue is between A and B, inclusive.

Counting operations are represented by a line of the form “C A B” where A and B are integers representing the range of players that should be considered in the count. Let’s consider that players whose position in the queue is between A and B, inclusive.

inclusive.

Output

For each operation, print a line containing three integers indicating respectly the number of Men, Elephant and Mouse symbols, that are used by the players in the given interval.

Print one blank line after each test case, including the last one.

Sample Input Sample Output
10 7
C 1 10
M 5 6
C 5 6
M 6 7
C 4 8
M 1 10
C 1 10
5 6
M 1 5
M 2 4
M 1 2
M 4 5
C 1 5
C 3 4
10 0 0
0 2 0
2 2 1
1 7 2

2 0 3
1 0 1

 

my solution:

 

<br />#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz size

#define MAXN 100010

#define ms(x,v) memset((x), (v), sizeof(x))

#define cl_(x) ((x) << 1)
#define cr_(x) (((x) << 1) + 1)
#define _NO_USE_LOG
#ifdef _USE_LOG
#define LOG(x) cout << x;
#else
#define LOG(x)
#endif

using namespace std;

typedef long long L;
typedef pair<L,L> PL;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef vector<PL> VPL;
typedef vector<VPL>VVPL;

#define MAN 0
#define ELEPHANT 1
#define RAT 2

class SegTree
{
private:
int st[MAXN*8][3];
int lazy[MAXN*8];
int n_;


inline void add_(int *res, int *inc) {
for(int i = 0; i < 3; ++i) res[i] += inc[i];
}

void prop_(int u, int l, int r) {
if(lazy[u] == 1) {
swap(st[u][0], st[u][1]); // 0 1 2 -> 1 0 2
swap(st[u][0], st[u][2]); // 1 0 2 -> 2 0 1
}
else if(lazy[u] == 2) {
swap(st[u][0], st[u][2]); // 0 1 2 -> 2 1 0
swap(st[u][0], st[u][1]); // 2 1 0 -> 1 2 0
}

if(lazy[u] && l != r) {
lazy[cl_(u)] = (lazy[cl_(u)] + lazy[u]) % 3;
lazy[cr_(u)] = (lazy[cr_(u)] + lazy[u]) % 3;
}

lazy[u] = 0;
}

void query_(int u, int l, int r, int i, int j, int *res) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j){
add_(res, st[u]);
}
else{
query_(cl_(u), l, (l + r)/2, i, j, res);
query_(cr_(u), (l + r)/2 + 1, r, i, j, res);
}
}

void upd_(int u, int l, int r, int i, int j) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j) {
lazy[u] = 1;
prop_(u, l, r);
}
else {
upd_(cl_(u), l, (l + r) / 2, i , j);
upd_(cr_(u), (l + r) / 2 + 1, r, i , j);
ms(st[u], 0);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}

void build_(int u, int l, int r) {
lazy[u] = 0;
ms(st[u], 0);
if(l == r) {
st[u][0] = 1;
}
else {
build_(cl_(u), l, (l + r) / 2);
build_(cr_(u), (l + r) / 2 + 1, r);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}
public:
void init(int n) {
n_ = n;
build_(1, 0, n_);
}

void update(int l, int r) {
upd_(1, 0, n_, l, r);
}

void query(int l, int r, int *res) {
query_(1, 0, n_, l, r, res);
}

};

SegTree st;

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

int n, m;
while(cin >> n >> m) {
st.init(n);
int queryRes[3];

for(int i = 0; i < m; ++i) {
char q;
int a, b;
cin >> q >> a >> b;
--a; --b;

if(q == 'C') {
ms(queryRes, 0);
st.query(a, b, queryRes);
cout << queryRes[0] << ' '
<< queryRes[1] << ' '
<< queryRes[2] << '\n';
}
else {
st.update(a, b);
}
}
cout << '\n';
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s