제출 #1026282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026282		NValchanov	Sum Zero (RMI20_sumzero)	C++17	0 / 100	2 ms	4444 KiB

sumzero

#include <iostream>
#include <unordered_map>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
const int MAXN = 4e5 + 10;
const int MAXQ = 4e5 + 10;
const int MAXLOG = 18;
 
int n, q;
int a[MAXN];
int nxt[MAXN];
int lift[MAXN];
pair < int, int > queries[MAXQ];
 
unordered_map < ll, int > sums;
 
void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> queries[i].first >> queries[i].second;
    }
}
 
void fill_nxt()
{
    int minpos = MAXN - 1;
    ll cursum = 0;
 
    for(int i = n + 1; i >= 1; i--)
    {
        cursum += nxt[i];
 
        if(sums.find(cursum) != sums.end())
            minpos = min(minpos, sums[cursum]);
 
        sums[cursum] = i;
        nxt[i] = minpos;
    }

    for(int i = 1; i <= q; i++)
    {
        a[i] = 0;
    }
}
 
void solve()
{
    for(int k = MAXLOG - 1; k >= 0; k--)
    {
        for(int i = 1; i <= n + 1; i++)
        {
            lift[i] = nxt[i];
        }
        lift[MAXN - 1] = MAXN - 1;
 
        for(int j = 1; j <= k; j++)
        {
            for(int i = 1; i <= n + 1; i++)
            {
                lift[i] = lift[lift[i]];
            }
            lift[MAXN - 1] = lift[lift[MAXN - 1]];
        }
 
        for(int i = 1; i <= q; i++)
        {
            if(lift[queries[i].first] <= queries[i].second + 1)
            {
                a[i] += (1 << k);
                queries[i].first = lift[queries[i].first];
            }
        }
    }
}
 
void print()
{
    for(int i = 1; i <= q; i++)
    {
        cout << a[i] << endl;
    }
    cout << endl;
}
 
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    read();
    fill_nxt();
    solve();
    print();
 
    return 0;
}

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