Submission #237979

#	Time	Username	Problem	Language	Result	Execution time	Memory
237979		MrRobot_28	Garaža (COCI17_garaza)	C++17	0 / 160	4078 ms	29164 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)
	{
		if(val == 1)
		{
			treeans[v] = 0;
		}
		else
		{
			treeans[v] = 1;
		}
		treeleft[v].clear();
		treeright[v].clear();
		treeleft[v].push_back({l, val});
		treeright[v].push_back({r, val});
		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 len1 = treeleft[v * 2].size();
	if(treeleft[v * 2 + 1].size() > 0 && len1 > 0 && treeleft[v * 2][len1 - 1].first == (r + l) / 2 && __gcd(treeleft[v * 2][len1 - 1].second, treeleft[v * 2+ 1][0].second) == treeleft[v * 2][len1 - 1].second)
	{
		int a = treeleft[v * 2].back().second;
		for(int i = 0; i < treeleft[v * 2].size() - 1; i++)
		{
			treeleft[v].push_back(treeleft[v * 2][i]);
		}
		for(int i = 0; i < treeleft[v * 2 + 1].size(); i++)
		{
			int d = __gcd(a, treeleft[v * 2 + 1][i].second);
			treeleft[v].push_back({treeleft[v * 2 + 1][i].first, d});
		}
	}
	else if(len1 > 0 && treeleft[v * 2].size() > 0 && treeleft[v * 2].back().first == (r + l) / 2)
	{
		int a = treeleft[v * 2].back().second;
		for(int i = 0; i < treeleft[v * 2].size(); i++){
			treeleft[v].push_back(treeleft[v * 2][i]);
		}
		for(int i = 0; i< treeleft[v * 2 + 1].size(); i++)
		{
			int d = __gcd(a, treeleft[v * 2 + 1][i].second);
			if(d == 1){
				break;
			}
			treeleft[v].push_back({treeleft[v * 2 + 1][i].first, d});
		}
	}
	else
	{
		for(int i = 0; i < treeleft[v * 2].size(); i++)
		{
			treeleft[v].push_back(treeleft[v * 2][i]);
		}
	}
	int len2 = treeright[v * 2 + 1].size();
	if(len2 > 0 && treeright[v * 2].size() > 0 && treeright[v * 2 + 1].back().first == (r + l) / 2 + 1 && __gcd(treeright[v * 2 + 1].back().second, treeright[v * 2][0].second) == treeright[v * 2 + 1].back().second)
	{
		int a = treeleft[v * 2 + 1].back().second;
		for(int i = 0; i < treeright[v * 2 + 1].size() - 1; i ++)
		{
			treeright[v].push_back(treeright[v * 2 + 1][i]);
		}
		for(int i = 0; i < treeright[v * 2].size(); i++)
		{
			int d = __gcd(a, treeright[v * 2][i].second);
			treeright[v].push_back({treeright[v * 2][i].first, d});
		}
	}
	else if(len2 > 0 && treeright[v * 2].size() > 0 && treeright[v * 2 + 1].back().first == (r + l) /  2 + 1)
	{
		int a = treeright[v * 2 + 1].back().second;
		for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
		{
			treeright[v].push_back(treeright[v * 2 + 1][i]);
		}
		for(int i = 0; i < treeright[v * 2].size(); i++)
		{
			int d = __gcd(a, treeright[v * 2][i].second);
			if(d == 1)
			{
				break;
			}
			treeright[v].push_back({treeright[v * 2][i].first, d});
		}
	}
	else
	{
		for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
		{
			treeright[v].push_back(treeright[v * 2 + 1][i]);
		}
	}
	treeans[v] = treeans[v * 2] + treeans[v * 2 + 1];
	int j = -1;
		for(int i = 0; i < treeright[v * 2].size(); i++)
		{
			while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
			{
				j++;
			}
			if(j != -1)
			{
				if(i == treeright[v * 2].size() - 1)
				{
					treeans[v]+= ((r + l) / 2 + 1 -  treeright[v * 2][i].first) * (treeleft[v * 2 + 1][j].first - (r + l) / 2);
				}
				else
				{
					treeans[v] += (treeright[v * 2][i + 1].first - treeright[v * 2][i].first) * (treeleft[v * 2 + 1][j].first - (r + l ) / 2);
				}
			}
		}
}
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);
		int j = -1;
		for(int i = 0; i < treeright[v * 2].size(); i++)
		{
			while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
			{
				j++;
			}
			if(j != -1)
			{
				if(i == treeright[v * 2].size() - 1)
				{
					sum += ((r + l) / 2 + 1 - max(al, treeright[v * 2][i].first)) * (min(ar, treeleft[v * 2 + 1][j].first) - (r + l) / 2);
				}
				else
				{
					sum += (max(al, treeright[v * 2][i + 1].first) - max(al, treeright[v * 2][i].first)) * (min(ar, treeleft[v * 2 + 1][j].first) - (r + l ) / 2);
				}
			}
		}
		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:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeleft[v * 2].size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeleft[v * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeleft[v * 2].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i< treeleft[v * 2 + 1].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeleft[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2 + 1].size() - 1; i ++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:116:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:122:10: 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:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < treeright[v * 2].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:151:10: 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