oj.uz

Submission #1017418

# Submission time Handle Problem Language Result Execution time Memory
1017418 2024-07-09T07:50:42 Z modwwe Fish 2 (JOI22_fish2) C++17
43 / 100
 716 ms 408148 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<"cuuuuuuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
int sa,sb;
main()
{
#ifndef ONLINE_JUDGE
   //    fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
struct IT
{
    int sl,sr;/// size left
    /// size right
    ic cr[32];
    ic cl[32];
    int c,d;
    int a;
} t[400001],ans;
int a[100001];
vector<id> v;
bool cmp(id a,id b)
{
    return a.a<b.a;
}
IT mer(int y,int z,int mid,int l,int r)
{
    IT tx;
    v.clear();
    for(int i=0; i<=t[z].sl; i++)
        v.pb({a[t[z].cl[i].b]-t[z].cl[i].a,t[z].cl[i].a,t[z].cl[i].b,i});
    sort(v.begin(),v.end(),cmp);
    s4=-1 ;
    mx=t[y].sr+1;
    s5=-1;
    s6=-1;
    for(auto x:v )
    {
        while(mx>0&&t[y].cr[mx-1].a<x.a)s5=max(s5,a[t[y].cr[mx-1].b]-t[y].cr[mx-1].a),mx--;
        if(s5>x.b)
        {
            s4=max(s4,x.c);
            if(s4==x.c)
                s6=x.d;
        }
    }
    tx.d=t[z].d;
    s9=t[z].d;
    if(s4!=-1) tx.d+=s4-mid-t[z].cl[s6].c-1,s9+=s4-mid-t[z].cl[s6].c-1;
    s10=s4;
    v.clear() ;
    for(int i=0; i<=t[y].sr; i++)
        v.pb({a[t[y].cr[i].b]-t[y].cr[i].a,t[y].cr[i].a,t[y].cr[i].b,i});
    sort(v.begin(),v.end(),cmp);
    s4=n+1;
    mx=-1;
    s5=-1;
    s6=0;
    for(auto x:v)
    {
        while(mx<t[z].sl&&t[z].cl[mx+1].a<x.a)
            mx++,s5=max(s5,a[t[z].cl[mx].b]-t[z].cl[mx].a);
        if(s5>x.b)
        {
            s4=min(s4,x.c);
            if(s4==x.c) s6=x.d;
        }
    }
    s8=t[y].d;
    tx.d+=t[y].d;
    if(s4!=n+1)tx.d+=mid-s4-t[y].cr[s6].c,s8+=mid-s4-t[y].cr[s6].c;
    bool dl=0;
    bool dr=0;
    dem=-1;
    for(int i=0; i<=t[y].sl; i++)
        tx.cl[++dem]=t[y].cl[i];
    sa=-1;
    for(int i=0; i<=t[z].sl; i++)
        if(t[z].cl[i].a+t[y].a<a[t[z].cl[i].b])
        {
            tx.cl[++dem]=t[z].cl[i],
                         dl=1;
            if(s10!=-1)
            {
                if(t[z].cl[i].b<s10)
                {
                    tx.cl[dem].c=t[z].cl[i].b-mid;
                }
                else tx.cl[dem].c+=s9-t[z].d;
            }
            tx.cl[dem].c+=s8;
            tx.cl[dem].a+=t[y].a;
        }
    sa=dem;
//if(l==1&&r==3)cout<<t[y].d,down
    tx.sl=dem;
    dem=-1;
    sb=n+1;
    for(int i=0; i<=t[y].sr; i++)
        if(t[y].cr[i].a+t[z].a<a[t[y].cr[i].b])
        {
            tx.cr[++dem]=t[y].cr[i],
                         tx.cr[dem].a+=t[z].a,
                                       dr=1;
            if(s4!=n+1)
            {
                if(s4<t[y].cr[i].b)tx.cr[dem].c=mid-t[y].cr[i].b+1;
                else tx.cr[dem].c+=s8-t[y].d;
            }
            tx.cr[dem].c+=s9;
        }
    for(int i=0; i<=t[z].sr; i++)
        tx.cr[++dem]=t[z].cr[i];
    sb=0;
    tx.c=s9-tx.cl[sa].c+tx.cl[sa].b-l;
    tx.c+=s8-tx.cr[sb].c+r-tx.cr[sb].b;
    tx.a=t[y].a+t[z].a;
    tx.sr=dem;
    return tx;
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        t[node].cr[0]=t[node].cl[0]= {0,l};
        t[node].a=a[l];
        return;
    }
    int mid=l+r>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    t[node]=mer(node<<1,node<<1|1,mid,l,r);
}
void upd(int node,int l,int r,int l1)
 {
 if(l==r){ t[node].cr[0]=t[node].cl[0]= {0,l};
        t[node].a=a[l];
        return;}
        int mid=l+r>>1;
         if(l1<=mid) upd(node<<1,l,mid,l1);
         else upd(node<<1|1,mid+1,r,l1);
             t[node]=mer(node<<1,node<<1|1,mid,l,r);

 }
