Submission #775619

# Submission time Handle Problem Language Result Execution time Memory
775619 2023-07-06T16:02:39 Z SteGG Addk (eJOI21_addk) C++17
100 / 100
175 ms 8648 KB
//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
//const int base = ;
int n, k;
int arr[maxn];
int q;
int change[11];

//others struct or class

struct Fen{
	vector<int> bit;
	int sz;
	Fen(){}
	Fen(int _sz) : sz(_sz){
		this->assign(_sz);
	}

	void assign(int _sz){
		sz = _sz;
		bit.assign(_sz + 1, 0);
	}

	void update(int p, int v){
		for(; p <= sz; p += p & (-p)){
			bit[p] += v;
		}
	}

	int get(int p){
		int result = 0;
		for(; p > 0; p -= p & (-p)){
			result += bit[p];
		}
		return result;
	}

	int get(int l, int r){
		return get(r) - get(l - 1);
	}
};

//others function

//others init

Fen prefix, increPrefix, decrePrefix;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	cin >> n >> k;
	prefix.assign(n);
	increPrefix.assign(n);
	decrePrefix.assign(n);
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
	}

	auto reverse = [&](int i){
		return n + 1 - i;
	};

	for(int i = 1; i <= n; i++){
		prefix.update(i, arr[i]);
		increPrefix.update(i, i * arr[i]);
		decrePrefix.update(i, reverse(i) * arr[i]);
	}

	auto getIncre = [&](int l, int r){
		return increPrefix.get(l, r) - prefix.get(l, r) * (l - 1);
	};

	auto getDecre = [&](int l, int r){
		return decrePrefix.get(l, r) - prefix.get(l, r) * (reverse(r) - 1);
	};

	cin >> q;
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			for(int i = 1; i <= k; i++){
				cin >> change[i];
			}
			int first = arr[change[1]];
			for(int i = 2; i <= k; i++){
				int diff = arr[change[i]] - arr[change[i - 1]];
				prefix.update(change[i - 1], diff);
				increPrefix.update(change[i - 1], diff * change[i - 1]);
				decrePrefix.update(change[i - 1], diff * reverse(change[i - 1]));
				arr[change[i - 1]] = arr[change[i]];
			}
			int diff = first - arr[change[k]];
			prefix.update(change[k], diff);
			increPrefix.update(change[k], diff * change[k]);
			decrePrefix.update(change[k], diff * reverse(change[k]));
			arr[change[k]] = first;
		}else{
			int l, r, m;
			cin >> l >> r >> m;
			int len = r - l + 1;
			int rm = len - m + 1;
			if(m > rm) m = rm;
			int mid = (l + r) >> 1;
			int sum = getIncre(l, mid) + getDecre(mid + 1, r);
			if(m < mid - l + 1){
				l += m;
				r -= m;
				mid = (l + r) >> 1;
				sum -= getIncre(l, mid) + getDecre(mid + 1, r);
			}

			cout << sum << endl;
		}
	}

	return 0;
}

Compilation message

Main.cpp: In function 'void open()':
Main.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 6 ms 528 KB Output is correct
6 Correct 7 ms 596 KB Output is correct
7 Correct 9 ms 724 KB Output is correct
8 Correct 10 ms 796 KB Output is correct
9 Correct 14 ms 980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 30 ms 1236 KB Output is correct
2 Correct 44 ms 2304 KB Output is correct
3 Correct 62 ms 3076 KB Output is correct
4 Correct 114 ms 5236 KB Output is correct
5 Correct 157 ms 7372 KB Output is correct
6 Correct 145 ms 7084 KB Output is correct
7 Correct 162 ms 7084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 79 ms 2392 KB Output is correct
2 Correct 132 ms 6380 KB Output is correct
3 Correct 168 ms 8648 KB Output is correct
4 Correct 175 ms 7764 KB Output is correct