oj.uz

답안 #961618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961618 2024-04-12T09:01:28 Z vjudge1 Sum Zero (RMI20_sumzero) C++17
61 / 100
 214 ms 23332 KB 
// author : HuuHung
// 25.3.2024


#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()

using namespace std;

void maxzi(auto &a, auto b){
    a = max(a, b);
}

void minzi(auto &a, auto b){
    a = min(a, b);
}

const int N = 4e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void add(auto &a, auto b){
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

auto Pow(auto a, auto b){
    if (b == 0) return 1;
    if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
    auto c = Pow(a, b / 2);
    return 1ll * c * c % mod;
}

// * end

int jump[N], p[N], level[N];
unordered_map<ll, int> f;
void solve(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    ll tot = 0;
    int mx = -1;
    level[0] = 1;
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        tot += a;
        if(f[tot] || !tot) mx = max(mx, f[tot]);
        f[tot] = i;
        p[i] = mx;
        if(mx == -1) level[i] = 1;
        else
        level[i] = level[p[i]] + 1;
        if(mx >= 0 && level[p[i]] - level[jump[p[i]]] ==  level[jump[p[i]]] - level[jump[jump[p[i]]]]) jump[i] = jump[jump[p[i]]];
        else jump[i] = p[i];
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0; --l;
        while(r) {
            if(p[r] < l) break;
            if(jump[r] >= l) ans += level[r] - level[jump[r]], r = jump[r];
            else ans++, r = p[r];
        }
        cout << ans << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

Compilation message

sumzero.cpp:20:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maxzi(auto &a, auto b){
      |            ^~~~
sumzero.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maxzi(auto &a, auto b){
      |                     ^~~~
sumzero.cpp:24:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void minzi(auto &a, auto b){
      |            ^~~~
sumzero.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void minzi(auto &a, auto b){
      |                     ^~~~
sumzero.cpp:32:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   32 | void add(auto &a, auto b){
      |          ^~~~
sumzero.cpp:32:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   32 | void add(auto &a, auto b){
      |                   ^~~~
sumzero.cpp:38:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | auto Pow(auto a, auto b){
      |          ^~~~
sumzero.cpp:38:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | auto Pow(auto a, auto b){
      |                  ^~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2676 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2676 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 45 ms 6716 KB Output is correct
8 Correct 46 ms 5572 KB Output is correct
9 Correct 44 ms 3988 KB Output is correct
10 Correct 41 ms 6580 KB Output is correct
11 Correct 38 ms 4780 KB Output is correct
12 Correct 44 ms 3920 KB Output is correct

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2676 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 45 ms 6716 KB Output is correct
8 Correct 46 ms 5572 KB Output is correct
9 Correct 44 ms 3988 KB Output is correct
10 Correct 41 ms 6580 KB Output is correct
11 Correct 38 ms 4780 KB Output is correct
12 Correct 44 ms 3920 KB Output is correct
13 Correct 214 ms 13676 KB Output is correct
14 Runtime error 183 ms 23332 KB Memory limit exceeded
15 Halted 0 ms 0 KB -