Submission #1338194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338194		po_rag526	Sum Zero (RMI20_sumzero)	C++20	100 / 100	224 ms	13444 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define cd const double
#define cld const long double
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define psf push_front
#define ppf pop_front
#define ps push
#define pp pop
#define all(x) x.begin(), x.end()
#define popcount __builtin_popcountll
#define ctz __builtin_ctzll
#define clz __builtin_clzll
using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;

ci N = 4e5+1;
int v[N], a[N], b[N], c[N], res[N], l[N], r[N];
int n, q, k;

void transform(){
    for (int i=0; i<n; i++){
        c[i] = b[i];
    }
    for (int i=0; i<n; i++){
        int nxt = c[i];
        if (c[i] != inf) b[i] = c[c[i]];
        else b[i] = inf;
    }
}

void solve(){
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> v[i];
        v[i] += v[i-1];
    }
    n++;

    cin >> q;
    for (int i=0; i<q; i++) cin >> l[i] >> r[i];

    for (int i=0; i<n; i++){
        a[i] = v[i];
    }
    sort(a, a+n);
    k = unique(a, a+n) - a;
    for (int i=0; i<n; i++){
        v[i] = lower_bound(a, a+k, v[i]) - a;
        // cout << v[i] << " ";
    }
    // cout << "\n";

    fill(b, b+k, -1);
    fill(a, a+n, inf);
    for (int i=0; i<n; i++){
        if (b[v[i]] != -1){
            a[b[v[i]]] = i;
        }
        b[v[i]] = i;
    }
    for (int i=n-2; i>=0; i--) a[i] = min(a[i], a[i+1]);
    // for (int i=0; i<n; i++) cout << a[i] << " ";
    // cout << "\n\n";

    fill(res, res+q, 0);
    int LOG = 64 - clz(n);
    for (int i = LOG-1; i >= 0; i--){
        for (int j=0; j<n; j++) b[j] = a[j];
        for (int j=0; j<i; j++){
            transform();
        }

        for (int j=0; j<q; j++){
            // cout << l[j] << " " << r[j] << "\n";
            if (b[l[j]-1] <= r[j]){
                // cout << "query " << j << " passes on run " << i << "\n";
                l[j] = b[l[j]-1]+1;
                res[j] += (1 << i); 
            }
        }
        
        // for (int j=0; j<n; j++){
        //     cout << b[j] << " ";
        // }
        // cout << "\n";
    }
    for (int i=0; i<q; i++) cout << res[i] << "\n";
}

string file_name = "";
string input_extension = "";
string output_extension = "";

int main(){
    if (file_name.size() > 0 && input_extension.size() > 0){
        freopen((file_name+input_extension).c_str(), "r", stdin);
    }
    if (file_name.size() > 0 && output_extension.size() > 0){
        freopen((file_name+output_extension).c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    auto start = chrono::high_resolution_clock::now();

    int t=1;
    // cin >> t;
    while (t--) solve();

    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);

    cerr << "\n\nRuntime: " << duration.count() / 1000.0 << " ms\n";
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen((file_name+input_extension).c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen((file_name+output_extension).c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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