oj.uz

Submission #541511

# Submission time Handle Problem Language Result Execution time Memory
541511 2022-03-23T17:14:33 Z cegax Sum Zero (RMI20_sumzero) C++17
100 / 100
 291 ms 20464 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(A) A.rbegin(),A.rend()
#define pb push_back 
#define dbg(x) do {cerr << #x <<" = " << (x) << endl; } while (false)
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
//cout << setprecision(12) << fixed;

const int maxn = 4e5+5;
const int LOGN = 19;

ll a[maxn];
int go[maxn];
ii queries[maxn];
int ans[maxn];
int jump[maxn];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin >> n;
    a[0] = 0;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i-1];
    }
    
    for ( int i=0; i<=n+1; i++ )
        go[i] = n+1;
 
    multiset<int> mst;
 
    mst.insert( 0 );
 
    for ( int l=0, r=0; l<=n; l++ )
    {
        /*cout << l << ": ";
        for ( auto& el : mst )
            cout << el << ' ';
        cout << '\n';*/
 
        while ( r <= n )
        {
            if ( mst.count( a[r] ) >= 2 )
                break;
 
            r++;
 
            if ( r <= n )
                mst.insert( a[r] );
        }
 
        /*cout << l << ' ' << r << ": ";
        for ( auto& el : mst )
            cout << el << ' ';
        cout << '\n';*/
 
        go[l+1] = r;
        mst.erase( mst.find( a[l] ) );
    }
    
    for(int i = 1; i <= n+1; i++)
        go[i]++;

    // for(int i = 1; i <= n; i++)
    //     cout << go[i][0] << " ";

    int q; cin >> q;

    for(int i = 0; i < q; i++) 
        cin >> queries[i].first >> queries[i].second;

    for(int j = LOGN-1; j >= 0; j--) {
        for(int i = 1; i <= n+1; i++)
            jump[i] = go[i];

        for(int k = 1; k <= j; k++) {
            for(int i = 1; i <= n+1; i++) {
                if(jump[i] <= n+1) jump[i] = jump[jump[i]];
                else jump[i] = n+2;
            }
        }

        for(int i = 0; i < q; i++) {
            int L = queries[i].first, R = queries[i].second;
            if(jump[L] <= R+1) {
                ans[i] |= (1 << j);
                queries[i].first = jump[L];
            }
        }
    }

    for(int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
	
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 500 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 59 ms 3512 KB Output is correct
8 Correct 60 ms 3460 KB Output is correct
9 Correct 77 ms 3492 KB Output is correct
10 Correct 62 ms 3524 KB Output is correct
11 Correct 60 ms 3484 KB Output is correct
12 Correct 65 ms 3472 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 500 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 59 ms 3512 KB Output is correct
8 Correct 60 ms 3460 KB Output is correct
9 Correct 77 ms 3492 KB Output is correct
10 Correct 62 ms 3524 KB Output is correct
11 Correct 60 ms 3484 KB Output is correct
12 Correct 65 ms 3472 KB Output is correct
13 Correct 253 ms 13280 KB Output is correct
14 Correct 265 ms 13020 KB Output is correct
15 Correct 291 ms 20428 KB Output is correct
16 Correct 269 ms 19468 KB Output is correct
17 Correct 264 ms 20348 KB Output is correct
18 Correct 279 ms 20464 KB Output is correct