Submission #40137

#	Time	Username	Problem	Language	Result	Execution time	Memory
40137		alanm	Garaža (COCI17_garaza)	C++14	120 / 160	1708 ms	18696 KiB

garaza

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <math.h>
#include <stack>
#include <limits.h>
#include <queue>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>
#include <deque>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#include <fstream>
#define REP(i,N)for(int i=0;i<(N);i++)
#define FOR(i,a,b)for(int i=(a);i<=(b);i++)
#define FORD(i,a,b)for(int i=a;i>=(b);i--)
#define ll int
#define vi vector<ll>
#define vii vector<pair<ll,ll> >
#define vvi vector<vector<ll> >
#define vb vector<bool>
#define pii pair<ll,ll>
#define ALL(x) (x).begin(), (x).end()
#define SZ(a)((ll)(a).size())
#define CHECK_BIT(n,x)((bool)((n)&(((ll)1)<<(x))))
#define pow2(x) ((x)*(x))
#define VELA 2000000009999999999ll
#define X first
#define Y second
using namespace std;

ll gcd(ll a, ll b) {
	while (b) a %= b, swap(a, b);
	return a;
}

struct Range {
	vii pre, suf;
	long long count;
};
vii Add(vii a, vii b) {
	vii res=a;
	res.insert(res.end(),ALL(b));
	FOR(i,1, SZ(res)-1) {
		res[i].second = gcd(res[i].second,res[i-1].second);
	}
	vii zip(1,res[0]);
	FOR(i,1 ,SZ(res)-1) {
		if (zip.back().second == res[i].second) {
			zip[SZ(zip) - 1].first = zip[SZ(zip) - 1].first + res[i].first;
		}
		else {
			zip.push_back(res[i]);
		}
	}
	return zip;
}

vii GetR(vii a) {
	vii res = a;
	reverse(ALL(res));
	return res;
}

Range Union(Range a, Range b) {
	Range res;
	res.pre = Add(a.pre, b.pre);
	res.suf = GetR(Add(GetR(b.suf), GetR(a.suf)));
	res.count = a.count + b.count;
	ll r=0;
	ll rSz=0;
	REP(l, SZ(a.suf)) {
		while (r < SZ(b.pre) && gcd(b.pre[r].second, a.suf[l].second)>1) {
			rSz += b.pre[r].first;
			r++;
		}
		res.count += (ll)(a.suf[l].first)*(ll)rSz;
	}
	return res;
}

struct Intervalac {
	vector<Range> tree;
	ll nListy = 2;
	Intervalac(ll n, vi pole) {
		while (nListy < n + 2) {
			nListy *= 2;
		}
		tree = vector<Range>(2 * nListy, Range{ vii(1,{1,1}),vii(1,{1,1}),0 });
		FOR(i, nListy + 1, nListy + SZ(pole)) {
			ll v = pole[i-nListy-1], c = v > 1 ? 1 : 0;
			tree[i] = Range{ vii(1,{1,v}),vii(1,{1,v}),c };
		}
		FORD(i, nListy - 1, 1)tree[i] = Union(tree[i * 2], tree[i * 2 + 1]);
	}
	void Change(ll k, ll val) {
		k += nListy + 1;
		tree[k] = Range{ vii(1,{1,val}),vii(1,{1,val}),val>1?1:0};
		k /= 2;
		while (k > 0) {
			tree[k] = Union(tree[k*2ll],tree[k*2ll+1ll]);
			k /= 2;
		}
	}
	long long Get(ll l, ll r) {
		l += nListy;
		r += nListy + 2;
		Range resl,resR= Range{ vii(1, { 1,1 }), vii(1, {1,1}),0 };
		resl = resR;

		while (l / 2 != r / 2) {
			if (l % 2 == 0)resl = Union(resl, tree[l + 1]);
			if (r % 2 == 1)resR = Union(tree[r-1],resR);
			l /= 2;
			r /= 2;
		}
		Range res = Union(resl,resR);
		return res.count;
	}
};

int main() {
	cin.sync_with_stdio(0);
	ll n,q;
	cin >> n>>q;
	
	vi pole;
	REP(i, n) {
		ll val;
		cin >> val;

		//val = (rand() % 20) + 1;
		//cout << val << " ";
		pole.push_back(val);
	}
	Intervalac is(n,pole);
	//cout << "\n";

	while (q--) {
		ll typ;
		cin >> typ;

		//typ = (rand() % 2) + 1;

		if (typ == 1) {
			ll index, val;
			cin >> index>>val;
			index--;

			/*index = rand() % n;
			val = (rand() % 20) + 1;
			pole[index] = val;
			cout << index+1 << " " << val+1 << "\n";*/

			is.Change(index, val);
		}
		else {
			ll l, r;
			cin >> l >> r;
			l--;
			r--;

			/*l = rand() % n;
			r = rand() % n;
			if (l > r)swap(l, r);
			cout << l + 1 << " " << r + 1 << "\n";

			ll pocet = 0;
			FOR(i, l, r) {
				FOR(j, i, r) {
					ll curr_gcd = pole[i];
					FOR(k, i, j) {
						curr_gcd = gcd(curr_gcd, pole[k]);
					}
					if (curr_gcd > 1)pocet++;
				}
			}*/
			
			long long res = is.Get(l, r);
			//if (res != pocet)
			//	cout << pocet<<"\n";
			cout << res << "\n";
		}
	}
	return 0;
}

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