#include<bits/stdc++.h>
using namespace std;
int dizi[1000007];
vector<int> cnt[1000007];
list<int> r[1000007];
bool visit[1000007];
int main()
{
// cout << "yarrr";
int n;
cin >> n;
// cout << "ar";
// memset(cnt,-1,sizeof(cnt));
// memset(r,-1,sizeof(r));
for(int i=0;i<n;i++)
{
cin >> dizi[i];
}
// cout << "adasd";
cnt[dizi[n-1]].push_back(n-1);
for(int i=n-2;i>=0;i--)
{
// cout << i << " ";
if(cnt[dizi[i]-1].size()>0)
{
for(auto x:cnt[dizi[i]-1])
r[i].push_front(x);
// r[i].push_back(cnt[dizi[i]-1]);
}
cnt[dizi[i]].push_back(i);
}
// cout << endl;
// for(int i=0;i<n;i++)
// {
// for(auto x:r[i])
// cout << x << " ";
// cout << endl;
// // cout << r[i] << " ";
// }
// free(cnt);
// ~cnt;
delete[] cnt;
long long int sayac=0;
for(int i=0;i<n;i++)
{
if(visit[i]==1)
continue;
sayac++;
while(!r[i].empty()&&visit[r[i].front()]==1)
r[i].pop_front();
int ptr=i;
while(!r[ptr].empty() && visit[r[ptr].front()]!=1)
{
visit[ptr]=1;
ptr=r[ptr].front();
// cout << ptr << " ";
}
visit[ptr]=1;
// cout << endl;
}
// cout << visit[7] << " ";
cout << sayac;
}
Compilation message
baloni.cpp: In function 'int main()':
baloni.cpp:45:11: warning: deleting array 'cnt'
delete[] cnt;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
95864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
115 ms |
95992 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
113 ms |
96368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
113 ms |
96900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
527 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
526 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
459 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
463 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
498 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
495 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
