oj.uz

Submission #674405

# Submission time Handle Problem Language Result Execution time Memory
674405 2022-12-24T03:34:13 Z vjudge1 Global Warming (NOI13_gw) C++17
40 / 40
 211 ms 22332 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int par[N], n;
bool mark[N];
ii a[N];

int anc(int u)
{
    return par[u] == u ? u : par[u] = anc(par[u]);
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) 
        cin >> a[i].F, a[i].S = i, par[i] = i;
    sort(a + 1, a + 1 + n, greater<ii>());
    
    int cnt = 0, res = 0;
    for(int i = 1; i <= n; i++)
    {
        cnt++;
        int pos = a[i].S;
        mark[pos] = 1;
        if(mark[pos - 1])
        {
            cnt--;
            par[pos] = anc(pos - 1);
        }
        if(mark[pos + 1])
        {
            cnt--;
            par[pos] = anc(pos + 1);
        }
        if(i < n && a[i].F != a[i + 1].F)
            res = max(res, cnt);
    }
    cout << res;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1512 KB Output is correct
2 Correct 16 ms 1492 KB Output is correct
3 Correct 15 ms 1516 KB Output is correct
4 Correct 16 ms 1492 KB Output is correct
5 Correct 18 ms 1500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1524 KB Output is correct
2 Correct 12 ms 2172 KB Output is correct
3 Correct 18 ms 2380 KB Output is correct
4 Correct 18 ms 2380 KB Output is correct
5 Correct 17 ms 2388 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 13116 KB Output is correct
2 Correct 195 ms 22304 KB Output is correct
3 Correct 204 ms 22292 KB Output is correct
4 Correct 201 ms 22332 KB Output is correct
5 Correct 187 ms 21708 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 12944 KB Output is correct
2 Correct 203 ms 13184 KB Output is correct
3 Correct 208 ms 21616 KB Output is correct
4 Correct 171 ms 15824 KB Output is correct
5 Correct 171 ms 15848 KB Output is correct