Submission #881168

#	Time	Username	Problem	Language	Result	Execution time	Memory
881168		serifefedartar	Garaža (COCI17_garaza)	C++17	0 / 160	2027 ms	45484 KiB

garaza

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

struct Node {
	ll ans;
	vector<pair<int,int>> l_r, r_l;
	Node() { ans = 0; }
};

Node sg[4*MAXN];
vector<int> A;
Node merge(Node A, Node B) {
	Node new_node;
	new_node.ans = A.ans + B.ans;
	new_node.l_r.push_back({0, 0});
	new_node.r_l.push_back({0, 0});
	for (auto u : A.l_r)
		new_node.l_r.push_back(u);
	for (auto u : B.r_l)
		new_node.r_l.push_back(u);

	vector<pair<int,int>> lft = A.r_l;
	vector<pair<int,int>> rght = B.l_r;
	vector<int> prefL, prefR;
	for (auto u : lft) {
		if (prefL.size() == 0)
			prefL.push_back(u.s);
		else
			prefL.push_back(u.s + prefL.back());
	}
	for (auto u : rght) {
		if (prefR.size() == 0)
			prefR.push_back(u.s);
		else
			prefR.push_back(u.s + prefR.back());
	}

	for (int i = 0; i < lft.size(); i++) {
		for (int j = 0; j < rght.size(); j++) {
			if (__gcd(lft[i].f, rght[j].f) != 1)
				new_node.ans += prefL[i] * prefR[j];
		}
	}

	for (auto u : B.l_r) {
		if (__gcd(new_node.l_r.back().f, u.f) < new_node.l_r.back().f)
			new_node.l_r.push_back({__gcd(new_node.l_r.back().f, u.f), u.s});
		else
			new_node.l_r.back().s += u.s;
	}
	for (auto u : A.r_l) {
		if (__gcd(new_node.r_l.back().f, u.s) < new_node.r_l.back().f)
			new_node.r_l.push_back({__gcd(new_node.r_l.back().f, u.s), u.s});
		else
			new_node.r_l.back().s += u.s;
	}
	return new_node;
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k].ans = (A[a] > 1);
		sg[k].l_r.push_back({A[a], 1});
		sg[k].r_l.push_back({A[a], 1});
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int plc, int val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		A[a] = val;
		sg[k].ans = (A[a] > 1);
		sg[k].l_r.clear();
		sg[k].r_l.clear();
		sg[k].l_r.push_back({A[a], 1});
		sg[k].r_l.push_back({A[a], 1});
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

Node query(int k, int a, int b, int q_l, int q_r) {
	if (b < q_l || a > q_r)
		return Node();
	if (q_l <= a && b <= q_r)
		return sg[k];
	return merge(query(2*k, a, (a+b)/2, q_l, q_r),
					query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int main() {
	fast
	int N, Q;
	cin >> N >> Q;

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	init(1, 1, N);

	while (Q--) {
		int type, a, b;
		cin >> type >> a >> b;
		if (type == 1)
			update(1, 1, N, a, b);
		else
			cout << query(1, 1, N, a, b).ans << "\n";
	}
}

Compilation message (stderr)

garaza.cpp: In function 'Node merge(Node, Node)':
garaza.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i < lft.size(); i++) {
      |                  ~~^~~~~~~~~~~~
garaza.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int j = 0; j < rght.size(); j++) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40