/*void get(int node,int l,int r, int l1,int r1)
{  if(l>r1||r<l1) return ;
    if(l>=l1&&r<=r1)
    { if(t[0].sl==-1&&t[0].sr==-1) ans=t[node];
    else ans=(0,node);
        return;
    }
    int mid=l+r>>1;
    get(node<<1,l,mid,l1,r1);
    get(node<<1|1,mid+1,r,l1,r1);
}*/
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    build(1,1,n);
        cin>>m;
        for(int i=1; i<=m; i++)
        {
            cin>>l;
            if(l==1)
            {
                cin>>l>>r;
                a[l]=r;
                upd(1,1,n,l);
            }
            else
            {  cin>>l>>r;
             if(l==1&&r==n)
                 cout<<n-t[1].c;
                 else
                 {
                    assert(0);
                 }
                 down
            }
        }

}

Compilation message

fish2.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
fish2.cpp: In function 'IT mer(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:120:10: warning: variable 'dl' set but not used [-Wunused-but-set-variable]
  120 |     bool dl=0;
      |          ^~
fish2.cpp:121:10: warning: variable 'dr' set but not used [-Wunused-but-set-variable]
  121 |     bool dr=0;
      |          ^~
fish2.cpp: In function 'void build(long long int, long long int, long long int)':
fish2.cpp:177:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  177 |     int mid=l+r>>1;
      |             ~^~
fish2.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
fish2.cpp:187:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 154 ms 405852 KB Output is correct
3 Correct 161 ms 405756 KB Output is correct
4 Correct 158 ms 405840 KB Output is correct
5 Correct 154 ms 405840 KB Output is correct
6 Correct 165 ms 406356 KB Output is correct
7 Correct 167 ms 405492 KB Output is correct
8 Correct 158 ms 406352 KB Output is correct
9 Correct 155 ms 405680 KB Output is correct
10 Correct 158 ms 405840 KB Output is correct
11 Correct 155 ms 405588 KB Output is correct
12 Correct 176 ms 405584 KB Output is correct
13 Correct 165 ms 405840 KB Output is correct
14 Correct 155 ms 406100 KB Output is correct
15 Correct 161 ms 406096 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 154 ms 405852 KB Output is correct
3 Correct 161 ms 405756 KB Output is correct
4 Correct 158 ms 405840 KB Output is correct
5 Correct 154 ms 405840 KB Output is correct
6 Correct 165 ms 406356 KB Output is correct
7 Correct 167 ms 405492 KB Output is correct
8 Correct 158 ms 406352 KB Output is correct
9 Correct 155 ms 405680 KB Output is correct
10 Correct 158 ms 405840 KB Output is correct
11 Correct 155 ms 405588 KB Output is correct
12 Correct 176 ms 405584 KB Output is correct
13 Correct 165 ms 405840 KB Output is correct
14 Correct 155 ms 406100 KB Output is correct
15 Correct 161 ms 406096 KB Output is correct
16 Runtime error 11 ms 4584 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 154 ms 405852 KB Output is correct
3 Correct 161 ms 405756 KB Output is correct
4 Correct 158 ms 405840 KB Output is correct
5 Correct 154 ms 405840 KB Output is correct
6 Correct 165 ms 406356 KB Output is correct
7 Correct 167 ms 405492 KB Output is correct
8 Correct 158 ms 406352 KB Output is correct
9 Correct 155 ms 405680 KB Output is correct
10 Correct 158 ms 405840 KB Output is correct
11 Correct 155 ms 405588 KB Output is correct
12 Correct 176 ms 405584 KB Output is correct
13 Correct 165 ms 405840 KB Output is correct
14 Correct 155 ms 406100 KB Output is correct
15 Correct 161 ms 406096 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 714 ms 406940 KB Output is correct
18 Correct 611 ms 407520 KB Output is correct
19 Correct 542 ms 406868 KB Output is correct
20 Correct 484 ms 407380 KB Output is correct
21 Correct 679 ms 407124 KB Output is correct
22 Correct 638 ms 407380 KB Output is correct
23 Correct 716 ms 406932 KB Output is correct
24 Correct 651 ms 407320 KB Output is correct
25 Correct 654 ms 406868 KB Output is correct
26 Correct 421 ms 408148 KB Output is correct
27 Correct 521 ms 408100 KB Output is correct
28 Correct 491 ms 407400 KB Output is correct
29 Correct 457 ms 408004 KB Output is correct
30 Correct 532 ms 408140 KB Output is correct
31 Correct 544 ms 407324 KB Output is correct
32 Correct 661 ms 407376 KB Output is correct
33 Correct 706 ms 406980 KB Output is correct
34 Correct 619 ms 407680 KB Output is correct
35 Correct 627 ms 407376 KB Output is correct
36 Correct 544 ms 407376 KB Output is correct
37 Correct 524 ms 407084 KB Output is correct
38 Correct 381 ms 407124 KB Output is correct
39 Correct 439 ms 407744 KB Output is correct
40 Correct 281 ms 407652 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -