Hello,
I am trying to solve https://cses.fi/problemset/task/1163, but i am getting TLE on test cases 8 to 12 .
CODE
Can somebody explain? A lot of people solved that problem, I think I am missing something. Thanks.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Hello,
I am trying to solve https://cses.fi/problemset/task/1163, but i am getting TLE on test cases 8 to 12 .
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n,x;
cin>>x>>n;
multiset<long long> mul;
vector<long long> p;
p.push_back(0);
p.push_back(x);
vector<long long> q(n+1),ans(n+1);
for(long long i=0;i<n;i++)
{
long long val;
cin>>val;
p.push_back(val);
q[i+1]=val;
}
sort(p.begin(),p.end());
map<long long,long long> fwd,bk;
long long sz=p.size();
fwd[0]=p[1];
bk[x]=p[sz-2];
for(long long i=1;i<=(sz-2);i++)
{
fwd[p[i]]=p[i+1];
bk[p[i]]=p[i-1];
}
for(long long i=1;i<=(sz-1);i++)
{
mul.insert(p[i]-p[i-1]);
}
for(long long i=n;i>=1;i--)
{
ans[i]=*mul.rbegin();
long long val=q[i];
mul.erase(fwd[val]-val);
mul.erase(val-bk[val]);
mul.insert(fwd[val]-bk[val]);
long long a=fwd[val];
long long b=bk[val];
bk[a]=b;
fwd[b]=a;
}
for(long long i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<'\n';
return 0;
}
Can somebody explain? A lot of people solved that problem, I think I am missing something. Thanks.
Название |
---|