Submission #1143019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143019		tnknguyen_	Fish 3 (JOI24_fish3)	C++20	0 / 100	1 ms	328 KiB

Main

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

#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define int long long 

#define pii pair<int, int>
#define fi first
#define se second
#define MASK(k) (1LL << (k))

int n, D, q;
const int MX = 3e5 + 5;
int C[MX], st[18][MX], ps[MX], f[MX], g[MX];
pii Q[MX];

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

namespace SUB1{
    bool ok(){ return max(n, q) <= 3000; }
    void solve(){
        for(int i=1; i<=q; ++i){
            int L, R; tie(L, R) = Q[i];
            int sum = 0, ans = 0, pre = 0, last = 0;
            for(int j=L; j<=R; ++j){
                int x = C[j] % D;
                if(x < pre) x += (((pre - x) / D) + 1) * D;
                if(C[j] < x){
                    ans = -1;
                    break;  
                }
                else ans += (C[j] - x);
                pre = x, last = (C[j] - x);
            }
            cout << (ans == -1 ? ans : (ans - last * (R - L + 1)) / D) << endl;
        }
        exit(0); ///////////
    }
}

namespace SUB3{
    bool ok(){ return (D == 1); }
    void solve(){
        for(int i=1; i<=n;){
            int cur = i;
            while(C[i] == C[cur]) f[i] = cur, ++i;
        }
        for(int i=1; i<=n; ++i) st[0][i] = C[i], ps[i] = ps[i-1] + C[i];
        for(int j=1; j<18; ++j){
            for(int i=1; i+MASK(j-1)<=n; ++i){
                st[j][i] = min(st[j-1][i], st[j-1][i + MASK(j-1)]);
            }
        }

        for(int i=1; i<=q; ++i){
            int L, R; tie(L, R) = Q[i];
            R = max(L, f[R] - 1);
            cout << (ps[R] - ps[L-1]) - get(L, R) * (R - L + 1) << endl;
        }

        exit(0); ///////
    }
}

namespace SUB2{
    bool ok(){
        for(int i=1; i<=n; ++i) if(C[i] > 1) return 0;
        return 1;
    }
    void solve(){
        for(int i=1; i<=n;){
            int cur = i;
            while(C[i] == C[cur]) f[i] = cur, ++i;
        }
        for(int i=1; i<=n; ++i) ps[i] = ps[i-1] + C[i];   

        for(int i=1; i<=q; ++i){
            int L, R; tie(L, R) = Q[i];
            int sum = ps[R] - ps[L - 1];
            if(C[R] == 0) cout << ((sum == 0 || D == 1) ? sum : -1) << endl;
            else{
                R = max(L, f[R] - 1);
                sum = ps[R] - ps[L-1];
                cout << ((sum == 0 || D == 1) ? sum : -1) << endl;
            }   
        }
        exit(0); /////////////
    }
}

namespace SUB4{
    bool ok(){
        for(int i=1; i<n; ++i) if(C[i] < C[i+1]) return 0;
        return 1;
    }
    void solve(){
        int sum = 0, ans = 0, pre = 0, last = 0;
        for(int j=1; j<=n; ++j){
            int x = C[j] % D; 
            if(x < pre) x += (((pre - x) / D) + 1) * D;
            f[j] = x;
            pre = x, last = (C[j] - x);
            ps[j] = ps[j-1] + C[j], g[j] = g[j-1] + f[j];
        }

        for(int i=1; i<=q; ++i){
            int L, R; tie(L, R) = Q[i];
            if(C[R] < f[R] - D*(f[L] / D)){
                cout << -1 << endl;
                continue;
            }
            int x = ps[R] - ps[L-1];    
            int y = g[R] - g[L-1] - (f[L] / D) * (R - L + 1);
            int z = (C[R] - (f[R] - f[L] / D)) * (R - L + 1);
            cout << (x - y - z) / D << endl;
        }

        exit(0); ////////////
    }
}    

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("main.inp","r",stdin);
    freopen("main.out","w",stdout);

    cin >> n >> D;
    for(int i=1; i<=n; ++i) cin >> C[i];
    cin >> q;
    for(int i=1; i<=q; ++i){
        int L, R; cin >> L >> R;
        Q[i] = {L, R};
    }

    if(SUB3::ok()) SUB3::solve();   
    if(SUB2::ok()) SUB2::solve();
    if(SUB1::ok()) SUB1::solve();
    SUB4::solve();


    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen("main.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:133:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     freopen("main.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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