oj.uz

Submission #967164

# Submission time Handle Problem Language Result Execution time Memory
967164 2024-04-21T11:34:45 Z ainta Mizuyokan 2 (JOI23_mizuyokan2) C++17
0 / 100
 2872 ms 42016 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+1<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 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16844 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 5 ms 16832 KB Output is correct
7 Correct 707 ms 17948 KB Output is correct
8 Correct 285 ms 17276 KB Output is correct
9 Correct 22 ms 17000 KB Output is correct
10 Correct 1842 ms 19376 KB Output is correct
11 Correct 195 ms 17192 KB Output is correct
12 Incorrect 43 ms 16988 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16844 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 5 ms 16832 KB Output is correct
7 Correct 707 ms 17948 KB Output is correct
8 Correct 285 ms 17276 KB Output is correct
9 Correct 22 ms 17000 KB Output is correct
10 Correct 1842 ms 19376 KB Output is correct
11 Correct 195 ms 17192 KB Output is correct
12 Incorrect 43 ms 16988 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16844 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 5 ms 16832 KB Output is correct
7 Correct 707 ms 17948 KB Output is correct
8 Correct 285 ms 17276 KB Output is correct
9 Correct 22 ms 17000 KB Output is correct
10 Correct 1842 ms 19376 KB Output is correct
11 Correct 195 ms 17192 KB Output is correct
12 Incorrect 43 ms 16988 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Incorrect 2515 ms 37836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Incorrect 2872 ms 42016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16844 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 5 ms 16832 KB Output is correct
7 Correct 707 ms 17948 KB Output is correct
8 Correct 285 ms 17276 KB Output is correct
9 Correct 22 ms 17000 KB Output is correct
10 Correct 1842 ms 19376 KB Output is correct
11 Correct 195 ms 17192 KB Output is correct
12 Incorrect 43 ms 16988 KB Output isn't correct
13 Halted 0 ms 0 KB -