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

Cho dãy số nguyên có n phần tử a1,a2,...,an. 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≤n,q≤105), 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á 109.

q dòng tiếp theo mỗi dòng chứa đúng một số nguyên x (−109≤x≤109).

Đầ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 ≤x, xuất ra 0.

Subtask

30% số test có n,q≤1000.

Ví dụ

Đầu vào:

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

Đầu ra:

Copy
5
1
2
QDUY

Comments


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

    include<bits/stdc++.h>

    Copy
    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é

    Copy
    #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ử

      Copy
      2 1
4 5
5

  • -1
    rfcuongtay  commented on March 16, 2023, 6:35 a.m. ← edit 2
    Copy
    
#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