Submission #881169

#	Time	Username	Problem	Language	Result	Execution time	Memory
881169		serifefedartar	Garaža (COCI17_garaza)	C++17	120 / 160	1098 ms	42156 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;
	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 += lft[i].s * rght[j].s;
		}
	}

	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.f) < new_node.r_l.back().f)
			new_node.r_l.push_back({__gcd(new_node.r_l.back().f, u.f), u.s});
		else
			new_node.r_l.back().s += u.s;
	}

	reverse(new_node.l_r.begin(), new_node.l_r.end());
	new_node.l_r.pop_back();
	reverse(new_node.l_r.begin(), new_node.l_r.end());
	reverse(new_node.r_l.begin(), new_node.r_l.end());
	new_node.r_l.pop_back();
	reverse(new_node.r_l.begin(), new_node.r_l.end());
	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:32: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]
   32 |  for (int i = 0; i < lft.size(); i++) {
      |                  ~~^~~~~~~~~~~~
garaza.cpp:33: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]
   33 |   for (int j = 0; j < rght.size(); j++) {
      |                   ~~^~~~~~~~~~~~~

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