Submission #390600

#TimeUsernameProblemLanguageResultExecution timeMemory
390600PanTkdGrowing Trees (BOI11_grow)C++14
0 / 100
1091 ms2464 KiB
// // main.cpp // // Created by Panagiotis Chadjicostas on // Copyright © Panagiotis Hadjicostas. All rights reserved. // #include <iostream> #include <algorithm> #include <assert.h> #include <bitset> #include <complex> #include <deque> #include <fstream> #include <iomanip> #include <iterator> #include <limits> #include <list> #include <cstring> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #include <unordered_map> using namespace std; typedef int ll; typedef vector<ll> vi; #define fo(i,a,b) for(int i = a; i<=b; i++) #define f(i,b) for(int i=0;i<b;i++) #define F first #define S second const ll MOD=ll(1e9)+7; const ll MAXN=2*ll(1e5); void checker(){ ll n=rand()%20+2; vi a(n,ll()); for(ll i=0;i<n;i++){ a[i]=rand()%20+2; } for(ll b=0;b<(1<<n);b++){ vi on,off; for(ll i=0;i<n;i++){ if(i&(1<<i)){ on.push_back(i); } else{ off.push_back(i); } } } } ///////////////////////////////////////////////////////////////////////////////////////////////// ll n; ll seg[4*MAXN],a[MAXN],lazy[MAXN]; void Build(int node, int l, int r) { if(l == r) { seg[node] = a[l]; a[l] = node; return; } int mid = (l + r) >> 1; Build(node << 1, l, mid); Build(node << 1 | 1, mid + 1, r); seg[node] = max(seg[node << 1], seg[node << 1 | 1]); } void push(ll idx,ll s,ll e){ //// if(!lazy[idx])return; seg[idx]+=lazy[idx]; ll m=(s+e)>>1; if(s!=e){ lazy[idx<<1]+=lazy[idx]; //seg[idx<<1]+=lazy[idx]; lazy[idx<<1|1]+=lazy[idx]; //seg[idx<<1|1]+=lazy[idx]; } lazy[idx]=0; } void update(ll s,ll e,ll qs,ll qe,ll idx,ll val){ if(s>qe||e<qs){ return; } push(idx,s,e); if(qs<=s&&e<=qe){ lazy[idx]+=val; push(idx,s,e); return; } ll m=(s+e)>>1; update(s,m,qs,qe,idx<<1,val); update(m+1,e,qs,qe,idx<<1|1,val); seg[idx]=max(seg[idx<<1],seg[idx<<1|1]); } ll query(ll s,ll e,ll idx,ll val){ if(e<s)return 0; push(idx,s,e); if(seg[idx]<=val) return e-s+1; //if(seg[idx]>val)return 0; if(e-s==0)return 0; ll m=(e+s)>>1; return query(s,m,idx<<1,val)+query(m+1,e,idx<<1|1,val); } ll bs(ll idx,ll l,ll r,ll val){ if(r<l)return -1; if(val>r)return -1; push(idx,l,r); if(r-l==0)return seg[idx]; ll m=(l+r)>>1; if(val<=m){ return bs(idx<<1,l,m,val); } else{ return bs(idx<<1|1,m+1,r,val); } } void upd(){ ll c,h;cin>>c>>h; ll left=query(0,n-1,1,h-1); //cout<<left<<endl; ll val=bs(1,0,n-1,left+c-1); //cout<<val<<endl; ll r1=query(0,n-1,1,val-1),r2=query(0,n-1,1,val); //cout<<r1<<' '<<r2<<endl; update(0,n,left,r1-1,1,1); ll tmp=c+left-r1; update(0,n-1,max(r1+1,r2-tmp+1)-1,r2-1,1,1); } void qur(){ ll l,r; cin>>l>>r; cout<<query(0,n-1,1,r)-query(0,n-1,1,l-1)<<endl; } void solve(){ ll q;cin>>n>>q; //vi a(n,ll()); f(i,n){ cin>>a[i]; } sort(a,a+n); Build(1,0,n-1); //cout<<seg[2]<<endl; for(ll queries=1;queries<=q;queries++){ char type;cin>>type; if(type=='F'){ upd(); } else{ qur(); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t=1;//cin>>t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

grow.cpp: In function 'void push(ll, ll, ll)':
grow.cpp:77:8: warning: unused variable 'm' [-Wunused-variable]
   77 |     ll m=(s+e)>>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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...