Submission #971432

#	Time	Username	Problem	Language	Result	Execution time	Memory
971432		pan	Izbori (COCI22_izbori)	C++17	40 / 110	587 ms	524288 KiB

Main

#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

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 70