oj.uz

Submission #938645

# Submission time Handle Problem Language Result Execution time Memory
938645 2024-03-05T11:41:22 Z Syrius Sum Zero (RMI20_sumzero) C++14
0 / 100
 10 ms 856 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -