Submission #938645

#	Time	Username	Problem	Language	Result	Execution time	Memory
938645		Syrius	Sum Zero (RMI20_sumzero)	C++14	0 / 100	10 ms	856 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define pint pair < int , int >
#define ll long long
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)

const int inf = 1e9 + 9;
const int mxn = 2e5 + 2;
const int mod = 1e9 + 7;

int a[mxn];

int main() {

    int n;
    cin >> n;

    set < pint > s , L , R;

    s.insert({0 , 0});
    int sum = 0 , id = 0;
    int rlast = -1 , llast = -1;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        auto it = s.lower_bound({sum , -inf});

        if (it == s.end() || (*it).ff != sum) s.insert({sum , -i});
        else if ((*it).ff == sum) {
            if (-(*it).ss >= rlast) {
                id++;
                rlast = i;
                llast = -(*it).ss + 1;
                L.insert({-(*it).ss + 1 , id});
                R.insert({-i , id});
            } else if (-(*it).ss >= llast) {
                L.insert({-(*it).ss + 1 , id});
                R.insert({-i , id});
            }
            s.insert({sum , -i});
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int l , r;
        cin >> l >> r;

        auto it1 = L.lower_bound({l , 0});
        auto it2 = R.lower_bound({-r , 0});

        if (it1 == L.end() || it2 == R.end()) {
            cout << 0 << '\n';
            continue;
        }
        int id1 = (*it1).ss;
        int id2 = (*it2).ss;

        if (id2 < id1) cout << 0 << '\n';
        else cout << id2 - id1 + 1 << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39