Pagini recente » Cod sursa (job #2066416) | Cod sursa (job #2957561) | Cod sursa (job #1831571) | Cod sursa (job #318998) | Cod sursa (job #1219298)
/* varianta naspa cu AIB si parsare */
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>
using namespace std;
#define dbg(x) (cout<<#x<<" = "<<(x)<<'\n')
const string problemName = "unique";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
typedef pair<int, int> PII;
typedef pair<PII, int> qry;
const int NMAX = 100000 + 5;
int T, N, sol, top;
int V[NMAX];
qry Q[NMAX];
int AIB[NMAX];
int ante[NMAX];
bool cmp(qry A, qry B) {
return A.first.second < B.first.second;
}
void erase() {
memset(V, 0, sizeof(V));
memset(AIB, 0, sizeof(AIB));
memset(ante, 0, sizeof(ante));
sol = top = 0;
}
void update(int poz, int val) {
for(; poz <= N; poz += poz & (-poz))
AIB[poz] += val;
}
int query(int poz) {
int ans = 0;
for(; poz; poz -= poz & (-poz))
ans += AIB[poz];
return ans;
}
#define DIM 10000
char buff[DIM];
int poz;
void read(int &x) {
x = 0;
while('0' > buff[poz] || buff[poz] > '9') {
poz++;
if(poz == DIM) {
fread(buff, DIM, 1, stdin);
poz = 0;
}
}
while('0' <= buff[poz] && buff[poz] <= '9') {
x = x * 10 + buff[poz] - '0';
poz++;
if(poz == DIM) {
fread(buff, DIM, 1, stdin);
poz = 0;
}
}
}
int main() {
int i, j, k, x, nr;
#ifndef ONLINE_JUDGE
freopen(inputFile.c_str(), "r", stdin);
freopen(outputFile.c_str(), "w", stdout);
#endif
read(T);
while(T--) {
erase();
read(N);
for(i = 1; i <= N; i++)
read(V[i]);
for(i = 1; i <= N; i++) {
x = V[i];
for(j = i - 1; j >= 1; j--)
if(V[j] > x)
break;
for(k = i + 1; k <= N; k++)
if(V[k] > x)
break;
Q[++top] = make_pair(make_pair(j + 1, k - 1), x);
}
sort(Q + 1, Q + top + 1);
for(i = 1; i <= top; i++) {
for(j = Q[i - 1].first.second + 1; j <= Q[i].first.second; j++) {
if(ante[V[j]]) update(ante[V[j]], -1);
update(j, 1);
ante[V[j]] = j;
}
nr = query(Q[i].first.second) - query(Q[i].first.first - 1);
if(nr == Q[i].second) sol = max(sol, Q[i].first.second - Q[i].first.first + 1);
}
printf("%d\n", sol);
}
return 0;
}