Submission #60226

#TimeUsernameProblemLanguageResultExecution timeMemory
60226IvanCGrowing Trees (BOI11_grow)C++17
100 / 100
495 ms42524 KiB
#include <bits/stdc++.h> using namespace std; typedef struct node* pnode; struct node{ pnode l,r; int key,prior,size,lazy; node(int _key){ l = r = NULL; key = _key; prior = rand(); size = 1; lazy = 0; } }; int sz(pnode t){ if(t == NULL) return 0; return t->size; } void update(pnode t){ if(t) t->size = sz(t->l) + 1 + sz(t->r); } void propagate(pnode t){ if(t == NULL) return; if(t->lazy == 0) return; t->key += t->lazy; if(t->l) t->l->lazy += t->lazy; if(t->r) t->r->lazy += t->lazy; t->lazy = 0; } void split(pnode t,int key,pnode &l,pnode &r){ propagate(t); if(t == NULL){ l = r = NULL; } else if(key < t->key){ split(t->l,key,l,t->l); r = t; } else{ split(t->r,key,t->r,r); l = t; } update(t); } void merge(pnode &t,pnode l,pnode r){ propagate(l); propagate(r); if(l == NULL){ t = r; } else if(r == NULL){ t = l; } else if(l->prior > r->prior){ merge(l->r,l->r,r); t = l; } else{ merge(r->l,l,r->l); t = r; } update(t); } void insert(pnode &t,int key){ pnode aux = new node(key); pnode L,R; split(t,key,L,R); merge(t,L,aux); merge(t,t,R); } int kth(pnode t,pnode &l,pnode &r,int count){ propagate(t); if(sz(t->l) + 1 == count){ r = t->r; t->r = NULL; l = t; update(t); return t->key; } if(count <= sz(t->l)){ int ans = kth(t->l,l,t->l,count); r = t; update(t); return ans; } else{ int ans = kth(t->r,t->r,r,count - sz(t->l) - 1); l = t; update(t); return ans; } } void query_F(pnode &t,int ci,int hi){ pnode L = NULL,mid1 = NULL,mid2 = NULL,mid3 = NULL,R = NULL; split(t,hi-1,L,R); if(R){ //printf("C %d H %d Rs %d\n",ci,hi,sz(R)); ci = min(ci,sz(R)); int quebra = kth(R,mid1,R,ci); if(mid1) mid1->lazy += 1; split(R,quebra,mid3,R); split(mid1,quebra,mid1,mid2); merge(t,L,mid1); merge(t,t,mid3); merge(t,t,mid2); merge(t,t,R); } else{ merge(t,L,R); } } int query_C(pnode &t,int a,int b){ pnode L,mid,R; split(t,a-1,L,R); split(R,b,mid,R); int ans = sz(mid); merge(t,L,mid); merge(t,t,R); return ans; } int main(){ int N,M; pnode raiz = NULL; scanf("%d %d",&N,&M); for(int i = 1;i<=N;i++){ int x; scanf("%d",&x); insert(raiz,x); } while(M--){ char op; int a,b; scanf(" %c %d %d",&op,&a,&b); if(op == 'F'){ query_F(raiz,a,b); } else{ printf("%d\n",query_C(raiz,a,b)); } } return 0; }

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
grow.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
grow.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d",&op,&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...