Submission #372262

#	Time	Username	Problem	Language	Result	Execution time	Memory
372262		gustason	Travels (LMIO17_keliones)	C++11	100 / 100	294 ms	20076 KiB

keliones

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int mod = 1e9 + 7;
struct SegmentTree {
    vector<ll> tree;
    int n;
    SegmentTree(vector<int>& a) {
        n = a.size();
        tree.assign(2*n, 0);

        for(int i = n; i < 2*n; i++) {
            tree[i] = a[i-n];
        }
        for(int idx = n-1; idx > 0; idx--) {
            tree[idx] = tree[2*idx] + tree[2*idx+1];
        }
    }
    void update(int idx, ll val) {
        idx += n;
        tree[idx] = val;

        while(idx > 1) {
            idx /= 2;
            tree[idx] = tree[2*idx] + tree[2*idx+1];
            tree[idx] %= mod;
        }
    }
    ll getSum(int L, int R) {
        L += n;
        R += n;
        ll sum = 0;

        while(L < R) {
            if (L % 2) {
                sum += tree[L];
                sum %= mod;
                L++;
            }
            if (R % 2) {
                R--;
                sum += tree[R];
                sum %= mod;
            }
            L /= 2, R /= 2;
        }

        return sum;
    }
};
const int maxN = 200005;
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<ll> add(n+1);
    for(int i = 0; i < n; i++) {
        cin >> add[i];
    }

    vector<ll> pref(n+1, 0);
    pref[0] = 0;
    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i-1];
        pref[i] += add[i-1];
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[b].push_back(a);
    }

    vector<int> a(n+1, 0);
    SegmentTree cnt(a), sum(a);
    for(int i = 0; i < n; i++) {
        cnt.update(i, cnt.getSum(0, i) + i);
        sum.update(i, sum.getSum(i, i+1) + sum.getSum(0, i) + pref[i]);
        for(int j : adj[i]) {
            cnt.update(i, cnt.getSum(i, i+1) - cnt.getSum(j, j+1) - 1);
            sum.update(i, sum.getSum(i, i+1) - add[j] - sum.getSum(j, j+1));
        }
        sum.update(i, sum.getSum(i, i+1) + (add[i] * cnt.getSum(i, i+1)) % mod);
    }
    cout << (sum.getSum(0, n) + mod) % mod;
    return 0;
}

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