Phần tử đầu tiên nhỏ hơn

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 67M
Author:
creator
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho dãy số nguyên có \(n\) phần tử \(a_1, a_2, ...,a_n\). Bạn hãy trả lời các truy vấn dạng \(x\): vị trí (chỉ số) của phần tử đầu tiên trong dãy số không lớn hơn \(x\).

Đầu vào

Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(q\) \((1 \leq n, q \leq 10^5)\), số phần tử của dãy và số lần truy vấn.

Dòng tiếp theo gồm \(n\) số nguyên là các phần tử của dãy số có giá trị tuyệt đối không vượt quá \(10^{9}\).

\(q\) dòng tiếp theo mỗi dòng chứa đúng một số nguyên \(x\) (\(-10^{9} \le x \le 10^{9}\)).

Đầu ra

Xuất ra \(q\) dòng, mỗi dòng chứa duy nhất một số tự nhiên.

Nếu không có phần tử nào trong dãy \(\le x\), xuất ra \(0\).

Subtask

\(30\%\) số test có \(n, q \le 1000\).

Ví dụ

Đầu vào:

6 3
9 5 5 3 -2 5
1
10
5

Đầu ra:

5
1
2
QDUY

Comments


  • 0
    VuThanhHai_CNTT4_k64  commented on May 18, 2024, 2:34 p.m. ← edit 2

    include<bits/stdc++.h>

    using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
       return a.first<b.first; 
}
 int main(){
    int n,x,t;
    cin>>n>>t;
    int a[n];
    pair<int,int> p[n];
    for(int i=0;i<n;i++){
    cin>>a[i];
    p[i].first=a[i];
    p[i].second=i+1;
     }
    sort(p,p+n,cmp);
    for(int i=0;i<t;i++){
        cin>>x;
        int l=0,r=n-1;
        int res=INT_MAX;
        int ok=0;
        while(l<=r){
        int m=(l+r)/2;
        if(p[m].first<=x){
        ok=1;
        if(res>p[m].second)res=p[m].second;
        l=m+1;
         }
              else
                r=m-1;
            }
     if(ok==1)
    cout<<res<<endl;
     else
    cout<<0;
         }
    return 0;
     }

    ae giúp mình xem sai ở đâu với ạ <3


  • 1
    TICHPX  commented on March 24, 2024, 2:21 p.m.

    500 anh em kiểm tra code giúp Tichpx với nhé

    #include<bits/stdc++.h>
using namespace std;
int main()
{
    map<int,int> M;
    int n,x,m;
    cin>>n>>m;
    M[INT_MAX]=0;
    for(int i=1;i<=n;i++) 
    {
        cin>>x;     
        if(M.find(-x)==M.end()) M[-x]=i;        
    }
    while(m--)
    {
        cin>>x;
        auto it=M.lower_bound(-x);
        cout<<it->second<<"\n";
    }
}

    • 2
      NguyenHaKien_CNTT4_K63  commented on March 25, 2024, 1:58 a.m.

      output của thầy không phải phần tử đầu tiên ạ, thầy thử

      2 1
4 5
5

  • -1
    rfcuongtay  commented on March 16, 2023, 6:35 a.m. ← edit 2 
    
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,q;
    scanf("%d %d", &n, &q);
    int a[1000000], b[1000000];
    for(int i=1;i<=n;i++) scanf("%d", a+i);
    for(int j=1;j<=q;j++) {
    scanf("%d", b+j); 

        int d=0; 
        for(int i=1;i<=n;i++){
            if(b[j]>=a[i]){ d=i; 
        break;}  
        }
        if(d){

        printf("%d\n", d); } else printf("0\n"); 
    } 

}

    ae chỉ hộ em lỗi TLE vs ạ e bị từ test 4