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.
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
Przeszło wszystkie testy. Zrobione na drzewach przedziałowych.
#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";
}
}