#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
struct Node {
ll sum;
ll delta;
Node() {
sum = 0;
delta = 0;
}
void Reset() {
delta = 0;
}
};
struct SegTree {
int n;
vector<Node> tree;
SegTree(vector<int>& a) {
n = a.size();
tree.assign(4*n, Node());
}
void build_r(vector<int>& a, int l, int r, int idx) {
if (l == r) {
if (l < n)
tree[idx].sum = a[l];
else
tree[idx].sum = 0;
return;
}
int mid = (l + r) / 2;
build_r(a, l, mid, 2*idx+1);
build_r(a, mid+1, r, 2*idx+2);
tree[idx].sum = (tree[2*idx+1].sum + tree[2*idx+2].sum) % mod;
}
void applyAggr(int idx, int l, int r) {
tree[idx].sum += (r-l+1) * tree[idx].delta;
tree[idx].sum += mod;
tree[idx].sum %= mod;
if (l != r) {
compose(idx, 2*idx+1);
compose(idx, 2*idx+2);
}
tree[idx].Reset();
}
void compose(int par, int child) {
tree[child].delta += tree[par].delta;
tree[child].delta += mod;
tree[child].delta %= mod;
}
void updateSum(int L, int R, int val) {
updateSum_r(0, 0, n-1, L, R, val);
}
void updateSum_r(int idx, int l, int r, int& L, int& R, int& val) {
if (r < L || R < l || l >= n) {
return;
}
if (L <= l && R >= r) {
tree[idx].delta += val;
tree[idx].delta += mod;
tree[idx].delta %= mod;
return;
}
applyAggr(idx, l, r);
int mid = (l + r) / 2;
updateSum_r(2*idx+1, l, mid, L, R, val);
updateSum_r(2*idx+2, mid+1, r, L, R, val);
applyAggr(2*idx+1, l, mid);
applyAggr(2*idx+2, mid+1, r);
tree[idx].sum = (((tree[2*idx+1].sum + tree[2*idx+2].sum) % mod) + mod) % mod;
}
ll getSum(int L, int R) {
return getSum_r(0, 0, n-1, L, R);
}
ll getSum_r(int idx, int l, int r, int& L, int& R) {
if (r < L || R < l || l >= n)
return 0;
applyAggr(idx, l, r);
if (L <= l && R >= r)
return tree[idx].sum;
int mid = (l + r) / 2;
return ((getSum_r(2*idx+1, l, mid, L, R) + getSum_r(2*idx+2, mid+1, r, L, R) % mod) + mod) % mod;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> adj[n+2], add(n);
for(int i = 0; i < n; i++) {
cin >> add[i];
}
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
adj[a].push_back(b);
}
vector<int> a(n+1, 0);
SegTree sum(a), cnt(a);
for(int i = 0; i < n; i++) {
sum.updateSum(i, i, cnt.getSum(i, i) * add[i]);
cnt.updateSum(i+1, n-1, cnt.getSum(i, i) + 1);
sum.updateSum(i+1, n-1, sum.getSum(i, i) + add[i]);
for(int j : adj[i]) {
cnt.updateSum(j, j, -cnt.getSum(i, i) - 1);
sum.updateSum(j, j, -sum.getSum(i, i) - add[i]);
}
}
cout << sum.getSum(0, n-1) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
