oj.uz

Submission #945597

# Submission time Handle Problem Language Result Execution time Memory
945597 2024-03-14T05:28:36 Z salmon Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
priority_queue<pair<long long int,int>> pq;
long long int h[100100];
long long int w[100100];
int parent[100100];
long long int sise[100100];
long long int mal = 0;
long long int mod = 1'000'000'007;
bool a[100100];
long long int ans = 0;

int root(int i){
    if(parent[i] == i) return i;
    return parent[i] = root(parent[i]);
}

void connect(int a, int b){
    a = root(a);
    b = root(b);

    if(a == b) return;

    mal -= (sise[a] * (sise[a] + 1)/2) + (sise[b] * (sise[b] + 1)/2);
    sise[a] += sise[b];
    mal += (sise[a] * (sise[a] + 1)/2);
    mal %= mod;
    parent[b] = a;
}

int main(){
    scanf(" %d",&N);

    for(int i = 0; i < N; i++){
        parent[i] = i;

        scanf(" %lld",&h[i]);
        pq.push(make_pair(h[i],i));
        a[i] = false;
    }

    pq.push({0,N});

    for(int i = 0; i < N; i++){
        scanf(" %lld",&w[i]);
        sise[i] = w[i];
    }


    long long int ph = 0;

    while(!pq.empty()){
        long long int h1 = pq.top().first;
        int it = pq.top().second;
        pq.pop();
        //printf("%lld ",mal);

        if(mal != 0){
            ans += (ph * (ph + 1) / 2 - h1 * (h1 + 1) / 2) % mod * mal;
            ans %= mod;
        }

        ph = h1;

        a[it] = true;
        mal += sise[it] * (sise[it] + 1 )/2;
        mal %= mod;

        if(it < N - 1 && a[it + 1]){
            connect(it, it + 1);
        }
        if(it > 0 && a[it - 1]){
            connect(it, it - 1);
        }
    }

    printf("%lld",ans);
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
fancyfence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf(" %lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf(" %lld",&w[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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