oj.uz

Submission #361695

# Submission time Handle Problem Language Result Execution time Memory
361695 2021-01-31T09:26:26 Z stefdasca Global Warming (NOI13_gw) C++14
40 / 40
 321 ms 19820 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define FOR(i, a, b) for (signed ll i = (signed ll)(a); i < (signed ll)(b); i++)
#define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--)
#define vll vector<ll>
#define sll set<ll>
#define ld long double
#define inf 1000000000000000000
#define mll multiset<ll>
#define vpll vector<pll>
#define nn << "\n"
#define ss << " "
//10^8 operations per second
//greatest int is 2,147,483,647
//greates long long is 9.22337204e18
 
//ALL FUNCTIONS SHOULD BE LL!!!!
vector<int> parent(1000000),sz(1000000);
void make_set(ll v) {
    parent[v] = v;
    sz[v] = 1;
}
int find_set(ll v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void unite(ll a, ll b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b])
            swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n; cin>>n;
 
    vector<pair<int, int> > v(n);
 
    FOR(i,0,n){
        cin>>v[i].first; v[i].second=i;
    }
    
    sort(v.rbegin(),v.rend());
    vector<bool> risen(n+5);
    ll curr=0,ans=1;
    FOR(i,0,n){
        make_set(v[i].second);
        curr++;
        risen[v[i].second]=1;
        if (v[i].second && risen[v[i].second-1]){
            unite(v[i].second-1,v[i].second); --curr;
        }
        if (v[i].second+1 < n && risen[v[i].second+1]){
            unite(v[i].second+1,v[i].second);--curr;
        }
        if (i == n-1 || v[i+1].first != v[i].first) 
			ans=max(ans,curr);
    }
    cout<<ans;
 
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 6 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9196 KB Output is correct
2 Correct 27 ms 9196 KB Output is correct
3 Correct 27 ms 9196 KB Output is correct
4 Correct 27 ms 9196 KB Output is correct
5 Correct 27 ms 9324 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9836 KB Output is correct
2 Correct 22 ms 9580 KB Output is correct
3 Correct 32 ms 9836 KB Output is correct
4 Correct 30 ms 9836 KB Output is correct
5 Correct 30 ms 9708 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19772 KB Output is correct
2 Correct 297 ms 17900 KB Output is correct
3 Correct 321 ms 17516 KB Output is correct
4 Correct 312 ms 17476 KB Output is correct
5 Correct 296 ms 18028 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 19820 KB Output is correct
2 Correct 308 ms 18028 KB Output is correct
3 Correct 319 ms 17828 KB Output is correct
4 Correct 262 ms 17900 KB Output is correct
5 Correct 274 ms 19052 KB Output is correct