Submission #971432

#TimeUsernameProblemLanguageResultExecution timeMemory
971432panIzbori (COCI22_izbori)C++17
40 / 110
587 ms524288 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#include "bits_stdc++.h" #define endl '\n' #define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define input(x) scanf("%d", &x); #define input2(x, y) scanf("%lld%lld", &x, &y); #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z); #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a); #define print(x, y) printf("%lld%c", x, y); #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; #define all(x) x.begin(), x.end() #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); using namespace std; //using namespace __gnu_pbds; //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> //#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> typedef long long ll; typedef __int128 sll; typedef long double ld; typedef pair<ld, ll> pd; typedef pair<string, ll> psl; typedef pair<ll, ll> pi; typedef pair<ll, pi> pii; typedef pair<pi, pi> piii; ll n, arr[200005]; long long ans = 0; vector<ll> dis; vector<ll> dish[200005]; inline ll summation(ll x, ll y) { ll val = 0; if (x>=0) { val = y*(y+1)/2 - (x-1)*(x)/2; } else if (y<=0) { x = -x, y = -y; val = (x-1)*(x)/2 - y*(y+1)/2; } else { val = y*(y+1)/2 - abs(x)*(abs(x)+1)/2; } //show3(x,y, val); return val; } struct node{ int s, e, m; ll counter; ll summ; int lazy; node *l, *r; node (int S, int E) { s = S, e = E, m = s+e; if (m>=0) m/=2; else m = (m-1)/2; counter =0, summ = 0; lazy = 0; l=r=nullptr; } void create() { if(s != e && l==nullptr) { l = new node(s, m); r = new node(m+1, e); } } void propogate() { if (lazy==0) return; counter += lazy; summ += summation(s, e)*lazy; create(); if (s != e){ l->lazy+=lazy; r->lazy+=lazy; } lazy=0; } void update(int S, int E, ll V) { propogate(); if(s==S && e==E) {lazy += V; return;} else{ create(); if(E <= m) l->update(S, E, V); else if (m < S) r->update(S, E, V); else l->update(S, m, V),r->update(m+1, E, V); l->propogate(),r->propogate(); counter = l->counter + r->counter; summ = l-> summ + r->summ; } } ll querycount(int S, int E) { propogate(); if(s == S && e == E) return counter; create(); if(E <= m) return l->querycount(S, E); else if(S >= m+1) return r->querycount(S, E); else return l->querycount(S, m) + r->querycount(m+1, E); } ll querysum(int S, int E) { propogate(); if(s == S && e == E) return summ; create(); if(E <= m) return l->querysum(S, E); else if(S >= m+1) return r->querysum(S, E); else return l->querysum(S, m) + r->querysum(m+1, E); } } *root; int main() { input(n); for (ll i=0; i<n; ++i) { input(arr[i]); dis.pb(arr[i]); } discretize(dis); for (ll i=0; i<n; ++i) { ll ind = lb(all(dis), arr[i])-dis.begin(); dish[ind].pb(i); } root = new node(-n-5, n+5); for (ll i=0; i<dis.size(); ++i) { //show(i); ll offset = 0; root = new node(-n-5, n+5); vector<ll> & now = dish[i]; vector<pi> log; for (ll j=0; j<now.size(); ++j) { ll start; if (j) start = now[j-1] + 1; else start = 0; ll len = now[j]-start; //show(len); if (len>=1) {root->update(offset, offset+len-1, 1);log.pb(mp(offset, offset+len-1));} offset += len; root->update(offset, offset, 1); log.pb(mp(offset, offset)); offset--; //show(offset); ll end; if (j+1<now.size()) end = now[j+1] -1; else end = n-1; len = end-now[j]+1; //show(len); //show2( root->querysum(offset+1, offset+len), root->querycount(offset+1, offset+len)); ans += root->querysum(offset+1, offset+len) - offset*root->querycount(offset+1, offset+len); //show(ans); if (offset+len+1<=n+1) ans += root->querycount(offset+len+1, n+1)*len; //show(ans); } for (pi u: log) root->update(u.f, u.s, -1); } print(ans, '\n'); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:12:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   12 | #define input(x) scanf("%d", &x);
      |                        ^~~~  ~~~~
      |                              |
      |                              ll* {aka long long int*}
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   15 | #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   16 | #define print(x, y) printf("%lld%c", x, y);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   17 | #define show(x) cerr << #x << " is " << x << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   18 | #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   19 | #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   20 | #define all(x) x.begin(), x.end()
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   21 | #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 | using namespace std;
      | ~~~~~~~~~~~~~~~~~~~~    
   23 | //using namespace __gnu_pbds;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   24 | //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   25 | //#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   26 | typedef long long ll;
      | ~~~~~~~~~~~~~~~~~~~~~   
   27 | typedef __int128  sll;
      | ~~~~~~~~~~~~~~~~~~~~~~  
   28 | typedef long double ld;
      | ~~~~~~~~~~~~~~~~~~~~~~~ 
   29 | typedef pair<ld, ll> pd;
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   30 | typedef pair<string, ll> psl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   31 | typedef pair<ll, ll> pi;
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   32 | typedef pair<ll, pi> pii;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~
   33 | typedef pair<pi, pi> piii;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~
   34 | 
      |                         
   35 | ll n, arr[200005];
      | ~~~~~~~~~~~~~~~~~~      
   36 | long long ans = 0;
      | ~~~~~~~~~~~~~~~~~~      
   37 | vector<ll> dis;
      | ~~~~~~~~~~~~~~~         
   38 | vector<ll> dish[200005];
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   39 | inline ll summation(ll x, ll y)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 | {
      | ~                       
   41 |  ll val = 0;
      |  ~~~~~~~~~~~            
   42 |  if (x>=0)
      |  ~~~~~~~~~              
   43 |  {
      |  ~                      
   44 |   val = y*(y+1)/2 - (x-1)*(x)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |  }
      |  ~                      
   46 |  else if (y<=0)
      |  ~~~~~~~~~~~~~~         
   47 |  {
      |  ~                      
   48 |   x = -x, y = -y;
      |   ~~~~~~~~~~~~~~~       
   49 |   val = (x-1)*(x)/2 - y*(y+1)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   50 |  }
      |  ~                      
   51 |  else
      |  ~~~~                   
   52 |  {
      |  ~                      
   53 |   val = y*(y+1)/2 - abs(x)*(abs(x)+1)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   54 |  }
      |  ~                      
   55 |  //show3(x,y, val);
      |  ~~~~~~~~~~~~~~~~~~     
   56 |  return val;
      |  ~~~~~~~~~~~            
   57 | 
      |                         
   58 | }
      | ~                       
   59 | struct node{
      | ~~~~~~~~~~~~            
   60 | 
      |                         
   61 |     int s, e, m;
      |     ~~~~~~~~~~~~        
   62 |     ll counter;
      |     ~~~~~~~~~~~         
   63 |     ll summ;
      |     ~~~~~~~~            
   64 |     int lazy;
      |     ~~~~~~~~~           
   65 |     node *l, *r;
      |     ~~~~~~~~~~~~        
   66 |  node (int S, int E)
      |  ~~~~~~~~~~~~~~~~~~~    
   67 |  {
      |  ~                      
   68 |        s = S, e = E, m = s+e;
      |        ~~~~~~~~~~~~~~~~~~~~~~
   69 |        if (m>=0) m/=2;
      |        ~~~~~~~~~~~~~~~  
   70 |        else  m = (m-1)/2;
      |        ~~~~~~~~~~~~~~~~~~
   71 |        counter =0, summ = 0;
      |        ~~~~~~~~~~~~~~~~~~~~~
   72 |        lazy = 0;
      |        ~~~~~~~~~        
   73 |        l=r=nullptr;
      |        ~~~~~~~~~~~~     
   74 | 
      |                         
   75 |     }
      |     ~                   
   76 |     void create()
      |     ~~~~~~~~~~~~~       
   77 |     {
      |     ~                   
   78 |     if(s != e && l==nullptr)
      |     ~~~~~~~~~~~~~~~~~~~~~~~~
   79 |        {
      |        ~                
   80 |            l = new node(s, m);
      |            ~~~~~~~~~~~~~~~~~~~
   81 |            r = new node(m+1, e);
      |            ~~~~~~~~~~~~~~~~~~~~~
   82 |        }
      |        ~                
   83 |     }
      |     ~                   
   84 | 
      |                         
   85 |  void propogate()
      |  ~~~~~~~~~~~~~~~~       
   86 |  {
      |  ~                      
   87 |        if (lazy==0) return;
      |        ~~~~~~~~~~~~~~~~~~~~
   88 |        counter += lazy;
      |        ~~~~~~~~~~~~~~~~ 
   89 |        summ += summation(s, e)*lazy;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   90 |        create();
      |        ~~~~~~~~~        
   91 |        if (s != e){
      |        ~~~~~~~~~~~~     
   92 |            l->lazy+=lazy;
      |            ~~~~~~~~~~~~~~
   93 |            r->lazy+=lazy;
      |            ~~~~~~~~~~~~~~
   94 |        }
      |        ~                
   95 |        lazy=0;
      |        ~~~~~~~          
   96 |     }
      |     ~                   
   97 |  void update(int S, int E, ll V)
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   98 |  {
      |  ~                      
   99 |     propogate();
      |     ~~~~~~~~~~~~        
  100 |        if(s==S && e==E) {lazy += V;  return;}
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  101 |        else{
      |        ~~~~~            
  102 |            create();
      |            ~~~~~~~~~    
  103 |            if(E <= m) l->update(S, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  104 |            else if (m < S) r->update(S, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  105 |            else l->update(S, m, V),r->update(m+1, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  106 |            l->propogate(),r->propogate();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  107 |            counter = l->counter + r->counter;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  108 |            summ = l-> summ + r->summ;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~
  109 |        }
      |        ~                
  110 |     }
      |     ~                   
  111 |  ll querycount(int S, int E)
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  112 |  {
      |  ~                      
  113 | 
      |                         
  114 |        propogate();
      |        ~~~~~~~~~~~~     
  115 |        if(s == S && e == E) return counter;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  116 |        create();
      |        ~~~~~~~~~        
  117 |        if(E <= m) return l->querycount(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |        else if(S >= m+1) return r->querycount(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  119 |        else return l->querycount(S, m) + r->querycount(m+1, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  120 |     }
      |     ~                   
  121 |     ll querysum(int S, int E)
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~
  122 |  {
      |  ~                      
  123 | 
      |                         
  124 |        propogate();
      |        ~~~~~~~~~~~~     
  125 |        if(s == S && e == E) return summ;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  126 |        create();
      |        ~~~~~~~~~        
  127 |        if(E <= m) return l->querysum(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  128 |        else if(S >= m+1) return r->querysum(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  129 |        else return l->querysum(S, m) + r->querysum(m+1, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  130 |     }
      |     ~                   
  131 | 
      |                         
  132 | 
      |                         
  133 | } *root;
      | ~~~~~~~~                
  134 | 
      |                         
  135 | 
      |                         
  136 | 
      |                         
  137 | int main()
      | ~~~~~~~~~~              
  138 | {
      | ~                       
  139 |  input(n);
      |  ~~~~~~~                
Main.cpp:139:2: note: in expansion of macro 'input'
  139 |  input(n);
      |  ^~~~~
Main.cpp:12:26: note: format string is defined here
   12 | #define input(x) scanf("%d", &x);
      |                         ~^
      |                          |
      |                          int*
      |                         %lld
Main.cpp:12:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   12 | #define input(x) scanf("%d", &x);
      |                        ^~~~  ~~~~
      |                              |
      |                              ll* {aka long long int*}
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   15 | #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   16 | #define print(x, y) printf("%lld%c", x, y);
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   17 | #define show(x) cerr << #x << " is " << x << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   18 | #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   19 | #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   20 | #define all(x) x.begin(), x.end()
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   21 | #define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   22 | using namespace std;
      | ~~~~~~~~~~~~~~~~~~~~    
   23 | //using namespace __gnu_pbds;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   24 | //#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   25 | //#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   26 | typedef long long ll;
      | ~~~~~~~~~~~~~~~~~~~~~   
   27 | typedef __int128  sll;
      | ~~~~~~~~~~~~~~~~~~~~~~  
   28 | typedef long double ld;
      | ~~~~~~~~~~~~~~~~~~~~~~~ 
   29 | typedef pair<ld, ll> pd;
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   30 | typedef pair<string, ll> psl;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   31 | typedef pair<ll, ll> pi;
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   32 | typedef pair<ll, pi> pii;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~
   33 | typedef pair<pi, pi> piii;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~
   34 | 
      |                         
   35 | ll n, arr[200005];
      | ~~~~~~~~~~~~~~~~~~      
   36 | long long ans = 0;
      | ~~~~~~~~~~~~~~~~~~      
   37 | vector<ll> dis;
      | ~~~~~~~~~~~~~~~         
   38 | vector<ll> dish[200005];
      | ~~~~~~~~~~~~~~~~~~~~~~~~
   39 | inline ll summation(ll x, ll y)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 | {
      | ~                       
   41 |  ll val = 0;
      |  ~~~~~~~~~~~            
   42 |  if (x>=0)
      |  ~~~~~~~~~              
   43 |  {
      |  ~                      
   44 |   val = y*(y+1)/2 - (x-1)*(x)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |  }
      |  ~                      
   46 |  else if (y<=0)
      |  ~~~~~~~~~~~~~~         
   47 |  {
      |  ~                      
   48 |   x = -x, y = -y;
      |   ~~~~~~~~~~~~~~~       
   49 |   val = (x-1)*(x)/2 - y*(y+1)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   50 |  }
      |  ~                      
   51 |  else
      |  ~~~~                   
   52 |  {
      |  ~                      
   53 |   val = y*(y+1)/2 - abs(x)*(abs(x)+1)/2;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   54 |  }
      |  ~                      
   55 |  //show3(x,y, val);
      |  ~~~~~~~~~~~~~~~~~~     
   56 |  return val;
      |  ~~~~~~~~~~~            
   57 | 
      |                         
   58 | }
      | ~                       
   59 | struct node{
      | ~~~~~~~~~~~~            
   60 | 
      |                         
   61 |     int s, e, m;
      |     ~~~~~~~~~~~~        
   62 |     ll counter;
      |     ~~~~~~~~~~~         
   63 |     ll summ;
      |     ~~~~~~~~            
   64 |     int lazy;
      |     ~~~~~~~~~           
   65 |     node *l, *r;
      |     ~~~~~~~~~~~~        
   66 |  node (int S, int E)
      |  ~~~~~~~~~~~~~~~~~~~    
   67 |  {
      |  ~                      
   68 |        s = S, e = E, m = s+e;
      |        ~~~~~~~~~~~~~~~~~~~~~~
   69 |        if (m>=0) m/=2;
      |        ~~~~~~~~~~~~~~~  
   70 |        else  m = (m-1)/2;
      |        ~~~~~~~~~~~~~~~~~~
   71 |        counter =0, summ = 0;
      |        ~~~~~~~~~~~~~~~~~~~~~
   72 |        lazy = 0;
      |        ~~~~~~~~~        
   73 |        l=r=nullptr;
      |        ~~~~~~~~~~~~     
   74 | 
      |                         
   75 |     }
      |     ~                   
   76 |     void create()
      |     ~~~~~~~~~~~~~       
   77 |     {
      |     ~                   
   78 |     if(s != e && l==nullptr)
      |     ~~~~~~~~~~~~~~~~~~~~~~~~
   79 |        {
      |        ~                
   80 |            l = new node(s, m);
      |            ~~~~~~~~~~~~~~~~~~~
   81 |            r = new node(m+1, e);
      |            ~~~~~~~~~~~~~~~~~~~~~
   82 |        }
      |        ~                
   83 |     }
      |     ~                   
   84 | 
      |                         
   85 |  void propogate()
      |  ~~~~~~~~~~~~~~~~       
   86 |  {
      |  ~                      
   87 |        if (lazy==0) return;
      |        ~~~~~~~~~~~~~~~~~~~~
   88 |        counter += lazy;
      |        ~~~~~~~~~~~~~~~~ 
   89 |        summ += summation(s, e)*lazy;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   90 |        create();
      |        ~~~~~~~~~        
   91 |        if (s != e){
      |        ~~~~~~~~~~~~     
   92 |            l->lazy+=lazy;
      |            ~~~~~~~~~~~~~~
   93 |            r->lazy+=lazy;
      |            ~~~~~~~~~~~~~~
   94 |        }
      |        ~                
   95 |        lazy=0;
      |        ~~~~~~~          
   96 |     }
      |     ~                   
   97 |  void update(int S, int E, ll V)
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   98 |  {
      |  ~                      
   99 |     propogate();
      |     ~~~~~~~~~~~~        
  100 |        if(s==S && e==E) {lazy += V;  return;}
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  101 |        else{
      |        ~~~~~            
  102 |            create();
      |            ~~~~~~~~~    
  103 |            if(E <= m) l->update(S, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  104 |            else if (m < S) r->update(S, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  105 |            else l->update(S, m, V),r->update(m+1, E, V);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  106 |            l->propogate(),r->propogate();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  107 |            counter = l->counter + r->counter;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  108 |            summ = l-> summ + r->summ;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~
  109 |        }
      |        ~                
  110 |     }
      |     ~                   
  111 |  ll querycount(int S, int E)
      |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  112 |  {
      |  ~                      
  113 | 
      |                         
  114 |        propogate();
      |        ~~~~~~~~~~~~     
  115 |        if(s == S && e == E) return counter;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  116 |        create();
      |        ~~~~~~~~~        
  117 |        if(E <= m) return l->querycount(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |        else if(S >= m+1) return r->querycount(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  119 |        else return l->querycount(S, m) + r->querycount(m+1, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  120 |     }
      |     ~                   
  121 |     ll querysum(int S, int E)
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~
  122 |  {
      |  ~                      
  123 | 
      |                         
  124 |        propogate();
      |        ~~~~~~~~~~~~     
  125 |        if(s == S && e == E) return summ;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  126 |        create();
      |        ~~~~~~~~~        
  127 |        if(E <= m) return l->querysum(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  128 |        else if(S >= m+1) return r->querysum(S, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  129 |        else return l->querysum(S, m) + r->querysum(m+1, E);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  130 |     }
      |     ~                   
  131 | 
      |                         
  132 | 
      |                         
  133 | } *root;
      | ~~~~~~~~                
  134 | 
      |                         
  135 | 
      |                         
  136 | 
      |                         
  137 | int main()
      | ~~~~~~~~~~              
  138 | {
      | ~                       
  139 |  input(n);
      |  ~~~~~~~~~              
  140 |  for (ll i=0; i<n; ++i)
      |  ~~~~~~~~~~~~~~~~~~~~~~ 
  141 |  {
      |  ~                      
  142 |   input(arr[i]);
      |   ~~~~~~~~~~~~          
Main.cpp:142:3: note: in expansion of macro 'input'
  142 |   input(arr[i]);
      |   ^~~~~
Main.cp
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...