Submission #372250

#	Time	Username	Problem	Language	Result	Execution time	Memory
372250		gustason	Travels (LMIO17_keliones)	C++11	45 / 100	1090 ms	34284 KiB

keliones

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
#define int ll
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 = (tree[idx].sum + (r-l+1) * tree[idx].delta) % 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[child].delta + tree[par].delta);
        if (tree[child].delta < 0) {
            tree[child].delta += mod;
        } else 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;
            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;
    }
    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;
    }
};
const int maxN = 2e5 + 5;
vector<int> adj[maxN];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    vector<int> add(n+1);
    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;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55