Помогите 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++!!!
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++!!!
> 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++!!!
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++!!!
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