oj.uz

Submission #25137

# Submission time Handle Problem Language Result Execution time Memory
25137 2017-06-20T08:02:56 Z zoomswk Global Warming (NOI13_gw) C++14
19 / 40
 153 ms 12484 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int h[100005];
int tmp[100005];
map<int, int> mp;
vector<int> vt[100005];
int par[100005];

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

int main(){
    int n;
    scanf("%d", &n);
    if(n > 100000) return 1;
    for(int i=0; i<n; i++){
        scanf("%d", &h[i]);
        tmp[i] = h[i];
    }
    sort(tmp, tmp+n);
    for(int i=0; i<n; i++) mp[tmp[i]] = i;
    for(int i=0; i<n; i++) vt[mp[h[i]]].push_back(i);
    int res = 0, cur = 0;
    for(int i=0; i<=n; i++) par[i] = n;
    for(int i=n-1; i>=0; i--){
        cur += vt[i].size();
        for(int j=0; j<vt[i].size(); j++){
            par[vt[i][j]] = vt[i][j];
        }
        for(int j=0; j<vt[i].size(); j++){
            int pos = vt[i][j];
            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--;
            }
        }
        if(cur > res) res = cur;
    }
    printf("%d", res);
    return 0;
}

Compilation message

gw.cpp: In function 'int main()':
gw.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<vt[i].size(); j++){
                       ^
gw.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<vt[i].size(); j++){
                       ^
gw.cpp:20:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
gw.cpp:23:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &h[i]);
                           ^

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5428 KB Output is correct
2 Correct 26 ms 5420 KB Output is correct
3 Correct 16 ms 5432 KB Output is correct
4 Correct 33 ms 5424 KB Output is correct
5 Correct 19 ms 5424 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 12484 KB Output is correct
2 Correct 79 ms 12484 KB Output is correct
3 Correct 153 ms 12484 KB Output is correct
4 Correct 153 ms 12484 KB Output is correct
5 Correct 139 ms 12484 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -