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.

pentranje.cpp    5,002 b      izvorni kod rešenja
pentranje.50.cpp    2,670 b      izvorni kod rešenja za 50% poena
pentranje.tests.7z    40,228,109 b      test primeri

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,YN, 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;
}