oj.uz

Submission #1058014

# Submission time Handle Problem Language Result Execution time Memory
1058014 2024-08-14T07:59:49 Z vjudge1 Fish 2 (JOI22_fish2) C++17
31 / 100
 543 ms 17224 KB 

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+69;
const ll offset=2e5;
const ll inf=1e9+3;
const int base=350;
const ll mod=998244353;
int n,a[maxn],q;

struct fentree
{
    int st[maxn];
    void Update(int u,int v)
    {
        u+=1;
        for(;u<=n+3;u+=u&-u) st[u]+=v;
    }
    int Get1(int u)
    {
        u+=1;
        int r=0;
        for(;u>0;u-=u&-u) r+=st[u];
        return r;
    }
    int Get(int l,int r) {return Get1(r)-Get1(l-1);}
}tree2;
struct segtree1
{
    int mx[maxn*4];
    void Update(int u,int v,int id=1,int l=0,int r=n+1)
    {
//        cerr<<u<<' ' << id<<' '<<l<<' '<<r<<'\n';
        if (l==r)
        {
            mx[id]=v;
            return;
        }
        int mid=l+r>>1;
        if (u<=mid) Update(u,v,id*2,l,mid);
        else Update(u,v,id*2+1,mid+1,r);
        mx[id]=max(mx[id*2],mx[id*2+1]);
    }
    int Lwalk(int u,int val,int id=1,int l=0,int r=n+1)
    {
        if (l==r)
        {
            if (mx[id]<=val) return-1;
            return l;
        }
        int mid=l+r>>1;
        if (u<=mid) return Lwalk(u,val,id*2,l,mid);
        int c=-1;
        if (mx[id*2+1]>val) c=Lwalk(u,val,id*2+1,mid+1,r);
        if (c!=-1) return c;
        if (mx[id*2] > val) return Lwalk(u,val,id*2,l,mid);
        else return -1;
    }
    int Rwalk(int u,int val,int id=1,int l=0,int r=n+1)
    {
//        if (u==5 && val==3) cerr<< id<<' '<<l<<' '<<r<<'\n';
        if (l==r)
        {
            if (mx[id]<=val) return-1;
            return l;
        }
        int mid=l+r>>1;
        if (u>mid) return Rwalk(u,val,id*2+1,mid+1,r);
        int c=-1;
//        if (u==5 && val==3) cerr<<id<<' '<<mx[id*2]<<' '<<l<<' '<<mid<< " oday\n";
        if (mx[id*2] > val) c=Rwalk(u,val,id*2,l,mid);
        if (c!=-1) return c;
        if (mx[id*2+1] > val) return Rwalk(u,val,id*2+1,mid+1,r);
        else return -1;
    }
}tree1;

