oj.uz

답안 #968594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968594 2024-04-23T16:49:08 Z ainta Mizuyokan 2 (JOI23_mizuyokan2) C++17
32 / 100
 300 ms 27076 KB 
#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;
    }
    gnr(i,n-1,1)Nxt[i][0]=min(Nxt[i][0],Nxt[i+1][0]);
    rep(t,17){
        rng(i,1,n){
            Nxt[i][t+1]=n+1;
            int x = Nxt[i][t];
            if(x<=n)Nxt[i][t+1]=Nxt[x][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;
        ll Mn = 1e18;
        rng(i,b,min(b+30,e)){
            int t=i;
            int c=1;
            per(j,18){
                if(Nxt[t][j]<=e){
                    c+=(1<<j);
                    t=Nxt[t][j];
                }
            }
            c=c*2-1;
            if(S[i-1]-S[b-1] > w[i])c++;

            rng(j,t,e){
                if(S[e]-S[j] > w[j]){
                    c++;
                    break;
                }
            }


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

Compilation message

mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:112:12: warning: unused variable 'Mn' [-Wunused-variable]
  112 |         ll Mn = 1e18;
      |            ^~
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:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 95 ms 19088 KB Output is correct
3 Correct 159 ms 26528 KB Output is correct
4 Correct 185 ms 26452 KB Output is correct
5 Correct 153 ms 26704 KB Output is correct
6 Correct 130 ms 25940 KB Output is correct
7 Correct 156 ms 26116 KB Output is correct
8 Correct 138 ms 25940 KB Output is correct
9 Correct 139 ms 25828 KB Output is correct
10 Correct 181 ms 22308 KB Output is correct
11 Correct 245 ms 27076 KB Output is correct
12 Correct 300 ms 25732 KB Output is correct
13 Correct 240 ms 25664 KB Output is correct
14 Correct 213 ms 25736 KB Output is correct
15 Correct 272 ms 25708 KB Output is correct
16 Correct 221 ms 25620 KB Output is correct
17 Correct 110 ms 26712 KB Output is correct
18 Correct 191 ms 26964 KB Output is correct

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -