제출 #859470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859470		sleepntsheep	Sum Zero (RMI20_sumzero)	C++17	0 / 100	5 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);

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

    cin >> q;
    for (int x, y, i = 0; i < q; ++i)
    {
        cin >> x >> y;
        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;
        //cout << it2 << ' ' <<it << '\n';
        cout << it2 - it + 1 << '\n';
    }

    return 0;
}

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