Submission #973712

#TimeUsernameProblemLanguageResultExecution timeMemory
973712JwFXoizFancy Fence (CEOI20_fancyfence)C++14
12 / 100
1 ms604 KiB
#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 (stderr)

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;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...