Submission #968578

#TimeUsernameProblemLanguageResultExecution timeMemory
968578aintaMizuyokan 2 (JOI23_mizuyokan2)C++17
0 / 100
102 ms33568 KiB
#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][2], 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][0]=r; while(r<n && w[r]>=w[r+1]*2)r++; Nxt[i][0][1]=r; } rep(t,18){ rng(i,1,n){ int x = Nxt[i][t][1]; if(x<=n){ Nxt[i][t+1][0] = Nxt[x][t][0]; Nxt[i][t+1][1] = Nxt[x][t][1]; } else Nxt[i][t+1][0]=Nxt[i][t+1][1]=n+1; } } 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; rng(i,b,e){ if(i>b+1 && w[i]*2>w[i-1])break; int t=i; int c=1; per(j,18){ if(Nxt[t][j][1]<=e){ c+=(1<<j); t=Nxt[t][j][1]; } } if(Nxt[t][0][0]<=e)c++, t=Nxt[t][0][0]; 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: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:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...