TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

metro.cpp    2,180 b      izvorni kod rešenja
metro.pas    2,864 b      izvorni kod rešenja
metro.tests.7z    5,654,215 b      test primeri

zadatak: Metro

U jednom gradu postoji metro-linija sa N stanica, numerisanih brojevima od 1 do N. Metro ide pravolinijski, tj. sa stanice broj i možemo metroom doći do stanica broj i - 1 i i + 1 (sa stanice 1 možemo doći samo do stanice 2 a sa stanice N samo do stanice N -1). Svaka stanica ima svoj ulazni kod - jedan prirodan broj koji se menja svakog dana. Ako imamo kartu sa rednim brojem k, mi možemo doći na neku stanicu (sa leve ili desne strane) samo ako k deli ulazni kod te stanice. Nas zanima koliko stanica možemo posetiti za različite početne stanice i različite brojeve karata.

Preciznije, dato je Q upita jednog od sledeća dva tipa:

  • 1 i x - promeniti ulazni kod i-te stanice na x,
  • 2 i k - ispisati koliko stanica možemo posetiti ako smo trenutno u i-toj i imamo kartu sa rednim brojem k.

Odgovoriti na sve upite tipa 2. Broj naše karte će uvek deliti ulazni kod početne stanice.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke metro.in.) U prvom redu ulazne datoteke nalaze se dva prirodna broja, N i Q, koji predstavljaju, redom, broj stanica i broj upita (1 ≤ N ≤ 200.000, 1 ≤ Q ≤ 100.000). Sledeći red sadrži N prirodnih brojeva manjih od 2 ·109 - početne ulazne kodove. Sledićih Q redova sadrže upite u gore opisanom formatu (izvršavaju se u datom redosledu). Za svaki od upita važi 1 ≤ iN, 2 ≤ k, x ≤ 2· 109.

Izlaz:

(Izlazni podaci se ispisuju u datoteku metro.out.) Za svaki upit tipa 2 ispisati odgovor (ceo broj) u posebnom redu izlazne datoteke. Na upite odgovarati u datom redosledu.

Primer 1:

metro.in      metro.out
6 4
2 25 20 30 19 5
2 3 5
2 4 6
1 5 100
2 3 5
        
3
1
5

Objašnjenje.

Ako smo na stanici broj 3 (ulazni kod 20) i imamo kartu broj 5, mi možemo posetiti tri stanice - 2, 3 i 4. Iako 5 deli ulazni kod stanice broj 6, mi do nje ne možemo doći jer ne možemo ući na stanicu sa ulaznim kodom 19. U drugom upitu nalazimo se na stanici broj 4 i ne možemo nigde otići. Posle promene ulaznog koda stanice broj 5, mi iz stanice broj 3 sa kartom broj 5 možemo posetiti 5 stanica - 2, 3, 4, 5 i 6.

Napomena.

U 20% test primera Q ≤ 103. U 40% test primera imamo uvek istu kartu tj. u svim upitima tipa 2 broj k će biti isti (u ovim primerima je Q neparno a u ostalim je parno).

fajl: metro.cpp
#include <cstdlib>
#include <cstdio>
#include <memory.h>

const int MaxN = 1 << 18;  // 2^18

int N, Q, X, Y, Z, sol;
int a[MaxN];

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

struct SegmentTree {
  int N;
  int t[2 * MaxN];
  int l[2 * MaxN];
  int r[2 * MaxN];
  int offset;
    
  void init(int a[], int n) {
    N = n;
    offset = MaxN - 1;
    for (int i = 1; i < 2 * MaxN; i++) t[i] = 1;

    for (int i = 1; i <= n; i++)
      t[i + offset] = a[i];
    for (int i = offset + 1; i < 2 * MaxN; i++) {
      l[i] = i;  r[i] = i;
    }

    for (int node = offset; node > 0; node--) {
      t[node] = gcd(t[2 * node], t[2 * node + 1]);
      l[node] = l[2 * node];
      r[node] = r[2 * node + 1];
    }
  }

  void update(int pos, int val) {
    int i = pos + offset;
    t[i] = val;
    i = i / 2;
    while (i > 0) {
      t[i] = gcd(t[2 * i], t[2 * i + 1]);
      i = i / 2;
    }
  }

  int firstRight(int pos, int k) {
    int i = pos + offset;
    while (i > 1 && t[i] % k == 0) {
      if (pos + offset <= l[i / 2])
        i = i / 2;
      else
        i = r[i] + 1;
      if (i > offset + N) return N;
    }

    while (i <= offset) {
      if (t[2 * i] % k == 0)
        i = 2 * i + 1;
      else
        i = 2 * i;
    }
    return i - offset - 1;
  }

