Я перепробовал все методы, чтобы ускорить её, но всё равно моя программа на 0.014 сек медленнее, чем нужно.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
    int Ia, Sa;
    string O = "";

    scanf("%d", &Ia);
    vector<int> II(Ia, 0);

    for(auto &i:II){
        scanf("%d", &i);
    }

    scanf("%d", &Sa);
    vector<int> ia(3, 0);

    for(int i = 0; i < Sa; ++i){
        scanf("%d%d%d", &ia[0], &ia[1], &ia[2]);
        auto I = II;
        stable_sort(I.begin() + ia[0] - 1, I.begin() + ia[1]);
        if(*(lower_bound(I.begin() + ia[0] - 1, I.begin() + ia[1], ia[2])) == ia[2] && lower_bound(I.begin() + ia[0] - 1, I.begin() + ia[1], ia[2]) != I.begin() + ia[1]) O += '1';
        else O += '0';
    }

    puts(O.c_str());

    return 0;
}

Sort inside tests cycle looks mistake. You drops cities order by it.
My AC solution does 1 cities full sort before tests cycle and 1 lower_bound inside.

I tried make only one full sort, but I lost cities order, but in my solution I sort only range of cities, what change nothing and then reset cities vector. This is very slow, I know it, but I can't make better.

> but I lost cities order
*sigh*

struct city {
  int value;
  int number;
};

But how do you make lower bound with struct?

cin >> l >> r >> x;
city key;
key.number = l;
key.value = x;
auto it = std::lower_bound(cities.begin(), cities.end(), key);

man, why i have error?
#include <bits/stdc++.h>

using namespace std;
struct sity
{
    int value;
    int number;
};
bool comp (sity l,sity r)
{
    if (l.value==r.value) return l.number<r.number;
    return l.value<r.value;
}
vector <sity> d;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin >> x;
        d.push_back({x,i});
    }
    int m;
    cin >> m;
    sort (d.begin(),d.end(),comp);
    for (int i=1;i<=m;i++)
    {
        int l,r,x;
        cin >> l >> r >> x;
        sity key;
        key.value=x;
        key.number=l;
        auto a1=lower_bound(d.begin(),d.end(),key);
       // cout << *a1.value << endl;
       sity s=*a1;
       if (s.number<=r && s.number>=l)
           cout << 1 ;
        else cout << 0 ;
    }
}

Your problem is?

I mean I don't like people think I'm a medium.
Compilation error?
WA error?
No error, just want to type something?

Edited by author 06.11.2018 21:03