oj.uz

Submission #533291

# Submission time Handle Problem Language Result Execution time Memory
533291 2022-03-05T09:47:55 Z ddy888 Fancy Fence (CEOI20_fancyfence) C++17
27 / 100
 25 ms 3912 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, proc;

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) {
    if (same(a, b)) return;
    sz[root(b)] += sz[root(a)];
    par[root(a)] = root(b);
}
int getsize(int x) {return sz[root(x)];}

int binom(int x) {
    x %= MOD;
    return (x * (x + 1) / 2) % MOD;
}

int f(int x, int y) {
    return (binom(x) * binom(y)) % 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) {
        if (H[i] == H[i - 1]) proc.back().si += W[i];
        else proc.pb({H[i], W[i]});
    }
    int lim = proc.size();
    for (int i = 0; i < lim; ++i) blocks.pb({proc[i].fi, i});
    for (int i = 0; i < lim; ++i) par[i] = i, sz[i] = proc[i].si;
    sort(blocks.begin(), blocks.end(), [](pi a, pi b) {
        return a.fi > b.fi;
    });
    for (auto i: blocks) {
        if (i.si > 0 && proc[i.si].fi <= proc[i.si - 1].fi) {
            ans -= f(getsize(i.si - 1), proc[i.si].fi);
            merge(i.si, i.si - 1);
        } 
        if (i.si < lim - 1 && proc[i.si].fi <= proc[i.si + 1].fi) {
            ans -= f(getsize(i.si + 1), proc[i.si].fi);
            merge(i.si, i.si + 1);
        }
        ans += f(getsize(i.si), proc[i.si].fi);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 336 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 332 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 10 ms 1992 KB Output is correct
4 Correct 21 ms 3780 KB Output is correct
5 Correct 25 ms 3912 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 11 ms 2072 KB Output is correct
5 Correct 21 ms 3784 KB Output is correct
6 Correct 24 ms 3880 KB Output is correct
7 Incorrect 1 ms 336 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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