oj.uz

Submission #922629

# Submission time Handle Problem Language Result Execution time Memory
922629 2024-02-05T20:42:13 Z BigBadBully Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 22 ms 2652 KB 
#include<bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mod = 1'000'000'000 + 7;
struct seg{
    int l,r,h;
    
};
bool operator<(const seg& a, const seg& b){
    return a.l < b.l;
};
bool operator>(const seg& a, const seg& b){
    return a.l < b.l;
};

int sum (int l,int r)
{
    
    return ((r*r+r)/2 - (l*l-l)/2)%mod;
}

const int dva = 500000004LL;

void solve()
{

    int n;
    cin >> n;
    int at = 0;
    vector<seg> v(n);
    for (int i = 0; i<n; i++)
    {
        int aew;
        cin >> aew;
        v[i].h = aew;
    }
    for (int i = 0; i < n; i++)
    {
        int w;
        cin >> w;
        v[i].l = at;
        v[i].r = at+w-1;
        at=v[i].r+1;
    }
    int ans = 0;
    int cur = 0;
    set<pair<int,int>> cat;
    
    
    cat.insert({v[0].l,v[n-1].r});
    

    auto remove = [&](seg x)
    {
        pair<int,int> big = *(--cat.upper_bound({x.l,x.r}));
      
        int biglen = big.ss-big.ff+1;
        int oduz =(int)((((__uint128_t)biglen)*((__uint128_t)biglen)+((__uint128_t)biglen))/((__uint128_t)2)%mod);
        cur-=oduz;
        cur+=7*mod;
        cur%=mod;

        if (x.l-1 >= big.ff)
            cat.insert({big.ff,x.l-1});
        if (x.r+1 <= big.ss)
            cat.insert({x.r+1,big.ss});
        

        int len1 = max(0LL,(x.l-1 - big.ff)+1);
        int len2 = max(0LL,big.ss - x.r);

        int oduz1 =(int)((((__uint128_t)len1)*((__uint128_t)len1)+((__uint128_t)len1))/((__uint128_t)2)%mod);
        int oduz2 =(int)((((__uint128_t)len2)*((__uint128_t)len2)+((__uint128_t)len2))/((__uint128_t)2)%mod);

        cat.erase(big);
        cur+=oduz1+oduz2;
        cur%=mod;
    };
    auto comp = [&](seg& mile, seg& alen){
        return (mile.h < alen.h);
    };
    int globallen = (v[n-1].r - v[0].l + 1);
    sort(v.begin(),v.end(),comp);
    int prev = 0;
    int same = 0;
    
    globallen%=mod;
    cur = globallen*globallen+globallen;
    cur%=mod;
    cur*=dva;
    cur%=mod;

    for (int i = 0; i < n; i++)
    {
       
        
        
        if (i!=0 && v[i].h != v[i-1].h)
        {
            ans+=(cur*(sum(prev+1,v[i-1].h)))%mod;
            ans%=mod;
            for (int j = i-1; j >= same; j--)
                remove(v[j]);
            
            same = i;
            prev = v[i-1].h;
        }
    }

    ans+=(cur*(sum(prev+1,v[n-1].h)))%mod;
    ans%=mod;

    cout << ans << '\n';
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input1.txt", "r", stdin);
    solve();
    
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 10 ms 1628 KB Output is correct
4 Correct 17 ms 2652 KB Output is correct
5 Correct 17 ms 2648 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 8 ms 1628 KB Output is correct
5 Correct 17 ms 2652 KB Output is correct
6 Correct 17 ms 2652 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 10 ms 1628 KB Output is correct
10 Correct 22 ms 2648 KB Output is correct
11 Correct 22 ms 2652 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 18.0

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