Submission #859481

#	Time	Username	Problem	Language	Result	Execution time	Memory
859481		sleepntsheep	Sum Zero (RMI20_sumzero)	C++17	0 / 100	4 ms	5724 KiB

sumzero

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 400005
#define ALL(x) x.begin(), x.end()

ll n, q, a[N], p[N];
vector<pair<int, int>> intr;

vector<pair<int, int>> remove_covering(vector<pair<int, int>> v)
{
    sort(ALL(v), [](const pair<int, int>&a, const pair<int,int>&b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    vector<int> t(N<<1);
    auto qry = [&](int l, int r, int z = 0) {
        for (l += n + 1, r += n + 2; l < r; l >>= 1, r >>= 1) {
            if (l&1) z += t[l++];
            if (r&1) z += t[--r];
        }
        return z;
    };
    auto upd = [&](int p) { for (++t[p+=n+1]; p >>= 1;) t[p] = t[p<<1] + t[p<<1|1]; };
    vector<pair<int, int>> lft;
    for (auto [x, y] : v)
        if (!qry(0, y)) upd(y), lft.push_back({x, y});
    return lft;
}

    
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i-1] + a[i];

    {
        map<ll, vector<int>> mp;
        for (int i = 1; i <= n; ++i) mp[p[i]].push_back(i);
        for (int i = 0; i < n;)
        {
            auto it = upper_bound(ALL(mp[p[i]]), i);
            if (it == mp[p[i]].end()) ++i;
            else {
                intr.emplace_back(i+1, *it);
                i = *it;
            }
        }
    }

    intr = remove_covering(intr);
    sort(ALL(intr));
    for (int i = 1; i < intr.size(); ++i)
        assert(intr[i-1].second < intr[i].first);

     
    //cout << "INTR\n"; for (auto [a,b] : intr) cout << "("<<a<<", "<<b<<")\n";

    cin >> q;
    for (int qx, qy, i = 0; i < q; ++i)
    {
        cin >> qx >> qy;
        int it, it2;
        /*
        auto it = lower_bound(ALL(intr), make_pair(x, 0)) - intr.begin();
        auto it2 = prev(lower_bound(ALL(intr), make_pair(y, 0))) - intr.begin();
        if (intr[it2].second > y) --it2;
        */
        {
            int l = 0, r = intr.size()-1;
            while (l <= r)
            {
                int y = (l+r)/2;
                if (intr[y].first >= qx) it = y, r = y - 1;
                else l = y + 1;
            }
            l = 0, r = intr.size()-1;
            while (l <= r)
            {
                int y = (l+r)/2;
                if (intr[y].second <= qy) it2 = y, l = y + 1;
                else r = y - 1;
            }
        }
        //cout << it2 << ' ' <<it << '\n';
        cout << it2 - it + 1 << '\n';
    }

    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 1; i < intr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
sumzero.cpp:98:21: warning: 'it2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |         cout << it2 - it + 1 << '\n';
      |                 ~~~~^~~~
sumzero.cpp:98:21: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]

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