oj.uz

Submission #533289

# Submission time Handle Problem Language Result Execution time Memory
533289 2022-03-05T08:56:28 Z ddy888 Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 340 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

const int MOD = 1e9 + 7;
int N, H[100010], W[100010], par[100010], sz[100010], ans;
vector<pi> blocks;

int root(int x) { return (par[x]==x)? x:par[x]=root(par[x]); }
bool same(int a, int b) { return root(a) == root(b); }
void merge(int a, int b) {
    sz[root(b)] += sz[root(a)];
    par[root(a)] = root(b);
}
int getsize(int x) {return sz[root(x)];}

int f(int ww, int hh) {
    return ((hh * (hh + 1) % MOD * ww * (ww + 1) % MOD) % MOD / 4) % MOD;
}

signed main() {
    fast;
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> H[i];
    for (int i = 1; i <= N; ++i) cin >> W[i];
    for (int i = 1; i <= N; ++i) blocks.pb({H[i], i});
    sort(blocks.begin(), blocks.end(), [](pi a, pi b) {
        return a.fi > b.fi;
    });
    for (int i = 1; i <= N; ++i) par[i] = i, sz[i] = W[i];
    for (auto i: blocks) {
        if (i.si > 1 && H[i.si] <= H[i.si - 1]) { // left 
            ans -= f(getsize(i.si - 1), H[i.si]);
            merge(i.si, i.si - 1);
        } 
        if (i.si < N && H[i.si] <= H[i.si + 1]) { // right
            ans -= f(getsize(i.si + 1), H[i.si]);
            merge(i.si, i.si + 1);
        }
        ans += f(getsize(i.si), H[i.si]);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

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 336 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 324 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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