Submission #1213637

#TimeUsernameProblemLanguageResultExecution timeMemory
1213637sitingfakeGrowing Trees (BOI11_grow)C++20
0 / 100
67 ms10308 KiB
#include<bits/stdc++.h> using namespace std; // define #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; #define ll long long #define ld double #define ii pair<int,int> #define se second #define fi first #define iii pair<int,ii> #define all(v) v.begin(),v.end() #define bit(x,i) (((x)>>(i))&1LL) #define flip(x,i) ((x)^(1LL<<(i))) #define ms(d,x) memset(d,x,sizeof(d)) #define sitingfake 1 #define orz 1 //constant const ll mod = 1e9 + 7; const long long linf = 4557430888798830399; const int inf = 1061109567; const int maxarr = 1e6 + 5; const int dx[] = {0,1,-1,0}; const int dy[] = {1,0,0,-1}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } inline void Plus(ll & a ,ll b) { b %= mod; a += b; if(a >= mod) a -= mod; if(a < 0) a += mod; return; } inline void Mul(ll & a, ll b) { a %= mod; b %= mod; a *= b; a %= mod; return; } //code const int maxn = 1e5 + 7; int a[maxn]; int n , q; struct Node { ll Max; ll Min; int Cnt; int Lazy; Node () { Max = Cnt = Lazy = 0; } Node operator + (Node &other) { Node ans; ans.Max = max(Max , other.Max); ans.Min = min(Min , other.Min); if(Max == ans.Max) ans.Cnt += Cnt; if(other.Max == ans.Max) ans.Cnt += other.Cnt; return ans; } }st[4 * maxn]; void Build(int i ,int l ,int r) { if(l == r) { st[i].Max = a[l]; st[i].Min = a[l]; st[i].Cnt = 1; return; } int mid = (r + l) >> 1; Build(i * 2, l , mid); Build(i * 2 + 1, mid + 1 , r); st[i] = st[i * 2] + st[i * 2 + 1]; } void ApplyAdd(int i , int val) { st[i].Max += 1ll * val; st[i].Min += 1ll * val; st[i].Lazy += val; } void Push(int i) { if(st[i].Lazy) { ApplyAdd(i * 2 , st[i].Lazy); ApplyAdd(i * 2 + 1, st[i].Lazy); } } void update(int i ,int l ,int r, int u ,int v) { if(u > r || v < l) return; if(u <= l && r <= v) { ApplyAdd(i , 1); return; } int mid = (r + l) >> 1; Push(i); update(i * 2 , l , mid , u , v); update(i * 2 + 1, mid + 1, r , u , v); st[i] = st[i * 2] + st[i * 2 + 1]; } ii get(int i , int l ,int r, int u ,int v) { if(u > r || v < l) return ii(0 ,0); if(u <= l && r <= v) return ii(st[i].Max , st[i].Cnt); int mid = (r + l) >> 1; Push(i); ii ans1 = get(i * 2 , l , mid , u , v); ii ans2 = get(i * 2 + 1, mid + 1, r, u , v); if(ans1.fi == ans2.fi) { return ii(ans1.fi , ans1.se + ans2.se); } else if(ans1.fi > ans2.fi) return ans1; else return ans2; } int walk(int i , int l ,int r, int val) { if(st[i].Min > val) { return 0; } if(l == r) return l; int mid = (r + l) >> 1; Push(i); int res = walk(i * 2 + 1, mid + 1 , r, val); if(res == 0) return walk(i * 2 , l , mid , val); return res; } void Up() { int c , h; cin >> c >> h; if(st[1].Max < h) return; int l = walk(1 , 1, n, h - 1); if(l + c >= n) { update(1 , 1, n , l + 1, n); } else { l++; ii info = get(1 , 1, n , l , l + c - 1); int r = walk(1 , 1, n , info.fi); if(r == l + c - 1) { update(1 , 1, n , l , l + c - 1); } else { update(1 , 1, n , r - info.se + 1, r); if(l <= l + c - 1 - info.se) { update(1 , 1, n , l , l + c - 1 - info.se); } } } } void Query() { int mini , maxi; cin >> mini >> maxi; int l = walk(1 , 1 , n , mini - 1) , r = walk(1 , 1, n , maxi); cout << r - l << "\n"; } void solve(void) { cin >> n >> q; for(int i = 1; i <= n;i++) { cin >> a[i]; } sort(a + 1 , a + n + 1); Build(1 , 1, n); while(q--) { char type; cin >> type; if(type == 'F') { Up(); } else { Query(); } } } /** 5 1 1 3 2 5 2 F 2 1 **/ signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int tc; tc = 1; while(tc--) solve(); //execute; }

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:263:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
grow.cpp:264:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...