Cod sursa(job #1219298)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 13 august 2014 22:32:41
Problema Distincte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
/* 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;
}