MATSUM

zašto radi samo 4 / 10.
http://www.z-trening.com/submit.php?submit=7100067993&subm_code=1

pa prvo sto sam primetio je:
long long sol = log.get(x2, y2) + log.get(x2, y1 - 1) + log.get(x1 - 1, y2) + log.get(x1 - 1, y1 - 1);

i to nije dobro...

zasto ???

sta tebi da log.get( x, y ) ?

da ti sumu od 0,0 do x, y tako ?

e sada tebi treba suma od x1, y1 do x2, y2

a ti trazis tako sto radis
long long sol = log.get(x2, y2) + log.get(x2, y1 - 1) + log.get(x1 - 1, y2) + log.get(x1 - 1, y1 - 1);

i tu dobijes sumu od:
sumu od 0,0 do x2, y2
sumu od 0,0 do x2, y1-1
sumu od 0,0 do x1-1, y2
sumu od 0,0 do x1-1, y1-1

tj. dobijes
4 * ( suma od 0,0 do x1-1, y1-1 ) + 2 * ( suma od 0,0 do x1-1,y2 ) + 2 * ( suma od 0,0 do x2,y1-1 ) + ( suma od x1, y1 do x2, y2 )...

e zato formula trebalo malo drugacije da izgleda...

probaj da nacrtas, pa ces uspeti da vidis... :)

aha, tnx

Ma šta god ispišem radi 4 / 10.
Mislim da u tim testovima koji mi rade su svi ispisi 0.
Možda je greška u samoj strukturi

vidim da ti ne valja formula..

formula bi trebala biti:

za x1, y1, x2, y2

get( x2, y2 ) - get( x2, y1 - 1 ) - get( x1 - 1, y2 ) + get( x1 - 1, y1 - 1 ).. :)

opet isto 4 / 10.
počinjem misliti da se to može samo meni dogoditi :)

imas jos 2 greske... sad sam video...

1.void set(int i, int j, int value) {
for (; i <= n ; i += i & -i) {
for (int _j = j; _j <= n ; _j += _j & -_j) {
a[ i ][ _j ] = value;
}
zasto a[ i ][ _j ] = value ?
zar ne bi trebalo a[ i ][ _j ] += value ?

2.if (tmp[ 2 ] == 'T') {
scanf ("%d %d %d", &x, &y, &val);
++x;
++y;
log.set(x , y, val);
}
tu ovo log.set( x, y, val ) ne valja... zasto ?

pa sta ako ti se da 2 puta za isto polje da postavis neku vrednost ?

ti ces samo dodati na prethodnu vrednost novu vrednost..
znaci umesto log.set( x, y, val ) ti treba da updatetujes polje x, y sa val - Get( x, y, x, y )..

tj. treba log.set( x, y, val - Get( x, y, x, y ) )

gde je Get( int x1, int y1, int x2, int y2 ):

int Get( int x1, int y1, int x2, int y2 )
{
return log.get( x2, y2 ) - log.get( x1 - 1, y2 ) - log.get( x2, y1 - 1 ) + log.get( x1 - 1, y1 - 1 );
}

nadam se da si razumeo

boris , mislim da u testovima nece biti problema s time jer su neki bez toga poslali pa je proslo :)

meni log.get() prima 2 varijable. Zašto si stavio 4??

srry.. update-ovo sam...

opet 4 / 10.
baš i nisam skužio ovo...
AABB
AABB
CCDD
CCDD
OVAKO NEKA IZGLEDA MATRICA.
onda bi trebao u sol zbrojiti sve od početka do kraja, onda oduzeti dio di su A i B, oduzeti dio di su A i C i pridodati tome 2*(zbroj svugdje di je A)

Ako se ne varam ti oces da izracunas sumu gde je D.

zasto 2 * ( suma gde je A ) ? Treba samo jednom sabrati to...

zasto ?

pa tebi treba ovako..
+ suma cele matrice gde su A, B, C, D
- suma gde su A i B
- suma gde su A - C
+ suma gde je A

i sada pogledaj:
2 puta sabiras, 2 puta oduzimas gde je A
1 put sabiras, 1 put oduzimas gde je B
1 put sabiras, 1 put oduzimas gde je C
1 put sabiras gde je D

i dobijes sumu gde je D...

pre nego sto posaljes na grader, trebas da proveris da li ti rade test primeri u zadatku...
tebi taj test primer ne radi...

e sada gde ti je greska u kodu...

pogledaj svoju do{}while petlju koja izgleda ovako:
do{
...
}while ( tmp[ 2 ] == 'D' ) ... zasto == ?
zar ne bi trebalo while ( tmp[ 2 ] != 'D' ) ?

jos jedna greska ti je u strukturi...
u svim funkcijama ti koristis n, koje program uzima iz tvoje strukture, a to n nije postavljeno...

znaci ili stavi log.n = n ili izbrisi n iz strukture..

evo radi, najbrže rješenje.
http://z-trening.com/submit.php?submit=7100069796&subm_code=1
samo neš ne kužim
long long sol = Get(x, y, x, y);
printf ("%lld", sol);

zašto to radi uopće :)

Sa test podatcima nesto ozbiljno ne valja. Na primjer nikad se nece desiti da se broj upisuje na isto mjesto , tako je moje proslo, a mateov kod uopce ne radi sta bi trebao, pa je svedno proslo!!

xD matteo to nebi trebalo raditi jer ti printas ono sta se nalazi na polju koje je zadnje upisano xD to nesmije radit lol losi su primjeri strasno..

Ma probajte vi to na spoju poslati... Ako vam tamo prodje onda vam je kod uredu..... ;)

Najpametnije Amtrix :)

ma nemorate govorit da je loše rješenje...vidite da sam sam skužio LOL...probat ću na spoju...@Amtrix: dobra ideja


TEK SAM SADA VIDIO...POBRISALI MI RJEŠENJE...BAŠ VAM HVALA :)

SAMO MI PADAJU 8. I 10. PRIMER, NA NJIME JAVLJA TLE. STA NE VALJA?

# include <iostream>
# include <string>
# include <cstdio>
using namespace std;
int m[1100][1100];
int n;
int calc(int &x1,int &y1, int &x2, int &y2) {
int sum(0);
for(int j=y1;j<=y2;j++)
for(int i=x1;i<=x2;i++)sum+=m[i][j];
return sum;
}
int main() {
scanf("%d",&n);
string s;
int x,y,num,xx,yy;
for (int j=0;j<n;j++)
for (int i=0;i<n;i++)
m[i][j]=0;
while ((cin>>s,s)!="END") {
if (s == "SET") {
scanf("%d%d%d",&x,&y,&num);
m[x][y]=num;
}

else {
scanf("%d%d%d%d",&x,&y,&xx,&yy);
printf("%d\n",calc(x,y,xx,yy));
}

}
//system("pause");



}

Kod je u redu, ali cij je rešti ovaj zadatak nekim drugim (bržim) postupkom, a ne brute force.
Nadji na netu nešto o kumulativnim tabelama.

Napred na ovoj stranici Mateo koristi 'binary indexed tree', što i tebi preporučujem.