oj.uz

Submission #310999

# Submission time Handle Problem Language Result Execution time Memory
310999 2020-10-09T02:52:45 Z urd05 Fancy Fence (CEOI20_fancyfence) C++14
25 / 100
 102 ms 8168 KB 
#include <bits/stdc++.h>
using namespace std;

long long h[100000];
long long w[100000];
long long pos[100000];
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P>> pq;
const int mod=1e9+7;
long long inv2=5e8+4;

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%lld",&h[i]);
        pq.push(P(h[i]+1,i));
    }
    set<long long> s;
    long long sum=0;
    for(int i=0;i<n;i++) {
        scanf("%lld",&w[i]);
        sum+=w[i];
        if (i) {
            pos[i]=pos[i-1]+w[i-1];
        }
    }
    s.insert(0);
    s.insert(sum);
    sum%=mod;
    long long pl=(sum*(sum+1));
    pl%=mod;
    pl*=inv2;
    pl%=mod;
    long long prev=0;
    long long ret=0;
    while (!pq.empty()) {
        long long save=pl;
        int now=pq.top().first;
        while (!pq.empty()&&pq.top().first==now) {
            long long p=pos[pq.top().second];
            long long d=*(--(s.upper_bound(p)));
            long long u=*s.lower_bound(p+w[pq.top().second]);
            long long len=(u-d)%mod;
            pl-=(((len*(len+1))%mod)*inv2)%mod;
            len=(p-d)%mod;
            pl+=(((len*(len+1))%mod)*inv2)%mod;
            len=(u-p-w[pq.top().second])%mod;
            pl+=(((len*(len+1))%mod)*inv2)%mod;
            pl%=mod;
            pl+=mod;
            pl%=mod;
            s.insert(p);
            s.insert(p+w[pq.top().second]);
            pq.pop();
        }
        long long len=now;
        ret+=(save*(((len*(len+mod-1))%mod)*inv2)%mod)%mod;
        len=prev;
        ret-=(save*(((len*(len+mod-1))%mod)*inv2)%mod)%mod;
        ret%=mod;
        ret+=mod;
        ret%=mod;
        prev=now;
    }
    printf("%lld",ret);
}

Compilation message

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

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 46 ms 4216 KB Output is correct
4 Correct 102 ms 8168 KB Output is correct
5 Correct 98 ms 8168 KB Output is correct
6 Correct 86 ms 8148 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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