Submission #851647

#TimeUsernameProblemLanguageResultExecution timeMemory
851647MilosMilutinovicFish 2 (JOI22_fish2)C++17
8 / 100
4019 ms35664 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> B; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=100100; const int M=8*N; const int inf=(int)1e9; int n,q,a[N]; namespace sum { ll c[N]; void modify(int p,int v) { for (;p<N;p+=p&-p) c[p]+=v; } ll get(int p) { ll r=0; for (;p>0;p-=p&-p) r+=c[p]; return r; } ll get(int l,int r) { return get(r)-get(l-1); } }; namespace segs { vector<PII> st[M]; void add(int x,int l,int r,int ql,int qr,PII p) { if (l>r||l>qr||r<ql) { return; } if (ql<=l&&r<=qr) { st[x].pb(p); return; } int mid=l+r>>1; add(x*2,l,mid,ql,qr,p); add(x*2+1,mid+1,r,ql,qr,p); } }; namespace cnt { PII st[M]; int lzy[M]; void push(int x) { st[x*2].fi+=lzy[x]; st[x*2+1].fi+=lzy[x]; lzy[x*2]+=lzy[x]; lzy[x*2+1]+=lzy[x]; lzy[x]=0; } PII mrg(PII a,PII b) { PII r; r.fi=min(a.fi,b.fi); r.se=(a.fi==r.fi?a.se:0)+(b.fi==r.fi?b.se:0); return r; } void pull(int x) { st[x]=mrg(st[x*2],st[x*2+1]); } void build(int x,int l,int r) { if (l==r) { st[x].fi=0; st[x].se=1; return; } int mid=l+r>>1; build(x*2,l,mid); build(x*2+1,mid+1,r); pull(x); } void add(int x,int l,int r,int ql,int qr,int v) { if (l>r||l>qr||r<ql) { return; } if (ql<=l&&r<=qr) { st[x].fi+=v; lzy[x]+=v; push(x); return; } push(x); int mid=l+r>>1; add(x*2,l,mid,ql,qr,v); add(x*2+1,mid+1,r,ql,qr,v); pull(x); } PII query(int x,int l,int r,int ql,int qr) { if (l>r||l>qr||r<ql) { return mp(inf,0); } if (ql<=l&&r<=qr) { return st[x]; } push(x); int mid=l+r>>1; auto qvl=query(x*2,l,mid,ql,qr); auto qvr=query(x*2+1,mid+1,r,ql,qr); pull(x); return mrg(qvl,qvr); } int sol(int l,int r) { auto p=query(1,1,n,l,r); if (p.fi==0) { return p.se; } else { return 0; } } }; void build() { cnt::build(1,1,n); rep(i,1,n+1) sum::modify(i,a[i]); stack<int> stk; rep(i,1,n+1) { while (SZ(stk)>0&&a[i]>a[stk.top()]) { int L=stk.top(); int R=i; if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) { //printf("add %d %d\n",L,R); segs::add(1,1,n,L,R,mp(L,R)); cnt::add(1,1,n,L+1,R-1,1); } stk.pop(); } stk.push(i); } while (SZ(stk)) stk.pop(); per(i,1,n+1) { while (SZ(stk)>0&&a[i]>=a[stk.top()]) { int L=i; int R=stk.top(); if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) { //printf("add %d %d\n",L,R); segs::add(1,1,n,L,R,mp(L,R)); cnt::add(1,1,n,L+1,R-1,1); } stk.pop(); } stk.push(i); } } int main() { scanf("%d",&n); rep(i,1,n+1) { scanf("%d",&a[i]); } build(); scanf("%d",&q); while (q--) { int op; scanf("%d",&op); if (op==1) { } else { int l,r; scanf("%d%d",&l,&r); int nl=l,nr=r; rep(i,l+1,r+1) { if (a[i]>sum::get(l,i-1)) { nl=i; } } per(i,l,r) { if (a[i]>sum::get(i+1,r)) { nr=i; } } l=nl; r=nr; printf("%d\n",cnt::sol(l,r)); } } }

Compilation message (stderr)

fish2.cpp: In function 'void segs::add(int, int, int, int, int, PII)':
fish2.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void cnt::build(int, int, int)':
fish2.cpp:85:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void cnt::add(int, int, int, int, int, int)':
fish2.cpp:101:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'PII cnt::query(int, int, int, int, int)':
fish2.cpp:114:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
fish2.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:177:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~
#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...