|
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.
|
logo by Igor Antolović
|
|
|
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 ≤ i ≤ N, 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.
|
|
|