struct segtree2
{
    int mn[maxn*4],st[maxn*4],lazy[maxn*4];
    void push(int id)
    {
        int& x= lazy[id];
        mn[id<<1]+=x;
        lazy[id<<1]+=x;
        mn[id<<1|1]+=x;
        lazy[id<<1|1]+=x;
        x=0;
    }
    pii Merge(pii l,pii r)
    {
        if (l.fi==r.fi) return {l.fi,l.se+r.se};
        if (l.fi<r.fi) return {l.fi,l.se};
        return {r.fi,r.se};
    }
    void Build(int id=1,int l=1,int r=n)
    {
        if (l==r)
        {
            mn[id]=0;
            st[id]=1;
            return;
        }
        int mid=l+r>>1;
        Build(id*2,l,mid);
        Build(id*2+1,mid+1,r);
        pii x=Merge({mn[id*2],st[id*2]},{mn[id*2+1],st[id*2+1]});
        mn[id]=x.fi,st[id]=x.se;
    }
    void Update(int u,int v,int val,int id=1,int l=1,int r=n)
    {
        if (u>r || v<l) return;
        if (u<=l && r<=v)
        {
            mn[id]+=val;
            lazy[id]+=val;
            return;
        }
        if (lazy[id]!=0) push(id);
        int mid=l+r>>1;
        Update(u,v,val,id<<1,l,mid);
        Update(u,v,val,id<<1|1,mid+1,r);
        pii x=Merge({mn[id*2],st[id*2]},{mn[id*2+1],st[id*2+1]});
        mn[id]=x.fi,st[id]=x.se;
    }
    pii Get(int u,int v,int id=1,int l=1,int r=n)
    {
        if (u>r || v<l) return {inf,0};
        if (u<=l && r<=v) return {mn[id],st[id]};
        if (lazy[id]!=0) push(id);
        int mid=l+r>>1;
        return Merge(Get(u,v,id<<1,l,mid),Get(u,v,id<<1|1,mid+1,r));
    }
}tree3;
vector<int> L,R;
void Lget(int u)
{
    L.clear();
    L.pb(u-1);
    if (u==1) return;
    int id=u-2;
    while (id!=-1)
    {
        int sum=tree2.Get(id+1,u-1);
        if (a[id]>sum) L.pb(id);
        sum+=a[id];
        id=tree1.Lwalk(id-1,sum);
    }
}
void Rget(int u)
{
    R.clear();
    R.pb(u+1);
    if (u==n) return;
    int id=u+2;
    while (id!=-1)
    {
        int sum=tree2.Get(u+1,id-1);
        if (a[id]>sum) R.pb(id);
        sum+=a[id];
        id=tree1.Rwalk(id+1,sum);
    }
}
void Add(int i,int val)
{
    Rget(i);
    Lget(i);
    for(int j:R)
    {
        if (j==i+1) continue;
        if (a[i]>tree2.Get(i+1,j-1))
        {
            tree3.Update(i+1,j-1,val);
        }
    }
    for(int j:L)
    {
        if (j==i-1) continue;
        if (a[i]>tree2.Get(j+1,i-1))
        {
            tree3.Update(j+1,i-1,val);
        }
    }
    int kk=0,k,sum;
    for(int j:R)
    {
        k=L[kk];
        sum=tree2.Get(k+1,j-1);
        while (kk<L.size()-1 && sum>=a[k])
        {
            kk++;
            k=L[kk];
            sum=tree2.Get(k+1,j-1);
        }
        if (sum<a[j])
        {
            tree3.Update(k+1,j-1,val);
        }
    }
    int j=R.back();
    while (kk<L.size()-1)
    {
        kk++;
        k=L[kk];
        sum=tree2.Get(k+1,j-1);
        if (sum<a[j] && sum<a[k])
        {
            tree3.Update(k+1,j-1,val);
        }
    }
}
void sol()
{
    cin >> n;
    for1(i,1,n) cin  >> a[i];
    a[0]=a[n+1]=inf;
    for1(i,0,n+1)
    {
        tree1.Update(i,a[i]);
        tree2.Update(i,a[i]);
    }
    tree3.Build();
    for1(i,0,n-1)
    {
        Rget(i);
        for(int j:R)
        {
            if (j==i+1) continue;
            if (a[i]>tree2.Get(i+1,j-1))
            {
                tree3.Update(i+1,j-1,1);
            }
        }
    }
    cin >> q;
    for1(_,1,q)
    {
        int t,l,r;cin >>t>>l>>r;
        if (t==1)
        {
            Add(l,-1);
            tree1.Update(l,r);
            tree2.Update(l,-a[l]+r);
            a[l]=r;
            Add(l,1);
        }
        else
        {
            Rget(l-1);
            Lget(r+1);
            int i=upper_bound(all(R),r)-R.begin()-1;
            i=R[i];
            int j=upper_bound(all(L),l,greater<int>())-L.begin()-1;
            j=L[j];
            cout << tree3.Get(i,j).se<<'\n';

        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("fish2.inp","r",stdin);
//    freopen("fish2.out","w",stdout);

    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
4 12
1 2 3
1 3
2 3
2 1
1 2
1 2
1 4
1 1
1 1
2 4
2 3
1 1
3 4



*/

Compilation message

fish2.cpp: In member function 'void segtree1::Update(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'long long int segtree1::Lwalk(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:66:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'long long int segtree1::Rwalk(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'void segtree2::Build(long long int, long long int, long long int)':
fish2.cpp:119:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'void segtree2::Update(long long int, long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:135:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'pii segtree2::Get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:146:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In function 'void Add(long long int, long long int)':
fish2.cpp:204:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         while (kk<L.size()-1 && sum>=a[k])
      |                ~~^~~~~~~~~~~
fish2.cpp:216:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     while (kk<L.size()-1)
      |            ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4560 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Incorrect 3 ms 4564 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 121 ms 14872 KB Output is correct
3 Correct 134 ms 14604 KB Output is correct
4 Correct 93 ms 14940 KB Output is correct
5 Correct 101 ms 14752 KB Output is correct
6 Correct 25 ms 15144 KB Output is correct
7 Correct 52 ms 14460 KB Output is correct
8 Correct 25 ms 15188 KB Output is correct
9 Correct 58 ms 14488 KB Output is correct
10 Correct 68 ms 14948 KB Output is correct
11 Correct 82 ms 14656 KB Output is correct
12 Correct 31 ms 14528 KB Output is correct
13 Correct 35 ms 14680 KB Output is correct
14 Correct 35 ms 14932 KB Output is correct
15 Correct 37 ms 14968 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4560 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Incorrect 3 ms 4564 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 121 ms 14872 KB Output is correct
3 Correct 134 ms 14604 KB Output is correct
4 Correct 93 ms 14940 KB Output is correct
5 Correct 101 ms 14752 KB Output is correct
6 Correct 25 ms 15144 KB Output is correct
7 Correct 52 ms 14460 KB Output is correct
8 Correct 25 ms 15188 KB Output is correct
9 Correct 58 ms 14488 KB Output is correct
10 Correct 68 ms 14948 KB Output is correct
11 Correct 82 ms 14656 KB Output is correct
12 Correct 31 ms 14528 KB Output is correct
13 Correct 35 ms 14680 KB Output is correct
14 Correct 35 ms 14932 KB Output is correct
15 Correct 37 ms 14968 KB Output is correct
16 Correct 0 ms 4444 KB Output is correct
17 Correct 269 ms 16312 KB Output is correct
18 Correct 270 ms 16780 KB Output is correct
19 Correct 308 ms 16352 KB Output is correct
20 Correct 273 ms 16368 KB Output is correct
21 Correct 257 ms 16264 KB Output is correct
22 Correct 247 ms 16748 KB Output is correct
23 Correct 245 ms 16204 KB Output is correct
24 Correct 317 ms 16280 KB Output is correct
25 Correct 265 ms 16220 KB Output is correct
26 Correct 305 ms 16212 KB Output is correct
27 Correct 110 ms 16996 KB Output is correct
28 Correct 102 ms 17224 KB Output is correct
29 Correct 99 ms 16868 KB Output is correct
30 Correct 210 ms 16212 KB Output is correct
31 Correct 276 ms 16048 KB Output is correct
32 Correct 388 ms 16200 KB Output is correct
33 Correct 178 ms 16592 KB Output is correct
34 Correct 294 ms 16208 KB Output is correct
35 Correct 208 ms 16252 KB Output is correct
36 Correct 249 ms 16788 KB Output is correct
37 Correct 102 ms 16208 KB Output is correct
38 Correct 98 ms 16180 KB Output is correct
39 Correct 120 ms 16724 KB Output is correct
40 Correct 113 ms 16720 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 121 ms 14872 KB Output is correct
3 Correct 134 ms 14604 KB Output is correct
4 Correct 93 ms 14940 KB Output is correct
5 Correct 101 ms 14752 KB Output is correct
6 Correct 25 ms 15144 KB Output is correct
7 Correct 52 ms 14460 KB Output is correct
8 Correct 25 ms 15188 KB Output is correct
9 Correct 58 ms 14488 KB Output is correct
10 Correct 68 ms 14948 KB Output is correct
11 Correct 82 ms 14656 KB Output is correct
12 Correct 31 ms 14528 KB Output is correct
13 Correct 35 ms 14680 KB Output is correct
14 Correct 35 ms 14932 KB Output is correct
15 Correct 37 ms 14968 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Incorrect 543 ms 15948 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4560 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Incorrect 3 ms 4564 KB Output isn't correct
6 Halted 0 ms 0 KB -