【vector】【bzoj 2083】Intelligence test

2083: [Poi2010]Intelligence test

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 294  Solved: 130

Description
覇中知能テスト機構の一つの仕事は、一定の規則に従ってシーケンスの数字を削除し、確定した数列を得ることだ.Lyxは覇中知能テスト機構の主管になることを渇望しているが、彼はこの仕事でよくやっていない.よく知っていて巧みだと言われているが、彼は多くの練習をするつもりだ.だから、彼はあなたがプログラムを書いて彼の答えが正しいかどうかを迅速に判断することを望んでいる.
Input
第1行目の整数m(1<=m<=100000)第2行目は、m個のスペースで区切られた整数ai(1<=ai<=100000)を含み、最初のシーケンスを構成し、第3行目の整数n(1<=n<=100000)は、n個のLyxが一連の削除を経て得られたシーケンスを表し、各シーケンスの2行目は、長さL(1<=L<=m)を与え、その後、次の行のL個のスペースで区切られた整数bi(1<=bi<100000)を与える.
Output
共n行、Lyxのシーケンスが確かに最初のシーケンスからいくつか削除された数で得られた場合、TAKが出力され、そうでなければNIEが出力される.
Sample Input

7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4

Sample Output

TAK
NIE
TAK
NIE
HINT

Source

by poi

問題:
vector. STLは素晴らしい!各重み値に対してvectorを開き、1つのシーケンスに対して位置を二分するたびに良くなり、明らかに各位置が上位になるほど良い.
Code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[1001000];
int n,m,b[1001000];
int in(){
    int x=0; char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
bool work(int l){
    int last=-1;
    for (int i=1; i<=l; i++){
        vector<int>::iterator it=upper_bound(a[b[i]].begin(),a[b[i]].end(),last);
        if (it==a[b[i]].end()) return false;
        last=*it;
    }
    return true;
}
int main(){
    n=in();
    for (int i=1; i<=n; i++){
        int x=in();
        a[x].push_back(i);
    }
    m=in();
    for (int i=1; i<=m; i++){
        int l=in();
        for (int j=1; j<=l; j++) b[j]=in();
        if (work(l)) printf("TAK
");
        else printf("NIE
");
    }
    return 0;
}