oj.uz

답안 #886081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886081 2023-12-11T12:43:35 Z CDuong Sum Zero (RMI20_sumzero) C++17
100 / 100
 497 ms 19908 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")


#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 4e5;
const int mod = 1e9 + 7;
const int LOG = 3;
const int base = 74;
const i64 oo = 1e18;

int aval, pw[LOG];
int nxt[LOG][mxN + 2];
map<i64, int>::iterator it;

void solve() {
    int n;
    cin >> n;

    pw[0] = 1;
    for (int i = 1; i < LOG; ++i)
        pw[i] = pw[i - 1] * base;

    fill(nxt[0], nxt[0] + mxN + 2, n + 1);
    map<i64, int> mp; mp[0] = 0;
    i64 cur_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> aval;
        cur_sum += aval;
        it = mp.find(cur_sum);
        if (it != mp.end()) nxt[0][it->ss] = i + 1;
        mp[cur_sum] = i + 1;
    }

    for (int i = n; i >= 0; --i) {
        nxt[0][i] = min(nxt[0][i], nxt[0][i + 1]);
    }

    for (int i = 1; i < LOG; ++i) {
        fill(nxt[i], nxt[i] + mxN + 2, n + 1);
        for (int j = 0; j < mxN + 2; ++j) {
            int cur = j;
            for (int _ = 0; _ < base; ++_)
                cur = nxt[i - 1][cur];
            nxt[i][j] = cur;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;

        int res = 0;
        for (int i = LOG - 1; i >= 0; --i) {
            while (nxt[i][l] <= r) {
                res += pw[i];
                l = nxt[i][l];
            }
        }
        cout << res << '\n';
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5200 KB Output is correct
2 Correct 75 ms 5284 KB Output is correct
3 Correct 78 ms 5336 KB Output is correct
4 Correct 75 ms 5260 KB Output is correct
5 Correct 74 ms 5252 KB Output is correct
6 Correct 77 ms 5184 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5200 KB Output is correct
2 Correct 75 ms 5284 KB Output is correct
3 Correct 78 ms 5336 KB Output is correct
4 Correct 75 ms 5260 KB Output is correct
5 Correct 74 ms 5252 KB Output is correct
6 Correct 77 ms 5184 KB Output is correct
7 Correct 142 ms 8016 KB Output is correct
8 Correct 125 ms 8528 KB Output is correct
9 Correct 155 ms 6232 KB Output is correct
10 Correct 147 ms 8032 KB Output is correct
11 Correct 122 ms 7764 KB Output is correct
12 Correct 151 ms 6060 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5200 KB Output is correct
2 Correct 75 ms 5284 KB Output is correct
3 Correct 78 ms 5336 KB Output is correct
4 Correct 75 ms 5260 KB Output is correct
5 Correct 74 ms 5252 KB Output is correct
6 Correct 77 ms 5184 KB Output is correct
7 Correct 142 ms 8016 KB Output is correct
8 Correct 125 ms 8528 KB Output is correct
9 Correct 155 ms 6232 KB Output is correct
10 Correct 147 ms 8032 KB Output is correct
11 Correct 122 ms 7764 KB Output is correct
12 Correct 151 ms 6060 KB Output is correct
13 Correct 434 ms 17240 KB Output is correct
14 Correct 347 ms 19164 KB Output is correct
15 Correct 497 ms 12096 KB Output is correct
16 Correct 462 ms 19608 KB Output is correct
17 Correct 341 ms 19908 KB Output is correct
18 Correct 479 ms 15020 KB Output is correct