제출 #1329097

#제출 시각아이디문제언어결과실행 시간메모리
1329097michael12Pilot (NOI19_pilot)C++20
40 / 100
1099 ms136148 KiB
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
const int oo = 1e18;
const int inf = 1e18;
struct ST{
    int n;
    vector<int> tree;
    ST(int sz){
        n = sz;
        tree.resize(4 * n);
    }
    void build(int node, int start, int end, vector<int>& T){
        if(start == end){
           tree[node] = T[start];
        }
        else{
            int mid = (start + end) / 2;
            build(2 * node, start, mid, T);
            build(2 * node + 1, mid + 1, end, T);
            tree[node] = max(tree[2 * node], tree[2 * node + 1]);
        }
    }
    int query(int node, int start, int end, int l, int r){
        if(start > r || end < l) return -inf;
        if(start >= l && end <= r) return tree[node];
        int mid = (start + end) / 2;
        int l1 = query(2 * node, start, mid, l, r);
        int r1 = query(2 * node + 1, mid + 1, end, l, r);
        return max(l1, r1);
    }
    int get(int node, int start, int end, int id){
        if(start == end){
            return tree[id];
        }
        else{
            int mid = (start + end) / 2;
            if(mid >= id){
                return get(2 * node, start, mid, id);
            }
            else{
                return get(2 * node + 1, mid + 1, end, id);
            }
        }
    }
    
 
};
signed main(){
   int n, m;
   cin >> n >> m;
   vector<int> a(n);
   for(int i = 0; i < n; i++){
    cin >> a[i];
   }
   vector<int> q(m);
   for(int i = 0; i < m; i++){
       cin >> q[i];
   }
   ST st(n);
   st.build(1, 0, n - 1, a);

   vector<int> g;
   for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        int a = st.query(1, 0, n - 1, i, j);
        g.push_back(a);
    }
   }
   sort(g.begin(), g.end());
   vector<int> pref(g.size());
   
   for(int i = 0; i < m; i++){
       int id = upper_bound(g.begin(), g.end(), q[i]) - g.begin();
       cout << id << endl;
   }


   

    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...