Submission #968587

#	Time	Username	Problem	Language	Result	Execution time	Memory
968587		ainta	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	207 ms	19196 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
 
ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}
 
 
template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;
using t4 = tuple<int,int,int,int>;
using t5 = tuple<int,int,int,int,int>;
template<> const Mint Mint::G = Mint(3);
#define N_ 251000
const int SZ = (1<<18);
int n, Nxt[N_][20], w[N_];
ll S[N_];
void Solve(){
    scanf("%d",&n);
    rng(i,1,n){
        scanf("%d",&w[i]);
        S[i]=S[i-1]+w[i];
    }
    rng(i,1,n){
        int b=i+2,e=n,r=n+1;
        while(b<=e){
            int mid = (b+e)/2;
            if(S[mid-1]-S[i]>w[i]){
                r=mid;
                e=mid-1;
            }
            else b=mid+1;
        }
        while(r<=n && S[r-1]-S[i]<=w[r])r++;
        Nxt[i][0]=r;
    }
    rep(t,18){
        rng(i,1,n){
            int x = Nxt[i][t];
            Nxt[i][t+1]=n+1;
            if(x<=n){
                rng(j,x,min(x+30,n)){
                    Nxt[i][t+1]=min(Nxt[i][t+1], Nxt[j][t]);
                }
            }
        }
    }
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int x,y,b,e;
        scanf("%d%d%d%d",&x,&y,&b,&e);
        b++;
        int ans=0;
        vi V;
        V.pb(b);
        ll Mn = 1e18;
        int pv=-1;
        rng(i,b+1,b+30){
            if(Mn >= S[i]+w[i]){
                Mn = S[i]+w[i];
                pv=i;
            }
        }
        if(pv!=-1)V.pb(pv);
        for(auto &i: V){
            //if(i>b+1 && w[i]*2>w[i-1])break;
            int t=i;
            int c=1;
            per(j,18){
                int nt = n+1;
                rng(k,t,(t+30,e)){
                    nt=min(nt, Nxt[k][j]);
                }
                if(nt<=e){
                    c+=(1<<j);
                    t=nt;
                }
            }
            c=c*2-1;
            if(S[i-1]-S[b-1] > w[i])c++;
            if(S[e]-S[t] > w[t])c++;


            ans=max(ans,c);
        }
        printf("%d\n",ans);
    }
}
int main(){
    int TC=1;
    while(TC--){
        Solve();
    }
}

Compilation message (stderr)

mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:132:27: warning: left operand of comma operator has no effect [-Wunused-value]
  132 |                 rng(k,t,(t+30,e)){
      |                          ~^~~
mizuyokan2.cpp:4:44: note: in definition of macro 'rng'
    4 | #define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
      |                                            ^
mizuyokan2.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11