oj.uz

Submission #973712

# Submission time Handle Problem Language Result Execution time Memory
973712 2024-05-02T09:52:34 Z JwFXoiz Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int add(int a, int b)
{
    return (((a + b) % mod) + mod) % mod;
}
int mult(int a, int b)
{
    return (((a * b) % mod) + mod) % mod;
}
int sum(int l, int r)
{
    return ((r - l + 1) * (l + r) / 2) % mod;
}

int res = 0;

struct DSU
{
    int n;
    vector<int> e, val;
    void init(int N)
    {
        n = N;
        e.assign(n + 1, -1);
        val.assign(n + 1, 0);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    void makeval(int x, int y)
    {
        x = get(x);
        res = add(res, -(val[x] * (val[x] + 1) / 2));
        val[x] = y;
        res = add(res, val[x] * (val[x] + 1) / 2);
    }
    void unite(int x, int y)
    {
        x = get(x), y = get(y);
        if (x == y) return;
        if (e[x] > e[y]) swap(x, y);
        res = add(res, -(val[x] * (val[x] + 1) / 2));
        res = add(res, -(val[y] * (val[y] + 1) / 2));
        val[x] += val[y];
        val[y] = 0;
        res = add(res, val[x] * (val[x] + 1) / 2);
        e[x] += e[y];
        e[y] = x;
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int h[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i];
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++) mp[h[i]].push_back(i);
    DSU dsu;
    dsu.init(n);
    int ans = 0;
    for (auto it = mp.rbegin(); it != mp.rend(); it++)
    {
        auto &[a, b] = *it;
        for (int i : b) dsu.makeval(i, w[i]);
        for (int i : b) 
        {
            if (i - 1 >= 1 && h[i - 1] >= a) dsu.unite(i, i - 1);
            if (i + 1 <= n && h[i + 1] >= a) dsu.unite(i, i + 1);
        }
        auto it1 = it;
        it1++;
        int nxt = 0;
        if (it1 != mp.rend()) nxt = (*it1).first;
        ans = add(ans, mult(sum(nxt + 1, a), res));
    }
    cout << ans << '\n';
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:77:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto &[a, b] = *it;
      |               ^

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 604 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 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.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 #4
0 / 15.0

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