oj.uz

Submission #534861

# Submission time Handle Problem Language Result Execution time Memory
534861 2022-03-09T04:37:26 Z leinad2 Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 460 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int A[100010], B[100010], n, i, j, k, a, b, C[100010], mod=1e9+7;
int ans;
int f(int a)
{
    return ((a*(a+1))/2)%mod;
}
int g(int a)
{
    return ((f(a)*(2*a+1))%mod*333333336)%mod;
}
int get(int a, int b, int c)
{
    a%=mod;b%=mod;c%=mod;
    int ans=0;
    ans+=g(a)*c;
    ans+=g(c)*a;
    ans+=f(a)*c;
    ans+=f(c)*a;
    ans+=((f(a)*f(b))%mod*(2*b+2))%mod;
    ans+=(((b+b*b)%mod*a)%mod*b)%mod;
    ans%=mod;
    if(ans%2)ans+=mod;
    ans/=2;
    return ans;
}
struct seg
{
    pair<int, int>seg[400010];
    void init(int id, int s, int e)
    {
        if(s==e)
        {
            seg[id]={B[s], s};
            return;
        }
        int m=s+e>>1;
        init(id*2, s, m);init(id*2+1, m+1, e);
        seg[id]=min(seg[id*2], seg[id*2+1]);
    }
    pair<int, int>get(int id, int s, int e, int l, int r)
    {
        if(e<l||r<s)return {1e9, 1e9};
        if(l<=s&&e<=r)return seg[id];
        int m=s+e>>1;
        return min(get(id*2, s, m, l, r), get(id*2+1, m+1, e, l, r));
    }
}seg;
void dnc(int l, int r)
{
    if(l>r)return;
    pair<int, int>p=seg.get(1, 1, n, l, r);
    int x=p.second;
    int res=0;
    int a=C[x-1]-C[l-1], b=A[x], c=C[r]-C[x];
    res+=f(b);
    res+=a*c;
    res+=b*c;
    res+=a*b;
    res%=mod;
    res*=f(p.first);
    res%=mod;
    ans+=res;
    ans%=mod;
    dnc(l, x-1);dnc(x+1, r);
}
main()
{
    ios_base::sync_with_stdio(!cin.tie(NULL));
    for(cin>>n;i++<n;)cin>>B[i];
    for(i=0;i++<n;)
    {
        cin>>A[i];
        C[i]=C[i-1]+A[i];
    }
    seg.init(1, 1, n);
    dnc(1, n);
    cout<<ans;
}

Compilation message

fancyfence.cpp: In member function 'void seg::init(long long int, long long int, long long int)':
fancyfence.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int m=s+e>>1;
      |               ~^~
fancyfence.cpp: In member function 'std::pair<long long int, long long int> seg::get(long long int, long long int, long long int, long long int, long long int)':
fancyfence.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int m=s+e>>1;
      |               ~^~
fancyfence.cpp: At global scope:
fancyfence.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 332 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 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 1 ms 336 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 336 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 320 KB Output is correct
2 Incorrect 1 ms 336 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 316 KB Output is correct
2 Incorrect 1 ms 460 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 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -