제출 #1105925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105925		horiaboeriu	Sum Zero (RMI20_sumzero)	C++17	100 / 100	362 ms	15176 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
#define MAXN 400000
#define MAXL 5
int rmq[MAXL][MAXN + 6], pozs[MAXN + 1];
long long v[MAXN + 1];
char cmp(int x, int y) {
    return v[x] < v[y];
}
int readInt() {
    int x, semn;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    semn = 1;
    if (ch == '-') {
        semn = -1;
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x * semn;
}
int calcPoz(int j, int i) {
    if (j % 4 == 0) {
        return rmq[j / 4][i];
    } else if (j % 4 == 1) {
        return rmq[j / 4][rmq[j / 4][i] + 1];
    } else if (j % 4 == 2) {
        return rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][i] + 1] + 1] + 1];
    } else {
        return rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][i] + 1] + 1] + 1] + 1] + 1] + 1] + 1];
    }
}
int main()
{
    int n, q, i, poz, j, p, p2, st, dr, rez, x0, x;
    long long y;
    //fac sume partiale si secv st dr are suma 0 daca sp[dr] = sp[st - 1]
    //deci trebuie sa caut numere egale dupa ce fac sume partiale
    //la fiecare interval gasesc prima pereche de nr egale, cea in care poz din dr este cat mai mica si dupa
    //tin cu un binary lifting care sunt urmatoarele si vad asa cate sunt pana la dr
    //scot jumatate din rmq ca sa nu iau mle
    n = readInt();
    for (i = 1; i <= n; i++) {
        v[i] = v[i - 1] + readInt();
        rmq[0][i] = n + 1;
        pozs[i] = i;
    }
    sort(pozs + 1, pozs + n + 1, cmp);
    y = v[pozs[1]];
    v[pozs[1]] = x = 1;
    x0 = -1;
    for (i = 2; i <= n; i++) {
        if (v[pozs[i]] != y) {
            x++;
        }
        if (v[pozs[i]] == 0) {
            x0 = x;//un 0 normalizat
        }
        y = v[pozs[i]];
        v[pozs[i]] = x;
    }
    for (i = 0; i <= n; i++) {
        pozs[i] = 0;
    }
    for (i = 1; i <= n; i++) {
        if (v[i] != x0 && pozs[v[i]] == 0) {
            pozs[v[i]] = i;
        } else {
            poz = pozs[v[i]] + 1;
            if (i < rmq[0][poz]) {
                rmq[0][poz] = i;
            }
            pozs[v[i]] = i;
        }
    }
    for (i = n - 1; i > 0; i--) {
        if (rmq[0][i + 1] < rmq[0][i]) {
            rmq[0][i] = rmq[0][i + 1];
        }
    }
    rmq[0][n + 1] = rmq[0][n + 2] = rmq[0][n + 3] = rmq[0][n + 4] = rmq[0][n + 5] = n + 1;//santinele
    //in pozdr[i] este pozitia minima a unui capat dr, pentr un st >= i
    j = p = 1;
    while (p <= n) {
        if (j % 4 == 0) {
            for (i = 1; i <= n + 2; i++) {
                rmq[j / 4][i] = rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][i] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1];
            }
        }
        j++;
        p *= 2;
    }
    q = readInt();
    p2 = 0;
    while ((1 << p2) <= n) {
        p2++;
    }
    p2--;
    for (i = 0; i < q; i++) {
        st = readInt();
        dr = readInt();
        rez = 0;
        for (p = p2; p >= 0; p--) {
            if (calcPoz(p, st) <= dr) {
                rez += (1 << p);
                st = calcPoz(p, st) + 1;
            }
        }
        printf("%d\n", rez);
    }
    return 0;
}

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