Submission #1105920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105920		horiaboeriu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	325 ms	26492 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
#define MAXN 400000
#define MAXL 20
int rmq[MAXL / 4][MAXN + 6];
unordered_map<long long, int> fr;
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;
    long long sum;
    //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++) {
        rmq[0][i] = n + 1;
    }
    sum = 0;
    for (i = 1; i <= n; i++) {
        sum += readInt();
        if (sum != 0 && fr[sum] == 0) {
            fr[sum] = i;//prima data cand apare
        } else {
            poz = fr[sum] + 1;
            if (i < rmq[0][poz]) {
                rmq[0][poz] = i;
            }
            fr[sum] = 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: 0 / 39