====== AISD: pracownia D ======
===== Wyniki =====
[[http://www.ii.uni.wroc.pl/~mbi/dyd/aisd_11s/wyniki_D.html]] - wyniki\\
1-sza kolumna to suma czasów z testów 1-10\\
0 oznacza nieprzejście jakiegoś testu 1-10.
<file wyniki.txt>
2032:   Paw Garn
2448:   Łuk Gnia
2644:   Pio Olma
3588:   Mar Sado
4288:   Pio Pole
4356:   Dan Błas
4364:   Paw Bogd
4384:   Kam Sobe
4708:   Ada Błas
4896:   Prz Past
4940:   Adr Mula
5004:   Mat Sier
5032:   Ram Huae (test)
5052:   Jan Marc
5084:   Mar Nied
5156:   Mat Lewa
5248:   Mat Kubi
5328:   Mac Maty
5700:   Łuk Synó
6064:   Tad Dul (test)
6216:   Jak Tarn
6284:   Mic Róża
6780:   Ale Szym
7096:   Mar Pawł
7896:   Pio Sobc (test)
7912:   Pio Sobc
10436:  Mac Kupi
10556:  Pio Krze
10928:  Grz Łoś
11468:  Kar Kona
12924:  Jan Walc
14036:  Mar Pole
15708:  Tad Dul
15976:  Mar Wier
16024:  Mat Buja
16040:  Mat Karw
16060:  Paw Schm
16132:  Raf Sław
16304:  Mar Kusy
16328:  Krz Kusi
16368:  Jak Stęp
16496:  Mar Wier (test)
17392:  Art Kras
17564:  Krz Piep
17572:  Mic Koło
17876:  Ewe Grot
19236:  Kam Wold
19668:  Dor Prze
19896:  Rob Miel
20432:  Ada Kuny
27988:  Pio Pole (test)
0:      Mar Zwon
0:      Kon Wypy
0:      Kar Woźn (test)
0:      Kar Woźn
0:      Mat Wójc
0:      Mac Wiec
0:      Dam Wiec
0:      Wer Świd
0:      Dor Such
0:      Kat Stre
0:      Paw Sobi
0:      Mar Siel
0:      Mic Rych
0:      Pio Popo
0:      Dam Piąt
0:      Cel Pawl
0:      Agn Olsz
0:      Pio Olch
0:      Aro Mojs
0:      Tom Miku
0:      Tom Macz
0:      Raf Maćk
0:      Łuk Lamp
0:      Mar Kusy (test)
0:      Mic Kras (test)
0:      Woj Kowa
0:      Mac Kena
0:      Mar Kacz
0:      Krz Hein
0:      Agn Góra
0:      Mic Głow
0:      Mik Garb
0:      Kat Form
0:      Mic Flen
0:      Daw Drza
0:      Jak Ceck
</file>
===== Rozwiązanie (cinkowskiw) =====
Przeszło wszystkie testy. Zrobione na drzewach przedziałowych.
<file zad4.c>#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;
const int M = 524288;
int i,  pozycja = 0, rozmiar = 0, znak, T, Ai, raw[M], sequence[M], starting[M], ending[M], tab[2*M], longest;
char buf[1000];

#define get_char(znak){if(rozmiar>pozycja)znak=buf[pozycja++];else{if(feof(stdin))znak=0;else{rozmiar=fread(buf,1,1000,stdin);znak=buf[0];pozycja=1;}}}
#define get_int(zm){zm=0;get_char(znak);while(znak!='\n'&&znak!=' '){zm=znak+10*zm-48;get_char(znak);}}

void insert(int element, int length) {
  int v = M + element;
  tab[v] = max(tab[v], length);
  while(v > 1) {
    v /= 2;
    tab[v] = max(tab[2 * v], tab[2 * v + 1]);
  }
}

int query(int smaller) {
  int x = M;
  int y = M + smaller;
  int r = tab[y];
  while(x / 2 != y / 2) {
    if (x % 2 == 0) r = max(r, tab[x + 1]);
    if (y % 2 == 1) r = max(r, tab[y - 1]);
    x /= 2; y /= 2;
  }
  return r;
}

int compare(const void * a, const void * b) {
  return(*(int*)a - *(int*)b);
}

int main()
{
  get_int(T);

  for(int i = 0; i < T; i++) {
    get_int(Ai);

    for(int j = 0; j < Ai; j++) {
      get_int(raw[j]);
      sequence[j] = raw[j];
    }
    
    /// PREPROCESING [skalowanie danych, z przedziału 10^9 robimy 5*10^5]
    qsort(raw, Ai, sizeof(int), compare);
    for(int j = 0; j < Ai; j++)
      sequence[j] = (int*) bsearch (&sequence[j], raw, Ai, sizeof (int), compare)-raw+1;

    /// STARTING [najdłuższy rosnący podciąg rozpoczynający się na danej pozycji] 
    starting[Ai-1] = 1;
    for(int j = (Ai-2); j >= 0; j--)
      starting[j] = (sequence[j] < sequence[j+1]) ? starting[j+1] + 1 : 1;
      
    /// ENDING [najdłuższy rosnący podciąg kończący się na danej pozycji] 
    ending[0] = 1;
    for(int j = 1; j < Ai; j++)
      ending[j] = (sequence[j-1] < sequence[j]) ? ending[j-1] + 1 : 1;

    /// MAIN LOOP
    longest = 0;
    for(int j = 0; j < Ai; j++) {
      longest = max(longest, query(sequence[j]-1) + starting[j]);
      insert(sequence[j], ending[j]);
    }

    memset(tab, 0, sizeof(tab));
    cout << longest << "\n";
  }
}
</file>