|
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ć
|
Sponzori
|
|
|
zadatak: Pentranje
|
Ako se dobro sećate, gazda Srba ima voćnjak šljiva u srcu Šumadije. Kako je Srba
veliki perfekcionista, on svoj šljivik održava uvek u formi kvadrata, tako da u svakom od
ukupno N redova šljivika bude tačno po N stabala šljiva. Svako stablo ima svoju visinu,
koju gazda Srba uredno kontroliše.
Kada se Srba popne na neku šljivu, on vidi vrhove svih šljiva u voćnjaku koje imaju
manju visinu od one na koju se popeo (vrhove ostalih šljiva ne vidi). Njega zanima, kada se
popne na neku šljivu, koji je najdalji vrh koji on vidi. Srba rastojanje između dve šljive
meri kao zbir apsolutnih razlika redova i kolona u kojima se nalaze. Vremenom će se i
visine nekih šljiva promeniti (gazda Srba može da ih poseče ili kalemi sa ciljem da bolje
rode sledeće godine), ali će vas blagovremeno obavestiti o svim promenama visina.
Formalnije, gazda Srba će vam dostaviti Q informacija. Informacija može da bude
tipa "1 X Y" što označava da se gazda Srba popeo na šljivu koja se nalazi u redu X i koloni
Y , na ovu informaciju vi njemu treba da odgovorite koliko je udaljena najdalja šljiva čiji
vrh on trenutno vidi; drugi tip informacije je "2 X Y V", što označava da je šljiva koja
se nalazi u redu X i koloni Y promenila visinu na V.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke pentranje.in.)
U ulaznoj datoteci se u prvom redu nalazi broj N (1 ≤ N ≤ 1000),
broj redova i kolona Srbinog voćnjaka. U sledećih N redova se nalaze po N
brojeva iz intervala [1, 109] koji predstavljaju početne visine svake šljive. U sledećem redu se
nalazi broj Q (1 ≤ Q ≤ 500.000), broj Srbinih informacija. U sledećih Q redova se
nalaze gore opisane informacije, u svakom redu po jedna. (1 ≤ X,Y ≤ N, 1 ≤ V ≤ 109).
Izlaz.
(Izlazni podaci se ispisuju u datoteku pentranje.out)
Za svaku informaciju prvog tipa ispisati udaljenost najudaljenije šljive čiji vrh gazda
Srba vidi kada se popne na tu šljivu. Ukoliko ne postoji šljiva manja od one na koju se on popeo, ispisati -1.
Primer 1.
pentranje.in
|
|
pentranje.out
|
5
6 7 8 2 3
4 8 2 4 7
9 8 2 8 3
1 7 1 8 2
2 5 5 3 9
7
1 5 1
2 5 1 3
1 5 1
2 2 5 1
1 5 1
1 2 5
1 3 5
|
|
3
5
7
-1
5
|
Objašnjenje.
Gazda Srba vam daje prvu informaciju da se popeo na
šljivu (5, 1). On sada vidi vrhove šljiva (4, 1) i (4, 3). Šljiva (4, 1) se
nalazi na udaljenosti 1 dok se šljiva (4, 3) nalazi na udaljenosti 3, pa je
rezultat 3. Druga informacija je da je šljiva (5, 1) promenila visinu na 3.
Treća informacija takođe kaže da se Srba popeo na šljivu (5, 1), ali sada on
vidi vrhove šljiva (2, 3), (3, 3), (4, 1), (4, 3), (4, 5), od kojih su
najudaljeniji (2, 3) i (4, 5) i nalaze se na udaljenosti 5. Za petu informaciju
najudaljenija šljiva je (2, 5), za šestu nema šljive koja ima visinu manju od 1
pa je odgovor -1, a za poslednju informaciju najudaljenija manja šljiva je (4, 1).
Napomena.
U 50% test primera, Srba vam nikad neće dati informaciju drugog tipa. U ovim primerima je Q neparno,
a tamo gde ima i informacija drugog tipa je Q parno.
|
|
fajl: pentranje.cpp
|
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>
using namespace std;
#define sz size()
#define pb push_back
#define len length()
#define clr clear()
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORR(i,n) for(i=0;i<n;i++)
#define is_digit(c) ('0'<=(c) && (c)<='9')
#define eps 0.0000001
#define PI 3.14159265359
#define inf 1999888777
int n,a[1005][1005],where_glavna[1005][1005],where_sporedna[1005][1005];
struct polje {
int x,y;
} pos_glavna[2000555],pos_sporedna[2000555];
int dist(int x1, int y1, int x2, int y2) {
return (abs(x1-x2) + abs(y1-y2));
}
class segmentno {
public:
int brc,m[3500555];
bool glavna;
void init(bool g) {
int i;
brc = 1;
while (brc < n*n) brc *= 2;
for(i=brc; i<2*brc; i++) {
m[i] = inf;
}
for(i=brc-1; i>0; i--) {
m[i] = inf;
}
glavna = g;
}
polje nadji_najblizi_levo(int v) {
int x;
x = 1;
while (x < brc) {
if (m[x*2] < v) x = x*2; else x = x*2 + 1;
}
if (glavna) {
return pos_glavna[x-brc+1];
} else {
return pos_sporedna[x-brc+1];
}
}
polje nadji_najblizi_desno(int v) {
int x;
x = 1;
while (x < brc) {
if (m[x*2+1] < v) x = x*2 + 1; else x = x*2;
}
if (glavna) {
return pos_glavna[x-brc+1];
} else {
return pos_sporedna[x-brc+1];
}
}
polje nadji_najdalji_manji(int x, int y) {
polje p1,p2;
p1 = nadji_najblizi_levo(a[x][y]);
p2 = nadji_najblizi_desno(a[x][y]);
return (dist(x,y,p1.x,p1.y) > dist(x,y,p2.x,p2.y)) ? p1 : p2;
}
void ubaci(int k, int v) {
int x;
x = brc + k - 1;
m[x] = v;
x /= 2;
while( x > 0 ) {
m[x] = min(m[2*x], m[2*x+1]);
x /= 2;
}
}
};
void init_where_glavna() {
int i,j,pi,pj,br;
br=0;
for(i=0; i<n; i++) {
pi=i; pj=0;
while(pi >= 0) {
br++;
where_glavna[pi][pj] = br;
pos_glavna[br].x = pi;
pos_glavna[br].y = pj;
pi--;
pj++;
}
}
for(j=1; j<n; j++) {
pi=n-1; pj=j;
while(pj < n) {
br++;
where_glavna[pi][pj] = br;
pos_glavna[br].x = pi;
pos_glavna[br].y = pj;
pi--;
pj++;
}
}
}
void init_where_sporedna() {
int i,j,pi,pj,br;
br=0;
for(i=n-1; i>=0; i--) {
pi=i; pj=0;
while(pi < n) {
br++;
where_sporedna[pi][pj] = br;
pos_sporedna[br].x = pi;
pos_sporedna[br].y = pj;
pi++;
pj++;
}
}
for(j=1; j<n; j++) {
pi=0; pj=j;
while(pj < n) {
br++;
where_sporedna[pi][pj] = br;
pos_sporedna[br].x = pi;
pos_sporedna[br].y = pj;
pi++;
pj++;
}
}
}
segmentno seg_glavna, seg_sporedna;
int main() {
FILE *fin = fopen("pentranje.in", "r"), *fout = fopen("pentranje.out", "w");
int i,j,x,y,v,q,up;
polje p1,p2;
fscanf(fin, "%d", &n);
//scanf("%d", &n);
init_where_glavna();
init_where_sporedna();
seg_glavna.init(true);
seg_sporedna.init(false);
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
fscanf(fin, "%d", &a[i][j]);
seg_glavna.ubaci(where_glavna[i][j], a[i][j]);
seg_sporedna.ubaci(where_sporedna[i][j], a[i][j]);
}
}
fscanf(fin,"%d", &q);
for(i=0; i<q; i++) {
fscanf(fin,"%d", &up);
if (up == 2) {
fscanf(fin,"%d%d%d", &x, &y, &v);
x--; y--;
a[x][y] = v;
seg_glavna.ubaci(where_glavna[x][y], v);
seg_sporedna.ubaci(where_sporedna[x][y], v);
} else {
fscanf(fin, "%d%d", &x, &y);
x--; y--;
if (seg_glavna.m[1] >= a[x][y]) {
fprintf(fout,"-1\n");
} else {
p1 = seg_glavna.nadji_najdalji_manji(x,y);
p2 = seg_sporedna.nadji_najdalji_manji(x,y);
fprintf(fout,"%d\n", max( dist(x,y,p1.x,p1.y), dist(x,y,p2.x,p2.y)));
}
}
}
fclose(fin); fclose(fout);
return 0;
}
|
|
|