oj.uz

Submission #967167

# Submission time Handle Problem Language Result Execution time Memory
967167 2024-04-21T11:38:11 Z ainta Mizuyokan 2 (JOI23_mizuyokan2) C++17
0 / 100
 4000 ms 34224 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;
int w[N_];
ll S[N_];
vc<t3> IT[SZ+SZ];
ll BIT[SZ];
void Add(int a, ll b){
    while(a<SZ){
        BIT[a]+=b;
        a+=(a&-a);
    }
}
ll Sum(int a){
    ll r=0;
    while(a){
        r += BIT[a];
        a-=(a&-a);
    }
    return r;
}
vc<t3> Merge(vc<t3> A, vc<t3> B){
    if(A.empty())return B;
    if(B.empty())return A;
    vc<t3>T;
    for(auto &[c1,b1,e1]: A){
        for(auto &[c2,b2,e2]: B){
            ll bet = Sum(b2-1)-Sum(e1);
            if(w[e1] < bet && bet > w[b2]){
                T.pb({c1+c2,b1,e2});
            }
        }
    }
    for(auto &t: A)T.pb(t);
    for(auto &t: B)T.pb(t);
    sort(all(T), [&](t3 a, t3 b){
        auto [c1,b1,e1]=a;
        auto [c2,b2,e2]=b;
        if(c1!=c2)return c1<c2;
        return e1-b1 > e2-b2;
    });
    reverse(all(T));
    vc<t3>ret;
    rep(i,si(T)){
        int ck=0;
        auto [c,b,e]=T[i];
        rep(j,i){
            auto [c2,b2,e2]=T[j];
            if(c+2<c2){
                ck=1;
                break;
            }
            if(b2>=b && e2<=e){
                if(b2-b >30 || ((ll)w[b] << (b2-b)) >= w[b2]){
                    if(e-e2 > 30 || ((ll)w[e] << (e-e2)) >= w[e2] ){
                        ck=1;
                        break;
                    }
                }
            }
        }
        if(!ck)ret.pb(T[i]);
    }
    return ret;
}
vc<t3> Leaf(int a){
    return {{1,a,a}};
}
void Get(int l, int r){
    vi T1, T2;
    int b=l+SZ,e=r+SZ;
    while(b<=e){
        if(b&1)T1.pb(b);
        if(!(e&1))T2.pb(e);
        b=(b+1)>>1,e=(e-1)>>1;
    }
    reverse(all(T2));
    for(auto &t:T2)T1.pb(t);
    auto ret = IT[T1[0]];
    rng(i,1,si(T1)-1){
        ret = Merge(ret, IT[T1[i]]);
    }
    ll SB = Sum(l-1);
    ll SE = Sum(r);
    int Mx=0;
    for(auto &[c1,b1,e1]: ret){
        int c=c1*2-1;
        if(Sum(b1-1)-SB > w[b1]) c++;
        if(SE-Sum(e1) > w[e1]) c++;
        Mx=max(Mx,c);
    }
    printf("%d\n",Mx);
}
void UDT(int i){
    int a = SZ+i;
    IT[a] = Leaf(i);
    while(a!=1){
        a>>=1;
        IT[a] = Merge(IT[a*2],IT[a*2+1]);
    }
}
void Solve(){
    scanf("%d",&n);
    rng(i,1,n){
        scanf("%d",&w[i]);
        Add(i,w[i]);
    }
    rng(i,1,n){
        UDT(i);
    }
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int x, y, b, e;
        scanf("%d%d%d%d",&x,&y,&b,&e);
        Add(x,y-w[x]);
        w[x]=y;
        UDT(x);
        b++;
        Get(b,e);
    }
}
int main(){
    int TC=1;
    while(TC--){
        Solve();
    }
}

Compilation message

mizuyokan2.cpp: In function 'void Solve()':
mizuyokan2.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:185:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Execution timed out 4038 ms 18836 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Execution timed out 4038 ms 18836 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Execution timed out 4038 ms 18836 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Execution timed out 4058 ms 33644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Execution timed out 4032 ms 34224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Execution timed out 4038 ms 18836 KB Time limit exceeded
8 Halted 0 ms 0 KB -