  int firstLeft(int pos, int k) {
    int i = pos + offset;
    while (i > 1 && t[i] % k == 0) {
      if (r[i / 2] <= pos + offset)
        i = i / 2;
      else {
        i = l[i] - 1;
        if (i <= offset) return 1;
      }
    }

    while (i <= offset) {
      if (t[2 * i + 1] % k == 0)
        i = 2 * i;
      else
        i = 2 * i + 1;
    }
    return i - offset + 1;
  }

} metroLine;

int main() {

  FILE* inFile = fopen("metro.in", "r");
  FILE* outFile = fopen("metro.out", "w");

  fscanf(inFile, "%d%d", &N, &Q);
  for (int i = 1; i <= N; i++)
    fscanf(inFile, "%d", &a[i]);

  metroLine.init(a, N);
  for (int i = 0; i < Q; i++) {
    fscanf(inFile, "%d%d%d", &X, &Y, &Z);
    if (X == 1)
      metroLine.update(Y, Z);
    else {
      int r = metroLine.firstRight(Y, Z);
      int l = metroLine.firstLeft(Y, Z);
      fprintf(outFile, "%d\n", r - l + 1);
    }
  }

  fclose(inFile);
  fclose(outFile);
  return 0;
}
fajl: metro.pas
const
   MaxN = 1 shl 18;


var
   inFile, outFile : text;
   N, Q, X, Y, Z, sol : longint;
   a : array[0..MaxN] of longint;
   t, l, r : array[0..2*MaxN] of longint;
   N1, offset : longint;
   i, rs, ls : longint;


function gcd(a, b : longint) : longint;
begin
   if (b = 0) then gcd := a
        else gcd := gcd(b, a MOD b);
end;


procedure init(n : longint);
var
   i, node : longint;

begin
   N1 := n;
   offset := MaxN - 1;
   for i := 1 to 2 * MaxN - 1 do t[i] := 1;

   for i := 1 to n do
      t[i + offset] := a[i];

   for i := offset + 1 to 2 * MaxN - 1 do begin
      l[i] := i;
      r[i] := i;
   end;

   for node := offset downto 1 do begin
      t[node] := gcd(t[2 * node], t[2 * node + 1]);
      l[node] := l[2 * node];
      r[node] := r[2 * node + 1];
   end;
end;


procedure update(pos, val : longint);
var
   i : longint;

begin
   i := pos + offset;
   t[i] := val;
   i := i div 2;
   while (i > 0) do begin
      t[i] := gcd(t[2 * i], t[2 * i + 1]);
      i := i div 2;
   end;
end;



function firstRight(pos, k : longint) : longint;
var
   i : longint;
   found : boolean;

begin
   i := pos + offset;
   found := false;
   while ((i > 1) AND (t[i] MOD k = 0) AND (NOT found)) do begin
      if ((pos + offset) <= l[i DIV 2])
         then i := i DIV 2
      else
         i := r[i] + 1;
      if (i > offset + N1) then found := true;
   end;

   if (NOT found) then begin
      while (i <= offset) do
         if (t[2 * i] MOD k = 0) then i := 2 * i + 1
         else i := 2 * i;
   end;

   if (NOT found) then firstRight := i - offset - 1
   else firstRight := N1;
end;



function firstLeft(pos, k : longint) : longint;
var
   i : longint;
   found : boolean;

begin
   i := pos + offset;
   found := false;
   while ((i > 1) AND (t[i] MOD k = 0) AND (NOT found)) do begin
      if ((pos + offset) >= r[i DIV 2])
         then i := i DIV 2
      else begin
         i := l[i] - 1;
         if (i <= offset) then found := true;
      end;
   end;

   if (NOT found) then begin
      while (i <= offset) do
         if (t[2 * i + 1] MOD k = 0) then i := 2 * i
         else i := 2 * i + 1;
   end;

   if (NOT found) then firstLeft := i - offset + 1
   else firstLeft := 1;
end;



begin

        assign(inFile, 'metro.in'); reset(inFile);
  assign(outFile, 'metro.out'); rewrite(outFile);
  
  read(inFile, N, Q);
  for i := 1 to N do
           read(inFile, a[i]);

        init(N);
  
  for i := 1 to Q do begin

           read(inFile, X, Y, Z);
           if (X = 1) then update(Y, Z)
           else begin
              ls := firstLeft(Y, Z);
              rs := firstRight(Y, Z);
        writeln(outFile, rs - ls + 1);
     end;
  
        end;

  close(inFile);
  close(outFile);  

end.