ACM ICPC Latin America 2011 – J – Jupiter Attacks!

This problem is a case of RMQ or Interval Trees.
For join two ranges:

[latexpage][ quicklatex{size=20} R_a + R_b]

[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) cup (B^0f_4 + B^1f_3 + B^2f_2) ]

[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) + (B^0f_4 + B^1f_3 + B^2f_2)B^3 ]

[ quicklatex{size=20} B^0f_7 + B^1f_6 + B^2f_5 + B^3f_4 + B^4f_3 + B^5f_2 ]

With that formula we can pre-calculate some intervals and the intervals can join for solve queries, this my implementation.

 * @author: vudduu - Edwin Guzman
 * @problem: Problem J - Jupiter Attacks!
 * @contest: ACM ICPC Latin America Regional 2011
#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

LL T[400000], MOD, B[100005];

void insert(int i, int v, int it, int ini, int end){
   if(ini == end){
      T[it] = v % MOD;
   int le = it<<1, ri = le+1, mid = (ini+end)>>1;
   if(i <= mid) insert(i, v, le, ini, mid);
   else insert(i, v, ri, mid+1, end);
   T[it] = ((( T[le]*B[end-mid] ) % MOD) + T[ri]) % MOD;

LL functionH(int x, int y, int it, int ini, int end){
   if(x == ini && y == end) return T[it];
   int le = it<<1, ri = le+1, mid = (ini+end)>>1;
   if(y <= mid) return functionH(x, y, le, ini, mid);
   else if(x > mid) return functionH(x, y, ri, mid+1, end);
   return ((( functionH(x, mid, le, ini, mid)*B[y-mid] ) % MOD) + functionH(mid+1, y, ri, mid+1, end)) % MOD;

int main(){
   int b, p, l, n, x, y;
   char op;
   scanf("%d %d %d %d", &b, &p, &l, &n);
      memset(T, 0, sizeof(T));
      memset(B, 0, sizeof(B));
      B[0] = 1;
      MOD = p;
      FOR(i, 1, 100000) B[i] = (B[i-1]*LL(b)) % MOD;
      F(i, n){
         if(op == 'E') insert(x, y, 1, 1, l);
         else printf("%lldn", functionH(x, y, 1, 1, l));
      scanf("%d %d %d %d", &b, &p, &l, &n);


Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s