Submission #924610

#	Time	Username	Problem	Language	Result	Execution time	Memory
924610		pan	Addk (eJOI21_addk)	C++17	64 / 100	812 ms	40224 KiB

Main

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#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("%lld", &x);
#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 discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll n, k, q, t, l, r, m;
vector<ll> arr, change, newval;
struct node{
    ll s, e, m; //range is [s,e], m is the middle point
    ll val; //sum of [s,e]
    node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
    node (ll S, ll E){ //constructor called node
       s = S, e = E, m = (s+e)/2;
       val = 0; //initially all values are 0
	   l= r= nullptr;
	} 

	void create()
	{
		if(l==nullptr && s != e){ //node is not yet a leaf, so create two children
			l = new node(s, m); //create left child
			r = new node(m+1, e); //create right child
		}
	}
    void update(ll X, ll V){ //change the X-th element to be value V
       if(s == e) val = V; //node is leaf, update value
       else{ //go down to find the leaf
		   create();
           if(X <= m) { l->update(X, V);} //X is in the left child
           else {r->update(X, V);} //X is in the right child
           val = l->val + r->val; //update the range sum
       }
	}
    ll query(ll S, ll E){
       if(s == S && e == E) {return val;}//case 1
	   create();
       if(E <= m) return l->query(S, E); //case 2, recurse to left child
       else if(S >= m+1) return r->query(S, E); //case 3, recurse to right child
       else return l->query(S, m) + r->query(m+1, E); //case 4, split the query range, recurse to both childs
       

	}
} *root1, *root2, *root3;


int main()
{
	input(n); input(k);
	arr.resize(n+1);
	change.resize(k);
	newval.resize(k);
	root1 = new node(1, n);
	root2 = new node(1, n);
	root3 = new node(1, n);
	for (ll i=1; i<=n; ++i) 
	{
		input(arr[i]);
		root1->update(i, arr[i]);
		root2->update(i, arr[i]*i);
		root3->update(i, arr[i]*(n-i+1));
	}
	input(q);
	while (q--)
	{
		input(t);
		if (t==1)
		{
			
			for (ll i=0; i<k; ++i) input(change[i]);
			if (k==1) {continue;}
			for (ll i=0; i<k; ++i) 
			{
				if (i==k-1) newval[i] = arr[change[0]];
				else newval[i] = arr[change[i+1]];
			}
			for (ll i=0; i<k; ++i)
			{
				root1->update(change[i], newval[i]);
				root2->update(change[i], newval[i]*change[i]);
				root3->update(change[i], newval[i]*(n-change[i]+1));
				arr[change[i]] = newval[i];
			}
		}
		else
		{
			input(l); input(r); input(m);
			ll siz = r-l+1;
			if (siz<m) {print(0LL, '\n');}
			else if (m==1) 
			{
				print(root1->query(l, r), '\n');
			}
			else if (m==2)
			{
				ll ans  = arr[l] + arr[r];
				if (siz>2) ans+=2*root1->query(l+1, r-1);
				print(ans, '\n');
			}
			else 
			{
				ll ans = 0;
				ll maxx = min(siz-m+1, m);
				ans += root2->query(l, l+maxx-1) -  (l-1)*root1->query(l, l+maxx-1);
				ans+=root3->query(r-maxx+1, r) - (n-r)*root1->query(r-maxx+1, r);
				if ((r-maxx+1)-(l+maxx-1)>1) ans+=root1->query(l+maxx, r-maxx)*maxx;
				print(ans, '\n');
			}
		}
	}
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:67:2: note: in expansion of macro 'input'
   67 |  input(n); input(k);
      |  ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:67:12: note: in expansion of macro 'input'
   67 |  input(n); input(k);
      |            ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:76:3: note: in expansion of macro 'input'
   76 |   input(arr[i]);
      |   ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:81:2: note: in expansion of macro 'input'
   81 |  input(q);
      |  ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:84:3: note: in expansion of macro 'input'
   84 |   input(t);
      |   ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:88:27: note: in expansion of macro 'input'
   88 |    for (ll i=0; i<k; ++i) input(change[i]);
      |                           ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:105:4: note: in expansion of macro 'input'
  105 |    input(l); input(r); input(m);
      |    ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:105:14: note: in expansion of macro 'input'
  105 |    input(l); input(r); input(m);
      |              ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Main.cpp:105:24: note: in expansion of macro 'input'
  105 |    input(l); input(r); input(m);
      |                        ^~~~~

• Subtask 1: 0 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8