oj.uz

Submission #25140

# Submission time Handle Problem Language Result Execution time Memory
25140 2017-06-20T08:09:33 Z zoomswk Global Warming (NOI13_gw) C++14
40 / 40
 413 ms 12836 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

pair<int, int> h[1000005];
int par[1000005];

int findpar(int x){
    if(par[x] != x) par[x] = findpar(par[x]);
    return par[x];
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &h[i].first);
        h[i].second = i;
    }
    sort(h, h+n);
    int res = 0, cur = 0;
    for(int i=0; i<=n; i++) par[i] = n;
    for(int i=n-1; i>=0; i--){
        cur++;
        par[h[i].second] = h[i].second;
        if(i == 0 || h[i].first != h[i-1].first){
            int ptr = i;
            while(ptr < n && h[ptr].first == h[i].first){
                int pos = h[ptr].second;
                int u = findpar(pos);
                if(pos != n-1){
                    int v = findpar(pos+1);
                    if(v != n && u != v) par[v] = u, cur--;
                }
                if(pos != 0){
                    int v = findpar(pos-1);
                    if(v != n && u != v) par[v] = u, cur--;
                }
                ptr++;
            }
            if(cur > res) res = cur;
        }
    }
    printf("%d", res);
    return 0;
}

Compilation message

gw.cpp: In function 'int main()':
gw.cpp:17:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
gw.cpp:19:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &h[i].first);
                                 ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12836 KB Output is correct
2 Correct 0 ms 12836 KB Output is correct
3 Correct 0 ms 12836 KB Output is correct
4 Correct 0 ms 12836 KB Output is correct
5 Correct 0 ms 12836 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12836 KB Output is correct
2 Correct 23 ms 12836 KB Output is correct
3 Correct 23 ms 12836 KB Output is correct
4 Correct 29 ms 12836 KB Output is correct
5 Correct 33 ms 12836 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12836 KB Output is correct
2 Correct 23 ms 12836 KB Output is correct
3 Correct 36 ms 12836 KB Output is correct
4 Correct 29 ms 12836 KB Output is correct
5 Correct 46 ms 12836 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 12836 KB Output is correct
2 Correct 413 ms 12836 KB Output is correct
3 Correct 376 ms 12836 KB Output is correct
4 Correct 379 ms 12836 KB Output is correct
5 Correct 379 ms 12836 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 12836 KB Output is correct
2 Correct 353 ms 12836 KB Output is correct
3 Correct 349 ms 12836 KB Output is correct
4 Correct 273 ms 12836 KB Output is correct
5 Correct 286 ms 12836 KB Output is correct