fork download

copy

#include <iostream>
using namespace std;
 
int main() {
	// your code goes here
	return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin);
#define writeFile freopen("output","w",stdout);
#define fastIO ios::sync_with_stdio(0);
typedef pair<int ,int> ii;
typedef unsigned long long ULL;
bool cmp(ii a,ii b){
    return a.first<b.first;
}
 
struct Node{
    Node *l,*r;
    int val;
    int pref,suf;
    int sz;
    Node(){
        l=r=NULL;
        val=pref=suf=0;
        sz=1;
    }
    Node(int val){
        this->val = pref=suf = val;
        this->sz = 1;
    }
    Node(Node *l,Node *r){
        this->sz = l->sz+r->sz;
        this->l = l;
        this->r = r;
        this->pref = l->pref;
        if (l->sz==l->pref)
            this->pref+=r->pref;
        this->suf = r->suf;
        if (r->sz==r->suf)
            this->suf+=l->suf;
        this->val = max(l->val,max(r->val,l->suf+r->pref));
    }
};
const int N=100005;
ii arr[N];
int comp[N];
int n,q;
int st[N];
Node* tree[N+1];
 
Node* build(int l,int r){
    if (l==r) return new Node();
    int mid=(l+r)>>1;
    return new Node(build(l,mid),build(mid+1,r));
}
Node* insert(Node *node,int l,int r,int idx){
    if (l==r){
        return new Node(1);
    }
    int mid = (l+r)>>1;
    if (idx<=mid){
        return new Node(insert(node->l,l,mid,idx),node->r);
    }
    return new Node(node->l,insert(node->r,mid+1,r,idx));
}
Node* query(Node *node,int l,int r,int ll,int rr){
    if (l>rr || r<ll||r<l || rr<ll) return new Node();
    if (l>=ll && r<=rr) return node;
    int mid = (l+r)>>1;
    return new Node(query(node->l,l,mid,ll,rr),query(node->r,mid+1,r,ll,rr));
}
 
int getH(int val){
    ii* it = lower_bound(arr+1,arr+n+1,make_pair(arr[st[val]].first,0),cmp);
    if (it->first==arr[st[val]].first) return st[val];
    return st[comp[(++it)->second]];
}
 
 
 
 
int main(){
#ifndef ONLINE_JUDGE
    readFile;
#endif
    fastIO;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].first,arr[i].second=i;
    }
    sort(arr+1,arr+n+1);
    int pointer=1;
    comp[arr[1].second] = 1;
    st[1] = arr[1].second;
    for(int i=2;i<=n;i++){
        if (arr[i].first!=arr[i-1].first) {
            pointer++;
            st[pointer] = i;
        }
        comp[arr[i].second] = pointer;
    }
    tree[n+1] = build(1,n);
    for(int i=n;i>0;i--){
        tree[i] = insert(tree[i+1],1,n,arr[i].second);
    }
    cin>>q;
    while (q--){
        int l,r,w; cin>>l>>r>>w;
        int ll=0,rr=pointer,res=0;
        while (ll<rr){
            if (ll>=rr) break;
            int mid = (ll+rr+1)>>1;
            int h = getH(mid);
            int quer = query(tree[h],1,n,l,r)->val;
            if (quer>=w){
                ll=mid;
            }
            else rr = mid-1;
        }
        cout<<arr[st[ll]].first<<"\n";
    }
}

prog.cpp:7:2: error: stray '#' in program
 }#include <bits/stdc++.h>
  ^
prog.cpp:7:3: error: 'include' does not name a type
 }#include <bits/stdc++.h>
   ^
prog.cpp:11:27: error: 'atan' was not declared in this scope
 const double PI = atan(1.0);
                           ^
prog.cpp: In function 'int getH(int)':
prog.cpp:78:75: error: no matching function for call to 'lower_bound(ii*, ii*, std::pair<int, int>, bool (&)(ii, ii))'
     ii* it = lower_bound(arr+1,arr+n+1,make_pair(arr[st[val]].first,0),cmp);
                                                                           ^
In file included from /usr/include/c++/5/bits/char_traits.h:39:0,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from prog.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:996:5: note: candidate: template<class _ForwardIterator, class _Tp> _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)
     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
     ^
/usr/include/c++/5/bits/stl_algobase.h:996:5: note:   template argument deduction/substitution failed:
prog.cpp:78:75: note:   candidate expects 3 arguments, 4 provided
     ii* it = lower_bound(arr+1,arr+n+1,make_pair(arr[st[val]].first,0),cmp);
                                                                           ^
prog.cpp: In function 'int main()':
prog.cpp:86:5: error: redefinition of 'int main()'
 int main(){
     ^
prog.cpp:4:5: note: 'int main()' previously defined here
 int main() {
     ^
prog.cpp:95:23: error: 'sort' was not declared in this scope
     sort(arr+1,arr+n+1);
                       ^

Standard output is empty