# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
477879 | sumit_kk10 | Global Warming (NOI13_gw) | C++17 | 547 ms | 65540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1000003;
const int MOD = 1e9 + 7;
void solve(){
int n;
cin >> n;
vector<ll> a(n);
for(int i = 0; i < n; ++i)
cin >> a[i];
vector<pair<long long, int> > comp;
for(int i = 0; i < n; ++i)
comp.push_back({a[i], i});
sort(comp.begin(), comp.end());
int ct = 1;
a[comp[0].second] = ct;
for(int i = 1; i < comp.size(); ++i){
if(comp[i].first != comp[i - 1].first)
++ct;
a[comp[i].second] = ct;
}
vector<int> pos[ct + 2];
for(int i = 0; i < n; ++i)
pos[a[i]].push_back(i);
int x = 0;
for(int j = 0; j < n; ++j){
int cur = j;
while(a[cur] > 1 and cur < n)
++cur;
if(cur != j){
j = cur - 1;
++x;
}
}
vector<bool> mp(n + 1, 0);
for(auto k : pos[1])
mp[k] = true;
int ans = x;
for(int i = 2; i <= ct; ++i){
for(auto k : pos[i]){
if(k >= 1 and mp[k - 1] and mp[k + 1]){
--x;
mp[k] = true;
continue;
}
if(k >= 1 and mp[k - 1]){
if(k == n - 1) --x;
mp[k] = true;
continue;
}
if(mp[k + 1]){
if(k == 0) --x;
mp[k] = true;
continue;
}
if(k != 0 and k != n - 1)
x++;
mp[k] = true;
}
ans = max(ans, x);
}
cout << ans << "\n";
}
int main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |