Submission #1081258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081258		HienTD	Fish 3 (JOI24_fish3)	C++14	0 / 100	146 ms	37716 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define                  fi  first
#define                  se  second
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define              ALL(v)  (v).begin(), (v).end()
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  (((x) >> (i)) & 1)
#define           REP(i, v) for( __typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define           F0R(i, n)  for(int i = 0, _n = (n); i < _n; ++ i)
#define          F0RD(i, n)  for(int i = (n); i > 0; -- i)
#define        FOR(i, a, b)  for(int i = (a), _b = (b); i < _b; ++ i)
#define       FORD(i, b, a) for(int i = (b), _a = (a); i > _a; -- i)
#define       FORE(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++ i)
#define      FORDE(i, b, a)  for(int i = (b), _a = (a); i >= _a; -- i)
#define  __builtin_popcount  __builtin_popcountll

#define mxN 300010
#define LOG 19

const string NAME = "BAITAP";

int N, Q;
long long D;
long long max_A = 0;
vector<int> A(mxN);

namespace subtask_2{
    vector<vector<int>> RMQ(mxN, vector<int> (LOG + 1));
    bool check(){
        FORE(i, 1, N) if(A[i] > 1) return false;
        return true;
    }

    void build(){
        FORE(i, 1, N) RMQ[i][0] = A[i];
        FORE(j, 1, LOG) FORE(i, 1, N - MASK(j) + 1) RMQ[i][j] = min(RMQ[i][j - 1], RMQ[i + MASK(j - 1)][j - 1]);
    }

    int get(int l, int r){
        int k = 31 - __builtin_clz(r - l + 1);
        return min(RMQ[l][k], RMQ[r - MASK(k) + 1][k]);
    }

    void solve(){
        build();
        cin >> Q;
        FORE(i, 1, Q){
            int l, r;
            cin >> l >> r;
            int res = get(l, r);
            if(res == 1) cout << 0 << '\n';
            else{
                bool chk = false;
                bool ans = true;
                FORE(j, l, r){
                    if(A[j] == 1) chk = true;
                    else if(A[j] == 0 && chk == true){
                        ans = false;
                        break;
                    }
                }
                cout << (ans == true ? 0 : -1) << '\n';
            }
        }
    }
};

void init(void){
    cin >> N >> D;
    FORE(i, 1, N) cin >> A[i];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    #ifdef LOCAL
        freopen((NAME + ".INP").c_str(), "r", stdin);
        freopen((NAME + ".OUT").c_str(), "w", stdout);
    #endif // LOCAL

    init();
    if(subtask_2::check()) subtask_2::solve();
    else cout << 1;

    cerr << "\nTime elapsed AC: " << TIME << "s.\n";

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36