oj.uz

답안 #886184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886184 2023-12-11T14:25:21 Z nnhzzz Sum Zero (RMI20_sumzero) C++14
100 / 100
 163 ms 17532 KB 
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <locale>
#include <map>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<(i))
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define               _PB  push_back
#define                fi  first
#define                se  second
#define                ll  long long
#define                ld  long double
#define                vi  vector<int>
#define               vvi  vector<vi>
#define              vvvi  vector<vvi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define             vvpii  vector<vpii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
#define              endl  "\n"
#define                MP  make_pair
// #define               int  ll


//-----------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{ c = getchar(); }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const  ll   LINF = 1e18;
const int    INF = 1e9;
const int    LOG = 4;
const int   MAXN = 4e5+7;
const int      N = 1e2+3;
const int    MOD = 1e9+7;
const int   BASE = 5;
const  ld    EPS = 1e-9;
const  ld     PI = acos(-1);
const int OFFSET = 1e3;
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int a[MAXN];
int n,query;

// namespace sub1{
//     void solve(){
//         REP(t,1,query){
//             int l = q[t].fi,r = q[t].se;
//             set<int> s; s.insert(0);
//             int sum = 0,res = 0;
//             REP(i,l,r){
//                 sum += a[i];
//                 if(s.find(sum)!=s.end()){
//                     s.clear();
//                     s.insert(0);
//                     sum = 0;
//                     ++res;
//                 }else{
//                     s.insert(sum);
//                 }
//             }
//             cout << res << endl;
//         }
//     }
// }

// namespace sub2{
//     int f[MAXN][LOG];

//     void solve(){
//         map<int,int> mp;
//         int sum = 0;
//         REP(i,1,n) sum += a[i];
//         f[n+1][0] = n+1;
//         int MIN = n+1;
//         REPD(i,n,0){
//             if(mp.count(sum)) mini(MIN,mp[sum]);
//             f[i][0] = MIN;
//             mp[sum] = i;
//             sum -= a[i];
//         }
//         REP(j,1,LOG-1){
//             REP(i,0,n+1){
//                 f[i][j] = f[i][j-1];
//                 REP(k,1,MASK(BASE)-1){
//                     f[i][j] = f[f[i][j]][j-1];
//                 }
//             }
//         }
//         REP(t,1,query){
//             int l = q[t].fi-1,r = q[t].se,res = 0;
//             REPD(i,LOG-1,0){
//                 while(f[l][i]<=r){
//                     res += MASK(i*BASE);
//                     l = f[l][i];
//                 }
//             }
//             cout << res << endl;
//         }
//     }
// }

namespace sub3{
    int nxt[MAXN],jump[MAXN],lvl[MAXN];

    void solve(){
        unordered_map<ll,int> mp;
        ll sum = 0;
        REP(i,1,n) sum += a[i];
        jump[n+1] = nxt[n+1] = n+1;
        int MIN = n+1;
        REPD(i,n,0){
            if(mp.count(sum)) mini(MIN,mp[sum]);
            nxt[i] = MIN;
            mp[sum] = i;
            sum -= a[i];
        }
        mp.clear();
        lvl[n+1] = 0;
        REPD(i,n,0){
            int x = nxt[i];
            if(lvl[x]==lvl[jump[x]]){
                lvl[i] = lvl[x]+1;
                jump[i] = jump[jump[x]];
            }else{
                lvl[i] = 1;
                jump[i] = nxt[i];
            }
        }
        REP(t,1,query){
            int res = 0,l = readInt(),r = readInt(); --l;
            while(nxt[l]<=r){
                if(jump[l]<=r){
                    res += MASK(lvl[l])-1;
                    l = jump[l];
                }else{
                    ++res;
                    l = nxt[l];
                }
            }
            cout << res << endl;
        }
    }
}

void solve(){
    n = readInt();
    REP(i,1,n) a[i] = readInt();
    query = readInt();
    // REP(t,1,query) cin >> q[t].fi >> q[t].se;
    sub3::solve(); return ;
    // if(n<=5000 && query<=5000){
    //     sub1::solve();
    //     return ;
    // }
    // if(n<=100000 && query<=100000){
    //     sub2::solve();
    //     return ;
    // }
    sub3::solve();
}

__nnhzzz__{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "nnhzzz"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }

    int test = 1;

    while(test--){
      solve();
    }
    cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:233:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:237:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:238:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 32 ms 7128 KB Output is correct
8 Correct 26 ms 7532 KB Output is correct
9 Correct 36 ms 6144 KB Output is correct
10 Correct 31 ms 7096 KB Output is correct
11 Correct 26 ms 6836 KB Output is correct
12 Correct 37 ms 6224 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 32 ms 7128 KB Output is correct
8 Correct 26 ms 7532 KB Output is correct
9 Correct 36 ms 6144 KB Output is correct
10 Correct 31 ms 7096 KB Output is correct
11 Correct 26 ms 6836 KB Output is correct
12 Correct 37 ms 6224 KB Output is correct
13 Correct 156 ms 14940 KB Output is correct
14 Correct 128 ms 17276 KB Output is correct
15 Correct 163 ms 9500 KB Output is correct
16 Correct 152 ms 17532 KB Output is correct
17 Correct 128 ms 14276 KB Output is correct
18 Correct 160 ms 9296 KB Output is correct