|
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: Mrvice
|
Baka je napravila veliku tortu kvadratnog oblika za svoje unuke. Kao ukras, uzduž i
popreko je stavila šlag preko torte, podelivši je na n x n kvadratnih polja
jednake veličine. Na kraju je na svako polje prosula određen broj čokoladnih mrvica.
Baka seče tortu na sledeći način: Prvo odabere jednu od četiri strane torte sa koje će
da krene da seče, a zatim odabere između kojih redova, odnosno kolona, će da seče tortu.
Posle toga se ne menja ni pravac, ni smer sečenja dok se sečenje ne završi. Ukoliko je ovo
prvo sečenje u tom pravcu i smeru, baka seče od ivice torte. Ako je ranije već sekla u
tom pravcu i smeru, onda seče od mesta završetka poslednjeg sečenja u tom pravcu i smeru.
Nakon što počne da seče parče, ne zaustavlja se do njegove suprotne ivice, odnosno dok ga
potpuno ne preseče. Ništa se ne seče ako je torta več presečena celom dužinom u datom
pravcu.
Pošto svi njeni unuci mnogo vole čokoladne mrvice, baka ne želi da neko dobije ni
premalo, a ni previše mrvica na parčetu.
Vama je dato je q upita jednog od sledeća dva tipa:
-
1 a b - torta se seče u smeru a (jednom od četiri kao na slici). Ako je horizontalno
sečenje, torta se seče između redova b i b + 1. Ako je vertikalno sečenje,
torta se seče između kolona b i b + 1.
-
2 l h - potrebno je odgovoriti koliko parčadi trenutno postoji takvih da je broj mrvica
na parčetu u intervalu [l, h].
Ulaz:
(Ulazni podaci se učitavaju iz datoteke mrvice.in.)
U prvom redu ulaza se nalaze brojevi n i q (1 ≤ n≤ 500, 1 ≤ q ≤ 100.000),
dimenzija torte i broj upita. U sledećih nredova nalazi se po n brojeva, broj mrvica na svakom
polju torte. Svako polje će imati najmanje jednu, a najviše 2*109 mrvica. Zatim sledi q redova koji
predstavljaju već opisane upite formata t i j, gde t ∈ {1,2}.
Ako je t = 1, onda 0 ≤ i ≤ 3 i 1 ≤ j ≤ n - 1.
Ako je t = 2, onda 1 ≤ i ≤ j ≤ 1015.
Upiti se izvrxavaju u redosledu datom na ulazu.
Izlaz:
(Izlazni podaci se ispisuju u datoteku mrvice.out.) Za svaki upit tipa 2 iz
ulaza ispisati u novi red izlaza odgovor na taj upit (odgovore ispisivati u odgovarajućem
redosledu). Postojaće bar jedan upit tipa 2.
Primer 1:
mrvice.in
|
|
mrvice.out
|
4 6
3 12 8 5
4 1 2 9
7 6 6 3
10 4 2 8
1 2 1
1 3 3
2 9 15
1 3 3
2 13 14
2 17 100
|
|
2
2
1
|
Objašnjenje.
Za dati primer, sečenja su prikazana na slikama:
|
|
|
Posle 1. sečenja
|
Posle 2. sečenja
|
Posle 3. sečenja
|
Napomena.
-
U 20% test primera biće n, q≤ 100.
-
U 40% test primera broj upita tipa 1 neće preći 1.000.
|
|
fajl: mrvice.cpp
|
#include <algorithm>
#include <cstdio>
#define MAXN 510
#define MAXQ 100010
#define INF 1LL<<60LL
using namespace std;
typedef struct
{
int vrsta;
long long a,b;
} upit;
typedef struct
{
long long nsuma,dsuma1,dsuma2;
} suma;
typedef struct
{
int glr, glk, ddr, ddk;
long long suma;
} parce;
int dr[4]={1,0,-1,0};
int dk[4]={0,-1,0,1};
int torta[MAXN][MAXN],mesto[4][MAXN],n,q,br,trenred,trenkol,dokle,brojsuma=1;
int brparcadi=1,parcadmat[MAXN][MAXN],trenparce,glr,glk,ddr,ddk;
int brojac[MAXQ*2];
long long sume[2*MAXQ],pocsuma;
parce parcad[MAXQ];
upit upiti[MAXQ];
suma upitSume[MAXQ];
int seci(int strana, int red, int kol)
{
if (strana==0 && red>mesto[2][kol] ||
strana==1 && kol<mesto[3][red] ||
strana==2 && red<mesto[0][kol] ||
strana==3 && kol>mesto[1][red] ||
parcadmat[red][kol]!=parcadmat[red-dr[strana]][kol-dk[strana]])
return 0;
return 1;
}
int nadjisumu(long long s)
{
int l=1,d=brojsuma,sr;
while (l<=d)
{
sr=(l+d)/2;
if (sume[sr]==s)
return sr;
if (s<sume[sr])
d=sr-1;
else
l=sr+1;
}
return 0;
}
int nadjigranicu(long long s)
{
int l=1,d=brojsuma,sr;
while (l+1<d)
{
sr=(l+d)/2;
if (s<sume[sr])
d=sr;
else
l=sr;
}
if (sume[d]<=s)
return d;
else
return l;
}
void dodaj(int poz, int kol)
{
for (int i=poz; i<=brojsuma; i+=(i & -i))
brojac[i]+=kol;
}
int prebroj(int poz)
{
int broj=0;
for (int i=poz; i>0; i-=(i & -i))
broj+=brojac[i];
return broj;
}
int main()
{
freopen("mrvice.in","r",stdin);
freopen("mrvice.out","w",stdout);
scanf("%d %d",&n,&q);
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
{
scanf("%d",&torta[i][j]);
pocsuma+=(long long)torta[i][j];
}
sume[1]=pocsuma;
for (int i=0; i<=3; i++)
for (int j=1; j<n; j++)
if (i==1 || i==2)
mesto[i][j]=n;
else
mesto[i][j]=1;
parcad[0].glr=1;
parcad[0].glk=1;
parcad[0].ddr=n;
parcad[0].ddk=n;
parcad[0].suma=sume[1];
for (int i=0; i<q; i++)
{
scanf("%d %lld %lld",&upiti[i].vrsta,&upiti[i].a,&upiti[i].b);
if (upiti[i].vrsta==1)
if (upiti[i].a&1 && mesto[3][upiti[i].b]>mesto[1][upiti[i].b] ||
(upiti[i].a&1)==0 && mesto[2][upiti[i].b]<mesto[0][upiti[i].b])
upiti[i].vrsta=0;
else
{
if (upiti[i].a&1)
{
trenred=upiti[i].b;
trenkol=mesto[upiti[i].a][upiti[i].b]+dk[upiti[i].a];
}
else
{
trenkol=upiti[i].b;
trenred=mesto[upiti[i].a][upiti[i].b]+dr[upiti[i].a];
}
while (seci(upiti[i].a,trenred,trenkol))
{
trenred+=dr[upiti[i].a];
trenkol+=dk[upiti[i].a];
}
if (upiti[i].a&1)
{
mesto[upiti[i].a][trenred]=trenkol;
trenparce=parcadmat[trenred][trenkol-dk[upiti[i].a]];
parcad[brparcadi].glk=parcad[trenparce].glk;
parcad[brparcadi].ddk=parcad[trenparce].ddk;
if (trenred-parcad[trenparce].glr<parcad[trenparce].ddr-trenred)
{
parcad[brparcadi].glr=parcad[trenparce].glr;
parcad[brparcadi].ddr=trenred;
parcad[trenparce].glr=trenred+1;
}
else
{
parcad[brparcadi].glr=trenred+1;
parcad[brparcadi].ddr=parcad[trenparce].ddr;
parcad[trenparce].ddr=trenred;
}
}
else
{
mesto[upiti[i].a][trenkol]=trenred;
trenparce=parcadmat[trenred-dr[upiti[i].a]][trenkol];
parcad[brparcadi].glr=parcad[trenparce].glr;
parcad[brparcadi].ddr=parcad[trenparce].ddr;
if (trenkol-parcad[trenparce].glk<parcad[trenparce].ddk-trenkol)
{
parcad[brparcadi].glk=parcad[trenparce].glk;
parcad[brparcadi].ddk=trenkol;
parcad[trenparce].glk=trenkol+1;
}
else
{
parcad[brparcadi].glk=trenkol+1;
parcad[brparcadi].ddk=parcad[trenparce].ddk;
parcad[trenparce].ddk=trenkol;
}
}
for (int r=parcad[brparcadi].glr; r<=parcad[brparcadi].ddr; r++)
for (int k=parcad[brparcadi].glk; k<=parcad[brparcadi].ddk; k++)
{
parcadmat[r][k]=brparcadi;
parcad[brparcadi].suma+=(long long)torta[r][k];
}
upitSume[i].nsuma=parcad[trenparce].suma;
parcad[trenparce].suma-=parcad[brparcadi].suma;
upitSume[i].dsuma1=parcad[trenparce].suma;
upitSume[i].dsuma2=parcad[brparcadi].suma;
sume[++brojsuma]=upitSume[i].dsuma1;
sume[++brojsuma]=upitSume[i].dsuma2;
brparcadi++;
}
}
sume[++brojsuma]=-INF;
sume[++brojsuma]=INF;
sort(sume+1,sume+brojsuma+1);
br=1;
for (int i=2; i<=brojsuma; i++)
if (sume[i]!=sume[i-1])
sume[++br]=sume[i];
brojsuma=br;
dodaj(nadjisumu(pocsuma),1);
for (int i=0; i<q; i++)
if (upiti[i].vrsta==1)
{
dodaj(nadjisumu(upitSume[i].dsuma1),1);
dodaj(nadjisumu(upitSume[i].dsuma2),1);
dodaj(nadjisumu(upitSume[i].nsuma),-1);
}
else
if (upiti[i].vrsta==2)
printf("%d\n",prebroj(nadjigranicu(upiti[i].b))-prebroj(nadjigranicu(upiti[i].a-1)));
return 0;
}
|
|
|