제출 #853646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853646		divad	Sum Zero (RMI20_sumzero)	C++14	0 / 100	13 ms	52312 KiB

sumzero

#include <bits/stdc++.h>
#define ends saradanciu
using namespace std;
const int LMAX = 20;
const int NMAX = 4e5+2;
int n,q,c[NMAX],x,y,nxt[LMAX][NMAX];
vector<int> v[NMAX],ends[NMAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    map<int, vector<int>> mp;
    int pref = 0;
    mp[pref].push_back(0);
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        pref += c[i];
        for(int it: mp[pref]){
            ends[it+1].push_back(i);
            break;
        }
        mp[pref].push_back(i);
    }
    set<int> s;
    s.insert(n+1);
    for(int i = n; i >= 1; i--){
        for(int it: ends[i]){
            s.insert(it);
        }
        nxt[0][i] = *s.upper_bound(i);
    }
    for(int j = 1; j < LMAX; j++){
        for(int i = n+1; i >= 1; i--){
            nxt[j][i] = nxt[j-1][nxt[j-1][i]];
        }
        for(int i = 1; i <= n; i++){
            if(nxt[j][i] == 0){
                nxt[j][i] = n+1;
            }
        }
    }
    cin >> q;
    while(q--){
        cin >> x >> y;
        int ans = 0;
        for(int i = LMAX-1; i >= 0; i--){
            if(nxt[i][x] <= y){
                ans += (1<<i);
                x = nxt[i][x];
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

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