ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1613. For Fans of Statistics

Помогите TLE №6 на C++!!!
Posted by Timur 19 Sep 2018 15:50
Я перепробовал все методы, чтобы ускорить её, но всё равно моя программа на 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;
}
Re: Помогите TLE №6 на C++!!!
Posted by ToadMonster 20 Sep 2018 13:35
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.
Re: Помогите TLE №6 на C++!!!
Posted by Timur 20 Sep 2018 16:40
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.
Re: Помогите TLE №6 на C++!!!
Posted by ToadMonster 20 Sep 2018 17:43
> but I lost cities order
*sigh*

struct city {
int value;
int number;
};
Re: Помогите TLE №6 на C++!!!
Posted by Timur 26 Sep 2018 16:16
But how do you make lower bound with struct?
Re: Помогите TLE №6 на C++!!!
Posted by ToadMonster 26 Sep 2018 17:35
cin >> l >> r >> x;
city key;
key.number = l;
key.value = x;
auto it = std::lower_bound(cities.begin(), cities.end(), key);
Re: Помогите TLE №6 на C++!!!
Posted by Danila 6 Nov 2018 17:45
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 ;
}
}
Re: Помогите TLE №6 на C++!!!
Posted by ToadMonster 6 Nov 2018 21:02
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