Submission #891538

#	Time	Username	Problem	Language	Result	Execution time	Memory
891538		vjudge1	Sum Zero (RMI20_sumzero)	C++17	61 / 100	193 ms	23348 KiB

sumzero

/*----23-12-2023----*/
#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define BIT(x, i) (1 & ((x) >> (i)))
#define OFF(x, i) ((x) ^ (1 << (i)))
#define ON(x, i) ((x) | (1 << (i)))
#define MASK(x) (1 << (x))
#define CNT(x) __builtin_popcountll(x)
#define ALL(x) x.begin(), x.end()
// #define int long long
#define For(x, a, b)                       \
    for(int x = a; x <= b; x++)
#define Rep(x, a, b)                       \
    for(int x = a; x >= b; x--)
#define file(name)                         \
    if (fopen(name ".inp", "r"))           \
    {                                      \
        freopen(name ".inp", "r", stdin);  \
        freopen(name ".out", "w", stdout); \
    }
#define faster                             \
    ios_base::sync_with_stdio(0);          \
    cin.tie(0);                            \
    cout.tie(0);
using namespace std;

const int inf = 1e18;
const double pi = acos(-1);
const int N = 4e5 + 1;
int n, q, x, y, cur = -1, par[N], d[N], lf[N];
long long a;
unordered_map<long long, int> mp;
void solve() {
    cin >> x >> y;
    int ans = 0; x--;
    while (y && par[y] >= x)
        ans += (lf[y] >= x ? d[y] - d[lf[y]] : 1), y = (lf[y] >= x ? lf[y] : par[y]);
    cout << ans << '\n';
}

void code() {
    cin >> n; d[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> x; a += x;
        if (!a || mp[a]) cur = max(cur, mp[a]);
        mp[a] = i; par[i] = cur;
        d[i] = (~cur ? d[par[i]] + 1 : 1);
        lf[i] = (~cur && d[par[i]] - d[lf[par[i]]] == d[lf[par[i]]] - d[lf[lf[par[i]]]] ? lf[lf[par[i]]] : par[i]);
    }
    cin >> q;
    while (q--) solve();
}

main() {
    faster;
    file("_");
    int t = 1;
    // cin >> t;
    while (t--) code(), cout << '\n';
    ofstream time("_.time");
    time << TIME << 's';
    return 0;
}

Compilation message (stderr)

sumzero.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const int inf = 1e18;
      |                 ^~~~
sumzero.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main() {
      | ^~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen(name ".inp", "r", stdin);  \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:56:5: note: in expansion of macro 'file'
   56 |     file("_");
      |     ^~~~
sumzero.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(name ".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:56:5: note: in expansion of macro 'file'
   56 |     file("_");
      |     ^~~~

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