Submission #1006673

#TimeUsernameProblemLanguageResultExecution timeMemory
1006673modwweFish 2 (JOI22_fish2)C++17
13 / 100
4086 ms10748 KiB
//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 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 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,c; }; 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; main() { #ifndef ONLINE_JUDGE // fin(task),fou(task); #endif NHP; /// cin>>s1; // modwwe phongbeo(); } ic t[400001]; int a[100001]; void build(int node,int l,int r) { if(l==r) {t[node].a=a[l],t[node].b=l;t[node].c=a[l];return;} int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); t[node]=t[node<<1|1]; if(t[node<<1].a>=t[node<<1|1].a) t[node]=t[node<<1]; t[node].c=t[node<<1].c+t[node<<1|1].c; } void upd(int node,int l,int r,int l1,int r1,int c) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) {t[node].a=c,t[node].c=c; return;} int mid=l+r>>1; upd(node<<1,l,mid,l1,r1,c); upd(node<<1|1,mid+1,r,l1,r1,c); t[node]=t[node<<1|1]; if(t[node<<1].a>=t[node<<1|1].a) t[node]=t[node<<1]; t[node].c=t[node<<1].c+t[node<<1|1].c; } ib get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return{0,0}; if(l>=l1&&r<=r1) return {t[node].a,t[node].b}; int mid=l+r>>1; ib ss3=get(node<<1,l,mid,l1,r1); ib ss4=get(node<<1|1,mid+1,r,l1,r1); if(ss3.a>=ss4.a) return ss3; else return ss4; } int get_c(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node].c; int mid=l+r>>1; return get_c(node<<1,l,mid,l1,r1)+get_c(node<<1|1,mid+1,r,l1,r1); } void calc(int l,int r) { s4++; if(l>=r) return ; ib sx=get(1,1,n,l,r); if(sx.b!=l) { s3=get_c(1,1,n,l,sx.b-1); if(s3>=sx.a) calc(l,sx.b-1); } if(sx.b!=r) { s3=get_c(1,1,n,sx.b+1,r); if(s3>=sx.a) calc(sx.b+1,r); } return; } 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; upd(1,1,n,l,l,r); } else { cin>>l>>r; s4=0; calc(l,r); cout<<s4,down } } }

Compilation message (stderr)

fish2.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main()
      | ^~~~
fish2.cpp: In function 'void build(long long int, long long int, long long int)':
fish2.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |      int mid=l+r>>1;
      |              ~^~
fish2.cpp:66:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |       if(t[node<<1].a>=t[node<<1|1].a)
      |       ^~
fish2.cpp:68:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |         t[node].c=t[node<<1].c+t[node<<1|1].c;
      |         ^
fish2.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:74:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 | int mid=l+r>>1;
      |         ~^~
fish2.cpp: In function 'ib get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |      int mid=l+r>>1;
      |              ~^~
fish2.cpp: In function 'long long int get_c(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:97:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |      int mid=l+r>>1;
      |              ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...