Submission #968618

#TimeUsernameProblemLanguageResultExecution timeMemory
968618aintaMizuyokan 2 (JOI23_mizuyokan2)C++17
0 / 100
685 ms51932 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], w[N_], INF = 1e9; ll IT[SZ+SZ]; struct Node{ int b, e; vc<pii>D; }T[SZ+SZ]; int Right(int a){ int x = SZ+a+1; ll s=0; while(1){ if(x&1)s+=IT[x]; if(s>w[a])break; x=(x+1)>>1; } while(x<SZ){ x*=2; s-=IT[x+1]; if(s<=w[a]){ s+=IT[x+1]; x++; } } x-=SZ;x++; while(s <= w[x]){ s+=w[x];x++; } return x; } ll Sum(int b, int e){ ll s=0; b+=SZ,e+=SZ; while(b<=e){ if(b&1)s+=IT[b]; if(!(e&1))s+=IT[e]; b=(b+1)>>1,e=(e-1)>>1; } return s; } void Put(int a, ll x){ a+=SZ; IT[a]=x; while(a!=1){ a>>=1; IT[a]=IT[a*2]+IT[a*2+1]; } } void UDT(int a, int b){ w[a]=b; Put(a,b); } pii D[N_]; void CalcNode(int nd, int b, int e){ T[nd].b=b,T[nd].e=e; if(T[nd].D.empty()){ T[nd].D.resize(min(e-b+1,30)); } gnr(i,e,b){ D[i]={0,i}; if(i!=e && D[i+1].fi) D[i]=D[i+1]; int pv = Right(i); if(pv<=e && D[i].fi < D[pv].fi + 1 || (D[i].fi == D[pv].fi+1 && D[i].se > D[pv].se))D[i]={D[pv].fi+1, D[pv].se}; } rng(i,b,min(b+29,e))T[nd].D[i-b]=D[i]; } pii DD[N_]; Node Merge(Node c1, Node c2){ int b = c1.b, e = c2.e, m = c1.e; assert(c2.b == m+1); vi Z; for(auto &t: c1.D){ Z.pb(t.se); } sort(all(Z)); Z.resize(unique(all(Z))-Z.begin()); reverse(all(Z)); int Mx = c2.D[0].fi, ee = c2.D[0].se; rep(i,si(c2.D)){ DD[m+1+i] = c2.D[i]; } for(auto &t: Z){ int r = Right(t); if(r-m-1 < si(c2.D)){ int td = c2.D[r-m-1].fi + 1, te = c2.D[r-m-1].se; if(Mx<td || (Mx == td && ee > te))Mx=td,ee=te; } if(Mx==0 && ee > t)ee = t; DD[t]={Mx,ee}; } Mx = c2.D[0].fi, ee = c2.D[0].se; Node ret; ret.D.resize(min(30,e-b+1)); per(i,si(ret.D)){ if(i+b>m){ ret.D[i] = DD[i+b]; continue; } int x = c1.D[i].se; int td = DD[x].fi + c1.D[i].fi, te = DD[x].se; if(Mx < td || (Mx==td && ee>te))Mx=td,ee=te; ret.D[i] = {Mx,ee}; } ret.b=b,ret.e=e; return ret; } void init(int nd, int b, int e){ if(b!=e){ int m = (b+e)>>1; init(nd*2,b,m); init(nd*2+1,m+1,e); } else{ T[nd] = Merge(T[nd*2],T[nd*2+1]); } } vi Z; void Solve(){ scanf("%d",&n); rng(i,1,n){ scanf("%d",&w[i]); UDT(i,w[i]); } UDT(n+1,INF+2); UDT(n+2,INF+1); rng(i,1,n){ CalcNode(SZ+i,i,i); } gnr(i,SZ-1,1){ if(T[i*2].b && T[i*2+1].b){ int b=T[i*2].b, e = T[i*2+1].e; if(e-b<60) CalcNode(i,b,e); else T[i] = Merge(T[i*2],T[i*2+1]); } } int Q; scanf("%d",&Q); while(Q--){ int x, y, b, e; scanf("%d%d%d%d",&x,&y,&b,&e); UDT(x,y); int a = SZ+x; while(a!=1){ a>>=1; if(T[a].b && T[a].e){ if(T[a].e-T[a].b<60)CalcNode(a,T[a].b,T[a].e); else T[a] = Merge(T[a*2],T[a*2+1]); } } b++; int tb=b+SZ,te=e+SZ; vi T1, T2; while(tb<=te){ if(tb&1)T1.pb(tb); if(!(te&1))T2.pb(te); tb=(tb+1)>>1,te=(te-1)>>1; } reverse(all(T2)); for(auto &t:T2)T1.pb(t); Node tp = T[T1[0]]; rng(j,1,si(T1)-1)tp=Merge(tp,T[T1[j]]); int ans=0; rep(j,si(tp.D)){ int c = tp.D[j].fi, bb = tp.b+j, ee = tp.D[j].se; c=c*2+1; if(Sum(b,b+j-1) > w[bb])c++; ll ss = Sum(ee+1,e); rng(k,ee,e-1){ if(ss > w[k]){ c++; break; } ss-=w[k+1]; } ans=max(ans,c); } printf("%d\n",ans); } } int main(){ int TC=1; while(TC--){ Solve(); } }

Compilation message (stderr)

mizuyokan2.cpp: In function 'void CalcNode(int, int, int)':
mizuyokan2.cpp:136:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  136 |         if(pv<=e && D[i].fi < D[pv].fi + 1 || (D[i].fi == D[pv].fi+1 && D[i].se > D[pv].se))D[i]={D[pv].fi+1, D[pv].se};
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:194:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:210:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:213:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |         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...