oj.uz

Submission #967326

# Submission time Handle Problem Language Result Execution time Memory
967326 2024-04-21T21:59:08 Z ainta Mizuyokan 2 (JOI23_mizuyokan2) C++17
6 / 100
 4000 ms 34052 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_];
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,si(ret)){
            auto [c2,b2,e2]=ret[j];
            if(c+2<c2){
                ck=1;
                break;
            }
            if(c+1<c2 && j>10){
                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]);
    }
    //printf("! %d\n",si(ret));
    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:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
mizuyokan2.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14436 KB Output is correct
3 Correct 7 ms 14696 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 9 ms 14684 KB Output is correct
6 Correct 8 ms 14680 KB Output is correct
7 Correct 367 ms 15684 KB Output is correct
8 Correct 161 ms 15052 KB Output is correct
9 Correct 65 ms 14956 KB Output is correct
10 Correct 275 ms 17432 KB Output is correct
11 Correct 113 ms 15464 KB Output is correct
12 Correct 89 ms 15188 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 10 ms 14684 KB Output is correct
15 Correct 10 ms 14480 KB Output is correct
16 Correct 12 ms 14684 KB Output is correct
17 Correct 14 ms 14684 KB Output is correct
18 Correct 12 ms 14716 KB Output is correct
19 Correct 13 ms 14680 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
21 Correct 12 ms 14684 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14436 KB Output is correct
3 Correct 7 ms 14696 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 9 ms 14684 KB Output is correct
6 Correct 8 ms 14680 KB Output is correct
7 Correct 367 ms 15684 KB Output is correct
8 Correct 161 ms 15052 KB Output is correct
9 Correct 65 ms 14956 KB Output is correct
10 Correct 275 ms 17432 KB Output is correct
11 Correct 113 ms 15464 KB Output is correct
12 Correct 89 ms 15188 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 10 ms 14684 KB Output is correct
15 Correct 10 ms 14480 KB Output is correct
16 Correct 12 ms 14684 KB Output is correct
17 Correct 14 ms 14684 KB Output is correct
18 Correct 12 ms 14716 KB Output is correct
19 Correct 13 ms 14680 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
21 Correct 12 ms 14684 KB Output is correct
22 Correct 28 ms 14684 KB Output is correct
23 Correct 33 ms 14684 KB Output is correct
24 Correct 42 ms 14804 KB Output is correct
25 Correct 49 ms 14740 KB Output is correct
26 Execution timed out 4037 ms 17828 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14436 KB Output is correct
3 Correct 7 ms 14696 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 9 ms 14684 KB Output is correct
6 Correct 8 ms 14680 KB Output is correct
7 Correct 367 ms 15684 KB Output is correct
8 Correct 161 ms 15052 KB Output is correct
9 Correct 65 ms 14956 KB Output is correct
10 Correct 275 ms 17432 KB Output is correct
11 Correct 113 ms 15464 KB Output is correct
12 Correct 89 ms 15188 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 10 ms 14684 KB Output is correct
15 Correct 10 ms 14480 KB Output is correct
16 Correct 12 ms 14684 KB Output is correct
17 Correct 14 ms 14684 KB Output is correct
18 Correct 12 ms 14716 KB Output is correct
19 Correct 13 ms 14680 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
21 Correct 12 ms 14684 KB Output is correct
22 Correct 28 ms 14684 KB Output is correct
23 Correct 33 ms 14684 KB Output is correct
24 Correct 42 ms 14804 KB Output is correct
25 Correct 49 ms 14740 KB Output is correct
26 Execution timed out 4037 ms 17828 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Execution timed out 4046 ms 33540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Execution timed out 4035 ms 34052 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14436 KB Output is correct
3 Correct 7 ms 14696 KB Output is correct
4 Correct 8 ms 14684 KB Output is correct
5 Correct 9 ms 14684 KB Output is correct
6 Correct 8 ms 14680 KB Output is correct
7 Correct 367 ms 15684 KB Output is correct
8 Correct 161 ms 15052 KB Output is correct
9 Correct 65 ms 14956 KB Output is correct
10 Correct 275 ms 17432 KB Output is correct
11 Correct 113 ms 15464 KB Output is correct
12 Correct 89 ms 15188 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 10 ms 14684 KB Output is correct
15 Correct 10 ms 14480 KB Output is correct
16 Correct 12 ms 14684 KB Output is correct
17 Correct 14 ms 14684 KB Output is correct
18 Correct 12 ms 14716 KB Output is correct
19 Correct 13 ms 14680 KB Output is correct
20 Correct 11 ms 14684 KB Output is correct
21 Correct 12 ms 14684 KB Output is correct
22 Correct 28 ms 14684 KB Output is correct
23 Correct 33 ms 14684 KB Output is correct
24 Correct 42 ms 14804 KB Output is correct
25 Correct 49 ms 14740 KB Output is correct
26 Execution timed out 4037 ms 17828 KB Time limit exceeded
27 Halted 0 ms 0 KB -