oj.uz

Submission #857066

# Submission time Handle Problem Language Result Execution time Memory
857066 2023-10-05T10:47:59 Z chanhchuong123 Sum Zero (RMI20_sumzero) C++14
100 / 100
 907 ms 16212 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""

const int MAX = 400002;
const int base = 128;
int n, q;
int pw[2];
int c[MAX];
int sf = 0;
int jump[2][MAX];
map<int, int> last;


int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	cin >> n;
	for (int i = 1; i <= n; ++i) {
        cin >> c[i];
	}
	for (int i = 1; i <= n + 1; ++i) {
        jump[0][i] = n + 2;
        jump[1][i] = n + 2;
	}
	last[0] = n + 1;
	for (int i = n; i >= 1; --i) {
        sf += c[i];
        jump[0][i] = min(jump[0][i], jump[0][i + 1]);
        if (last[sf] > 0) jump[0][i] = min(jump[0][i], last[sf]); last[sf] = i;
	}
	pw[0] = 1; pw[1] = base;
	for (int j = 1; j <= 1; ++j) {
        for (int i = 1; i <= n + 1; ++i) {
            jump[j][i] = i;
            for (int k = 1; k <= base; ++k) {
                jump[j][i] = jump[j - 1][jump[j][i]];
                if (jump[j][i] == n + 2) break;
            }
        }
	}
    cin >> q;
    while (q--) {
        int l, r, res = 0; cin >> l >> r;
        for (int j = 1; j >= 0; --j) {
            while (jump[j][l] - 1 <= r) {
                l = jump[j][l];
                res += pw[j];
            }
        }
        cout << res << '\n';
    }
	return 0;
}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:35:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   35 |         if (last[sf] > 0) jump[0][i] = min(jump[0][i], last[sf]); last[sf] = i;
      |         ^~
sumzero.cpp:35:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   35 |         if (last[sf] > 0) jump[0][i] = min(jump[0][i], last[sf]); last[sf] = i;
      |                                                                   ^~~~
sumzero.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 101 ms 7016 KB Output is correct
8 Correct 76 ms 7248 KB Output is correct
9 Correct 96 ms 5460 KB Output is correct
10 Correct 92 ms 7060 KB Output is correct
11 Correct 72 ms 6736 KB Output is correct
12 Correct 101 ms 5544 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 101 ms 7016 KB Output is correct
8 Correct 76 ms 7248 KB Output is correct
9 Correct 96 ms 5460 KB Output is correct
10 Correct 92 ms 7060 KB Output is correct
11 Correct 72 ms 6736 KB Output is correct
12 Correct 101 ms 5544 KB Output is correct
13 Correct 907 ms 14676 KB Output is correct
14 Correct 390 ms 16212 KB Output is correct
15 Correct 832 ms 8288 KB Output is correct
16 Correct 799 ms 16200 KB Output is correct
17 Correct 345 ms 13908 KB Output is correct
18 Correct 832 ms 14928 KB Output is correct