Submission #850317

#TimeUsernameProblemLanguageResultExecution timeMemory
850317Essa2006Growing Trees (BOI11_grow)C++14
10 / 100
94 ms5468 KiB
#ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif // C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif //#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define FF first #define SS second #define all(a) a.begin(), a.end() #define mod (ll)(1000000007) const int pr=18, s_p=1<<(pr), e_p=(1<<(pr+1))-1; int n, m; vector<int>A, S_sum; void pre(){ A.clear(), S_sum.clear(); A.resize(n), S_sum.resize(1<<(pr+1)); } void update(int ind, int c){ S_sum[ind]+=c; while(ind/=2) S_sum[ind]+=c; } int get(int id, int u, int v, int l, int r){ if(l>v || r<u) return 0; if(l>=u && r<=v) return S_sum[id]; int md=(l+r)/2; return get(id*2, u, v, l, md)+get(id*2+1, u, v, md+1, r); } int get_pos(int id, int bef, int sum, bool fir, int l, int r){ if((fir && bef+S_sum[id]<sum) || (!fir && bef>sum) || l>n-1+s_p) return -1; if(l==r){ if(fir){ if(bef+S_sum[id]>=sum) return l-s_p; } else{ if(bef+S_sum[id]<=sum) return l-s_p; } return -1; } int md=(l+r)/2; if(fir){ int res=get_pos(id*2, bef, sum, fir, l, md); if(res!=-1) return res; return get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r); } else{ int res=get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r); if(res!=-1) return res; return get_pos(id*2, bef, sum, fir, l, md); } } int calc(int u, int v){ if(u>v) return 0; return get(1, u+s_p, v+s_p, s_p, e_p); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; cout<<endl; pre(); for(int i=0;i<n;i++){ cin>>A[i]; } sort(all(A)); for(int i=n-1;i>0;i--){ A[i]-=A[i-1]; update(i+s_p, A[i]); } update(s_p, A[0]); while(m--){ char type; int x, y; cin>>type>>x>>y; if(type=='F'){ // change int l=get_pos(1, 0, y, 1, s_p, e_p); if(l==-1) continue; int r=min(n-1, l+x-1); int diff=r-l+1; if(calc(0, l)==calc(0, r)){ while(r+1<n && A[r+1]==0) r++; l=max(0, r-x+1); assert(diff==r-l+1); //assert(calc(0, get_pos(1, 0, y, 1, s_p, e_p))==calc(0, l)); A[l]++, update(l+s_p, 1); if(r+1<n) A[r+1]--, update(r+1+s_p, -1); continue; } int need=calc(0, r); int r_fir=get_pos(1, 0, need, 1, s_p, e_p); int r_las=get_pos(1, 0, need, 0, s_p, e_p); A[l]++, update(l+s_p, 1); if(r_las+1<n) A[r_las+1]--, update(r_las+1+s_p, -1); if(r!=r_las){ A[r_fir]--, update(r_fir+s_p, -1), A[r_las-(r-r_fir)]++, update(r_las-(r-r_fir)+s_p, 1); } } else{ // print int l=get_pos(1, 0, x, 1, s_p, e_p); int r=get_pos(1, 0, y, 0, s_p, e_p); int ans=r-l+1; if(l==-1 || r==-1 || l>r) ans=0; cout<<ans<<endl; } } }
#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...