Submission #237963

#	Time	Username	Problem	Language	Result	Execution time	Memory
237963		MrRobot_28	Garaža (COCI17_garaza)	C++17	0 / 160	4050 ms	38640 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();
	int j = 0;
	for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
	{
		while(j < treeright[v * 2].size() && treeright[v * 2 + 1][i].first > treeright[v * 2][j].first)
		{
			j++;
		}
		if(treeright[v * 2 + 1][i].second == (r + l) / 2 + 1)
		{
			int ind = j;
			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]);
		}
	}
	j = 0;
	for(int i = 0; i < treeleft[v * 2].size(); i++)
	{
		while(j < treeleft[v * 2 + 1].size() && treeleft[v * 2 + 1][j].first < treeleft[v * 2][i].first)
		{
			j++;
		}
		if(treeleft[v * 2][i].second == (r + l) / 2)
		{
			int ind = j;
			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);
		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);
			}
			minl = min(ar - (r + l) / 2, minl);
			if(i != treeright[v * 2].size() - 1)
			{
				sum += 1LL * (max(al, treeright[v * 2][i + 1].second) - max(al, treeright[v * 2][i].second)) * minl;
			}
			else
			{
				sum += 1LL * ((r + l) / 2 + 1 - max(al, treeright[v * 2][i].second)) * minl;
			}
		}
		sort(treeright[v * 2].begin(), treeright[v * 2].end());
		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:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < treeright[v * 2].size() && treeright[v * 2 + 1][i].first > treeright[v * 2][j].first)
         ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:63: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:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeleft[v * 2].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:80:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < treeleft[v * 2 + 1].size() && treeleft[v * 2 + 1][j].first < treeleft[v * 2][i].first)
         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:87: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:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < treeright[v * 2].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:107: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:111: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:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:136:12: 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:141:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i != treeright[v * 2].size() - 1)
       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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