oj.uz

Submission #968656

# Submission time Handle Problem Language Result Execution time Memory
968656 2024-04-23T19:50:37 Z ainta Mizuyokan 2 (JOI23_mizuyokan2) C++17
100 / 100
 2802 ms 55660 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, Nxt[N_][20], w[N_], INF = 1e9;
ll IT[SZ+SZ];
struct Node{
    int b, e;
    vc<pii>D;
}T[SZ+SZ];
void UDT(int a, int b){
    w[a]=b;
}
pii D[N_];
int Right[N_];
ll U[110];
int Deq[110]; 
ll S[N_];
void calc(int b, int e){
    S[b-1]=0;
    rng(i,b,e)S[i]=S[i-1]+w[i];
    ll Mn = 1e18;
    int pv = e;
    int head=1,tail=0;
    Right[e]=e+1;
    gnr(i,e-1,b){
        Right[i]=Right[i+1];
        if(Mn > S[i]+w[i]){
            Mn = S[i]+w[i];
        }
        while(S[pv-1] > Mn)pv--;
        rng(j,pv,Right[i]-1){
            if(S[j-1]> S[i]+w[i] && S[j-1]-S[i]>w[j]){
                Right[i]=j;
                break;
            }
        }
    }
}
void CalcNode(int nd, int b, int e){
    T[nd].b=b,T[nd].e=e;
    calc(b,e);
    if(T[nd].D.empty()){
        T[nd].D.resize(min(e-b+1,45));
    }
    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};
    }
    rep(i,si(T[nd].D))T[nd].D[i]=D[i+b];
}
pii DD[N_];
Node Merge(Node c1, Node c2){
    int b = c1.b, e = c2.e, m = c1.e;
    assert(c2.b == m+1);

    int bb = m;

    for(auto &t: c1.D){
        bb=min(bb,t.se);
    }

    calc(bb,min(m+45,e));

    int Mx = c2.D[0].fi, ee = c2.D[0].se;
    rep(i,si(c2.D)){
        DD[m+1+i] = c2.D[i];
    }
    gnr(t,m,max(m-44,b)){
        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(45,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;
        assert(x > m-49);
        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;
        
        ll sss=0;
        calc(max(e-50,1),e);
        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(sss > w[bb])c++;
            sss += w[b+j];
            ll ss = S[e]-S[ee];
            assert(ee>e-50);
            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

mizuyokan2.cpp: In function 'void calc(int, int)':
mizuyokan2.cpp:95:9: warning: unused variable 'head' [-Wunused-variable]
   95 |     int head=1,tail=0;
      |         ^~~~
mizuyokan2.cpp:95:16: warning: unused variable 'tail' [-Wunused-variable]
   95 |     int head=1,tail=0;
      |                ^~~~
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:198:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
mizuyokan2.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         scanf("%d%d%d%d",&x,&y,&b,&e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Correct 7 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 7 ms 26972 KB Output is correct
5 Correct 7 ms 26972 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 7 ms 26968 KB Output is correct
8 Correct 6 ms 26968 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 8 ms 27336 KB Output is correct
11 Correct 6 ms 27224 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 6 ms 26972 KB Output is correct
14 Correct 6 ms 27112 KB Output is correct
15 Correct 6 ms 26972 KB Output is correct
16 Correct 6 ms 26972 KB Output is correct
17 Correct 6 ms 27152 KB Output is correct
18 Correct 6 ms 26972 KB Output is correct
19 Correct 6 ms 26972 KB Output is correct
20 Correct 7 ms 26972 KB Output is correct
21 Correct 6 ms 26972 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Correct 7 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 7 ms 26972 KB Output is correct
5 Correct 7 ms 26972 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 7 ms 26968 KB Output is correct
8 Correct 6 ms 26968 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 8 ms 27336 KB Output is correct
11 Correct 6 ms 27224 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 6 ms 26972 KB Output is correct
14 Correct 6 ms 27112 KB Output is correct
15 Correct 6 ms 26972 KB Output is correct
16 Correct 6 ms 26972 KB Output is correct
17 Correct 6 ms 27152 KB Output is correct
18 Correct 6 ms 26972 KB Output is correct
19 Correct 6 ms 26972 KB Output is correct
20 Correct 7 ms 26972 KB Output is correct
21 Correct 6 ms 26972 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 6 ms 27224 KB Output is correct
24 Correct 7 ms 27228 KB Output is correct
25 Correct 6 ms 27224 KB Output is correct
26 Correct 7 ms 27336 KB Output is correct
27 Correct 6 ms 27228 KB Output is correct
28 Correct 6 ms 27312 KB Output is correct
29 Correct 8 ms 27224 KB Output is correct
30 Correct 7 ms 27224 KB Output is correct
31 Correct 6 ms 27228 KB Output is correct
32 Correct 6 ms 27228 KB Output is correct
33 Correct 6 ms 27228 KB Output is correct
34 Correct 6 ms 27112 KB Output is correct
35 Correct 6 ms 27124 KB Output is correct
36 Correct 7 ms 27228 KB Output is correct
37 Correct 7 ms 27228 KB Output is correct
38 Correct 6 ms 27228 KB Output is correct
39 Correct 7 ms 27228 KB Output is correct
40 Correct 6 ms 27224 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Correct 7 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 7 ms 26972 KB Output is correct
5 Correct 7 ms 26972 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 7 ms 26968 KB Output is correct
8 Correct 6 ms 26968 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 8 ms 27336 KB Output is correct
11 Correct 6 ms 27224 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 6 ms 26972 KB Output is correct
14 Correct 6 ms 27112 KB Output is correct
15 Correct 6 ms 26972 KB Output is correct
16 Correct 6 ms 26972 KB Output is correct
17 Correct 6 ms 27152 KB Output is correct
18 Correct 6 ms 26972 KB Output is correct
19 Correct 6 ms 26972 KB Output is correct
20 Correct 7 ms 26972 KB Output is correct
21 Correct 6 ms 26972 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 6 ms 27224 KB Output is correct
24 Correct 7 ms 27228 KB Output is correct
25 Correct 6 ms 27224 KB Output is correct
26 Correct 7 ms 27336 KB Output is correct
27 Correct 6 ms 27228 KB Output is correct
28 Correct 6 ms 27312 KB Output is correct
29 Correct 8 ms 27224 KB Output is correct
30 Correct 7 ms 27224 KB Output is correct
31 Correct 6 ms 27228 KB Output is correct
32 Correct 6 ms 27228 KB Output is correct
33 Correct 6 ms 27228 KB Output is correct
34 Correct 6 ms 27112 KB Output is correct
35 Correct 6 ms 27124 KB Output is correct
36 Correct 7 ms 27228 KB Output is correct
37 Correct 7 ms 27228 KB Output is correct
38 Correct 6 ms 27228 KB Output is correct
39 Correct 7 ms 27228 KB Output is correct
40 Correct 6 ms 27224 KB Output is correct
41 Correct 67 ms 50000 KB Output is correct
42 Correct 69 ms 53612 KB Output is correct
43 Correct 69 ms 53328 KB Output is correct
44 Correct 54 ms 45392 KB Output is correct
45 Correct 76 ms 53704 KB Output is correct
46 Correct 80 ms 52820 KB Output is correct
47 Correct 61 ms 46420 KB Output is correct
48 Correct 79 ms 53184 KB Output is correct
49 Correct 79 ms 52992 KB Output is correct
50 Correct 76 ms 52780 KB Output is correct
51 Correct 76 ms 52900 KB Output is correct
52 Correct 58 ms 47188 KB Output is correct
53 Correct 76 ms 53844 KB Output is correct
54 Correct 82 ms 53112 KB Output is correct
55 Correct 65 ms 52816 KB Output is correct
56 Correct 76 ms 52860 KB Output is correct
57 Correct 69 ms 52792 KB Output is correct
58 Correct 76 ms 52816 KB Output is correct
59 Correct 72 ms 53844 KB Output is correct
60 Correct 69 ms 53844 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26972 KB Output is correct
2 Correct 691 ms 48204 KB Output is correct
3 Correct 826 ms 55240 KB Output is correct
4 Correct 911 ms 55336 KB Output is correct
5 Correct 995 ms 55336 KB Output is correct
6 Correct 2799 ms 54716 KB Output is correct
7 Correct 2273 ms 54792 KB Output is correct
8 Correct 2300 ms 54544 KB Output is correct
9 Correct 2124 ms 54216 KB Output is correct
10 Correct 1173 ms 49264 KB Output is correct
11 Correct 1442 ms 55552 KB Output is correct
12 Correct 1397 ms 54492 KB Output is correct
13 Correct 1110 ms 54416 KB Output is correct
14 Correct 1446 ms 54408 KB Output is correct
15 Correct 1268 ms 54792 KB Output is correct
16 Correct 1473 ms 54300 KB Output is correct
17 Correct 775 ms 55344 KB Output is correct
18 Correct 912 ms 55572 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26972 KB Output is correct
2 Correct 6 ms 26972 KB Output is correct
3 Correct 675 ms 52432 KB Output is correct
4 Correct 824 ms 54200 KB Output is correct
5 Correct 691 ms 53848 KB Output is correct
6 Correct 1994 ms 53972 KB Output is correct
7 Correct 1804 ms 54008 KB Output is correct
8 Correct 1739 ms 54120 KB Output is correct
9 Correct 1732 ms 54080 KB Output is correct
10 Correct 1363 ms 54620 KB Output is correct
11 Correct 1366 ms 53780 KB Output is correct
12 Correct 1145 ms 53928 KB Output is correct
13 Correct 1536 ms 53840 KB Output is correct
14 Correct 1324 ms 53860 KB Output is correct
15 Correct 1495 ms 53840 KB Output is correct
16 Correct 762 ms 54348 KB Output is correct
17 Correct 1022 ms 54504 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26972 KB Output is correct
2 Correct 7 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 7 ms 26972 KB Output is correct
5 Correct 7 ms 26972 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 7 ms 26968 KB Output is correct
8 Correct 6 ms 26968 KB Output is correct
9 Correct 6 ms 26972 KB Output is correct
10 Correct 8 ms 27336 KB Output is correct
11 Correct 6 ms 27224 KB Output is correct
12 Correct 6 ms 26972 KB Output is correct
13 Correct 6 ms 26972 KB Output is correct
14 Correct 6 ms 27112 KB Output is correct
15 Correct 6 ms 26972 KB Output is correct
16 Correct 6 ms 26972 KB Output is correct
17 Correct 6 ms 27152 KB Output is correct
18 Correct 6 ms 26972 KB Output is correct
19 Correct 6 ms 26972 KB Output is correct
20 Correct 7 ms 26972 KB Output is correct
21 Correct 6 ms 26972 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 6 ms 27224 KB Output is correct
24 Correct 7 ms 27228 KB Output is correct
25 Correct 6 ms 27224 KB Output is correct
26 Correct 7 ms 27336 KB Output is correct
27 Correct 6 ms 27228 KB Output is correct
28 Correct 6 ms 27312 KB Output is correct
29 Correct 8 ms 27224 KB Output is correct
30 Correct 7 ms 27224 KB Output is correct
31 Correct 6 ms 27228 KB Output is correct
32 Correct 6 ms 27228 KB Output is correct
33 Correct 6 ms 27228 KB Output is correct
34 Correct 6 ms 27112 KB Output is correct
35 Correct 6 ms 27124 KB Output is correct
36 Correct 7 ms 27228 KB Output is correct
37 Correct 7 ms 27228 KB Output is correct
38 Correct 6 ms 27228 KB Output is correct
39 Correct 7 ms 27228 KB Output is correct
40 Correct 6 ms 27224 KB Output is correct
41 Correct 67 ms 50000 KB Output is correct
42 Correct 69 ms 53612 KB Output is correct
43 Correct 69 ms 53328 KB Output is correct
44 Correct 54 ms 45392 KB Output is correct
45 Correct 76 ms 53704 KB Output is correct
46 Correct 80 ms 52820 KB Output is correct
47 Correct 61 ms 46420 KB Output is correct
48 Correct 79 ms 53184 KB Output is correct
49 Correct 79 ms 52992 KB Output is correct
50 Correct 76 ms 52780 KB Output is correct
51 Correct 76 ms 52900 KB Output is correct
52 Correct 58 ms 47188 KB Output is correct
53 Correct 76 ms 53844 KB Output is correct
54 Correct 82 ms 53112 KB Output is correct
55 Correct 65 ms 52816 KB Output is correct
56 Correct 76 ms 52860 KB Output is correct
57 Correct 69 ms 52792 KB Output is correct
58 Correct 76 ms 52816 KB Output is correct
59 Correct 72 ms 53844 KB Output is correct
60 Correct 69 ms 53844 KB Output is correct
61 Correct 6 ms 26972 KB Output is correct
62 Correct 691 ms 48204 KB Output is correct
63 Correct 826 ms 55240 KB Output is correct
64 Correct 911 ms 55336 KB Output is correct
65 Correct 995 ms 55336 KB Output is correct
66 Correct 2799 ms 54716 KB Output is correct
67 Correct 2273 ms 54792 KB Output is correct
68 Correct 2300 ms 54544 KB Output is correct
69 Correct 2124 ms 54216 KB Output is correct
70 Correct 1173 ms 49264 KB Output is correct
71 Correct 1442 ms 55552 KB Output is correct
72 Correct 1397 ms 54492 KB Output is correct
73 Correct 1110 ms 54416 KB Output is correct
74 Correct 1446 ms 54408 KB Output is correct
75 Correct 1268 ms 54792 KB Output is correct
76 Correct 1473 ms 54300 KB Output is correct
77 Correct 775 ms 55344 KB Output is correct
78 Correct 912 ms 55572 KB Output is correct
79 Correct 7 ms 26972 KB Output is correct
80 Correct 6 ms 26972 KB Output is correct
81 Correct 675 ms 52432 KB Output is correct
82 Correct 824 ms 54200 KB Output is correct
83 Correct 691 ms 53848 KB Output is correct
84 Correct 1994 ms 53972 KB Output is correct
85 Correct 1804 ms 54008 KB Output is correct
86 Correct 1739 ms 54120 KB Output is correct
87 Correct 1732 ms 54080 KB Output is correct
88 Correct 1363 ms 54620 KB Output is correct
89 Correct 1366 ms 53780 KB Output is correct
90 Correct 1145 ms 53928 KB Output is correct
91 Correct 1536 ms 53840 KB Output is correct
92 Correct 1324 ms 53860 KB Output is correct
93 Correct 1495 ms 53840 KB Output is correct
94 Correct 762 ms 54348 KB Output is correct
95 Correct 1022 ms 54504 KB Output is correct
96 Correct 551 ms 47952 KB Output is correct
97 Correct 963 ms 54992 KB Output is correct
98 Correct 679 ms 55124 KB Output is correct
99 Correct 2802 ms 54516 KB Output is correct
100 Correct 2240 ms 54840 KB Output is correct
101 Correct 2236 ms 54364 KB Output is correct
102 Correct 2151 ms 54316 KB Output is correct
103 Correct 1359 ms 55660 KB Output is correct
104 Correct 1355 ms 54476 KB Output is correct
105 Correct 1130 ms 54296 KB Output is correct
106 Correct 1458 ms 54156 KB Output is correct
107 Correct 1278 ms 54532 KB Output is correct
108 Correct 1492 ms 54356 KB Output is correct
109 Correct 766 ms 55380 KB Output is correct
110 Correct 949 ms 55456 KB Output is correct