Submission #945597

#	Time	Username	Problem	Language	Result	Execution time	Memory
945597		salmon	Fancy Fence (CEOI20_fancyfence)	C++14	12 / 100	1 ms	2396 KiB

fancyfence

#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 (stderr)

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27