Pagini recente » Cod sursa (job #1154091) | Cod sursa (job #773815)
Cod sursa(job #773815)
// rezolvare off-line
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
# define verf ++poz == hg ? cin.read (ch, hg), poz = 0 : 0
const int hg = 1 << 13;
#define maxn 250005
#define maxm 300005
char ch[hg];
long poz;
inline void cit ( long &x ) {
if (ch[0] == '\0') cin.read (ch, hg) ;
else for (; ch[poz] < '0' || ch[poz] > '9' ; verf) ;
for (x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' ; x = x * 10 + ch[poz] - '0', verf) ;
}
typedef struct { long a,b,rez; } query;
query Q[maxm];
long i,n,m,x;
long Nr[maxn],nr,act;
long C[maxn];
vector <long> V[maxn];
vector <long> QM[maxn];
void DFs ( long varf )
{
nr=1;
while ( nr>0 )
{
varf = Nr[nr];
if ( !C[varf] )
{
long i;
for ( i=0; i<QM[varf].size(); i++ )
{
if ( Q[ QM[varf][i] ].b > nr )
Q[ QM[varf][i] ].rez=0;
else
Q[ QM[varf][i] ].rez = Nr[nr- Q[ QM[varf][i] ].b ];
}
}
if ( C[varf] == (V[varf].size() ))
nr--;
else{
nr++;
Nr[nr]=V[varf][C[varf]];
C[varf]++;
}
}
}
int main()
{
freopen ("stramosi.in","r",stdin);
freopen ("stramosi.out","w",stdout);
cit(n);
cit(m);
for ( i=1; i<=n; i++ )
{
cit(x);
V[x].push_back(i);
}
for ( i=1; i<=m; i++ )
{
cit ( Q[i].a);
cit ( Q[i].b);
QM[ Q[i].a ].push_back( i );
}
DFs(0);
for ( i=1; i<=m; i++ )
printf ("%d\n",Q[i].rez);
}