Submission #237951

#	Time	Username	Problem	Language	Result	Execution time	Memory
237951		MrRobot_28	Garaža (COCI17_garaza)	C++17	0 / 160	4065 ms	40628 KiB

garaza

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector <vector <pair <int, int> > > treeleft, treeright;
vector <ll> treeans;
bool cmp(pair <int, int> a, pair <int, int> b)
{
	return a.second < b.second;
}
void update(int v, int l, int r, int ind, int val)
{
	if(l == r){
		treeleft[v].clear();
		treeright[v].clear();
		if(val == 1){
			treeans[v] = 0;
		}
		else
		{
			treeans[v] = 1;
		}
		
		int val1 = val;
		for(int j = 2; j * j <= val; j++)
		{
			if(val1 % j == 0)
			{
				treeleft[v].push_back({j, l});
				treeright[v].push_back({j, l});
			}
			while(val1 % j == 0)
			{
				val1 = val1 / j;
			}
		}
		if(val1 != 1)
		{
			treeleft[v].push_back({val1, l});
			treeright[v].push_back({val1, r});
		}
		return;
	}
	if(ind <= (r + l) / 2)
	{
		update(v * 2, l, (r + l) / 2, ind, val);
	}
	else
	{
		update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
	}
	treeleft[v].clear();
	treeright[v].clear();
	for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
	{
		if(treeright[v * 2 + 1][i].second == (r + l) / 2 + 1)
		{
			int ind = lower_bound(treeright[v * 2].begin(), treeright[v * 2].end(), make_pair(treeright[v * 2 + 1][i].first, 0)) - treeright[v * 2].begin();
			if(ind == treeright[v * 2].size() || treeright[v * 2][ind].first != treeright[v * 2 + 1][i].first)
			{
				treeright[v].push_back(treeright[v * 2 + 1][i]);
			}
			else
			{
				treeright[v].push_back(treeright[v * 2][ind]);
			}
		}
		else
		{
			treeright[v].push_back(treeright[v * 2 + 1][i]);
		}
	}
	for(int i = 0; i < treeleft[v * 2].size(); i++)
	{
		if(treeleft[v * 2][i].second == (r + l) / 2)
		{
			int ind = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(treeleft[v * 2][i].first, 0)) - treeleft[v * 2 + 1].begin();
			if(ind == treeleft[v * 2+ 1].size() || treeleft[v * 2 + 1][ind].first != treeleft[v * 2][i].first)
			{
				treeleft[v].push_back(treeleft[v * 2][i]);
			}
			else
			{
				treeleft[v].push_back(treeleft[v * 2 + 1][ind]);
			}
		}
		else
		{
			treeleft[v].push_back(treeleft[v * 2][i]);
		}
	}
	treeans[v] = treeans[v * 2] + treeans[v * 2 + 1];
	sort(treeright[v * 2].begin(), treeright[v * 2].end(), cmp);
	int minl = 0;
	for(int i = 0; i < treeright[v * 2].size(); i++)
	{
		int iter = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(treeright[v * 2][i].first, 0)) - treeleft[v * 2 + 1].begin();
		if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == treeright[v * 2][i].first)
		{
			minl = max(minl, treeleft[v * 2 + 1][iter].second - (r + l) / 2);
		}
		if(i != treeright[v * 2].size() - 1)
		{
			treeans[v] += 1LL * (treeright[v * 2][i + 1].second - treeright[v * 2][i].second) * minl;
		}
		else
		{
			treeans[v] += 1LL * ((r + l) / 2 + 1 - treeright[v * 2][i].second) * minl;
		}
	}
	sort(treeright[v * 2].begin(), treeright[v * 2].end());
}
ll ans(int v, int l, int r, int al, int ar)
{
	if(l >= al && r <= ar)
	{
		return treeans[v];
	}
	else if(l <= ar && r >=  al)
	{
		ll sum = ans(v * 2, l, (r + l) / 2, al, ar) + ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar);
		vector <pair <int, int> > vec;
		for(int i = 0; i < treeright[v * 2].size(); i++)
		{
			vec.push_back({treeright[v * 2][i].first, max(al, treeright[v * 2][i].second)});
		}
		sort(vec.begin(), vec.end(), cmp);
		int minl = 0;
		for(int i = 0; i < vec.size(); i++)
		{
			int iter = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(vec[i].first, 0)) - treeleft[v * 2 + 1].begin();
			if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == vec[i].first)
			{
				minl = max(minl, treeleft[v * 2 + 1][iter].second - (r + l) / 2);
			}
			minl = min(minl, ar - (r + l) / 2);
			if(i != vec.size() - 1)
			{
				sum  += 1LL * (vec[i + 1].second - vec[i].second) * minl;
			}
			else
			{
				sum += 1LL * ((r + l) / 2 + 1 - vec[i].second) * minl;
			}
		}
		return sum;
	}
	else
	{
		return 0;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, q;
	cin >> n >> q;
	treeleft.resize(4 * n);
	treeright.resize(4 * n);
	treeans.resize(4 * n);
	vector <int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		update(1, 0, n - 1, i, a[i]);
	}
	while(q--)
	{
		int type;
		cin >> type;
		if(type == 1)
		{
			int x, v;
			cin >> x >> v;
			x--;
			update(1, 0, n - 1, x, v);
		}
		else
		{
			int l, r;
			cin >> l >> r;
			l--;
			r--;
			cout << ans(1, 0, n - 1, l, r) << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

garaza.cpp: In function 'void update(int, int, int, int, int)':
garaza.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind == treeright[v * 2].size() || treeright[v * 2][ind].first != treeright[v * 2 + 1][i].first)
       ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeleft[v * 2].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:77:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind == treeleft[v * 2+ 1].size() || treeleft[v * 2 + 1][ind].first != treeleft[v * 2][i].first)
       ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeright[v * 2].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == treeright[v * 2][i].first)
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:101:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i != treeright[v * 2].size() - 1)
      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'long long int ans(int, int, int, int, int)':
garaza.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < vec.size(); i++)
                  ~~^~~~~~~~~~~~
garaza.cpp:131:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == vec[i].first)
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:136:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i != vec.size() - 1)
       ~~^~~~~~~~~~~~~~~~~

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