Submission #328942

#	Time	Username	Problem	Language	Result	Execution time	Memory
328942		CodeTiger927	Garaža (COCI17_garaza)	C++14	160 / 160	1478 ms	225028 KiB

garaza

using namespace std;

#include <iostream>
#include <cstring>

#define MAXN 131072
#define MAXL 35

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

// Tournament Tree
struct node {
	int preS,sufS,preI[MAXL],preI2[MAXL],sufI[MAXL],sufI2[MAXL],index,pre[MAXL],suf[MAXL];
	long long ans;

	node(int i,long long v) {
		memset(pre,0,sizeof(pre));
		memset(suf,0,sizeof(suf));
		pre[0] = suf[0] = v;
		preI[0] = sufI[0] = preI2[0] = sufI2[0] = index = i;
		preS = sufS = 1;
		ans = 1;
		if(v == 1) ans = 0;
	}

	node() {
		memset(pre,0,sizeof(pre));
		memset(suf,0,sizeof(suf));
		pre[0] = suf[0] = 1;
		preI[0] = sufI[0] = preI2[0] = sufI2[0] = index = -1;
		preS = sufS = 1;
		ans = 0;
	}
};

node nodes[2 * MAXN];

// a is in front of b
node combine(node& a,node& b,bool debug = false) {
	node res;
	res.ans = a.ans + b.ans;
	res.preS = res.sufS = 0;
	res.index = a.index;

	if(debug) cout << "done " << b.index << " " << b.ans << " " << endl;

	// Prefix
	for(int i = 0;i < a.preS;++i) {
		res.pre[res.preS] = a.pre[i];
		res.preI[res.preS] = a.preI[i];
		res.preI2[res.preS++] = a.preI2[i];
	}

	for(int i = 0;i < b.preS;++i) {
		if(gcd(b.pre[i],res.pre[res.preS - 1]) != res.pre[res.preS - 1]) {
			res.pre[res.preS] = gcd(b.pre[i],res.pre[res.preS - 1]);
			res.preI[res.preS] = b.preI[i];
			res.preI2[res.preS++] = b.preI2[i];
		}else{
			// if(debug) cout << "hi " << b.preI2[i] << endl;
			res.preI2[res.preS - 1] = b.preI2[i];
		}
	}


	// Suffix
	for(int i = 0;i < b.sufS;++i) {
		res.suf[res.sufS] = b.suf[i];
		res.sufI[res.sufS] = b.sufI[i];
		res.sufI2[res.sufS++] = b.sufI2[i];
	}
	for(int i = 0;i < a.sufS;++i) {
		if(gcd(a.suf[i],res.suf[res.sufS - 1]) != res.suf[res.sufS - 1]) {
			res.suf[res.sufS] = gcd(a.suf[i],res.suf[res.sufS - 1]);
			res.sufI[res.sufS] = a.sufI[i];
			res.sufI2[res.sufS++] = a.sufI2[i];
		}else{
			res.sufI2[res.sufS - 1] = a.sufI2[i];
		}
	}
	// Count new interesting subarrays
	int ptr = 0;
	for(int i = b.preS - 1;i >= 0;--i) {
		while(ptr < a.sufS && gcd(b.pre[i],a.suf[ptr]) != 1) {
			ptr++;
		}
		ptr--;
		if(debug) cout << "pointer " << ptr << " " << b.index << " " << a.sufI2[ptr] << " " << (b.preI2[i] - b.preI[i] + 1) << endl;
		if(ptr >= 0) res.ans += 1ll * (b.index - a.sufI2[ptr]) * (b.preI2[i] - b.preI[i] + 1);
	}
	return res;
}

void update(int x,long long v) {
	x += MAXN;
	nodes[x] = node(x - MAXN,v);
	// cout << "hi " << x << endl;
	for(;x >>= 1;) {
		nodes[x] = combine(nodes[x << 1],nodes[x << 1 | 1]);
	}
}

long long query(int l,int r) {
	node resl(-1,1);
	node resr(-1,1);
	r++;
	for(l += MAXN,r += MAXN;l < r;l >>= 1,r >>= 1) {
		// cout << l << " " << r << endl;
		if(l & 1) {
			if(resl.index == -1) {
				resl = nodes[l++];
			}else{
				resl = combine(resl,nodes[l++],false);
			}
		}
		if(r & 1) {
			if(resr.index == -1) {
				resr = nodes[--r];
			}else{
				resr = combine(nodes[--r],resr,false);
			}
		}
	}

	if(resl.index == -1) return resr.ans;
	if(resr.index == -1) return resl.ans;
	return combine(resl,resr,false).ans;
}

int N,Q;

int main() {
	cin >> N >> Q;
	for(int i = 0;i < N;++i) {
		long long cur;
		cin >> cur;
		update(i,cur);
	}
	for(int i = N;i < MAXN;++i) {
		update(i,1);
	}
	// cout << nodes[MAXN / 2].suf[1] << " " << nodes[MAXN / 2].sufI[1] << " " << nodes[MAXN / 2].sufI2[1] << endl;
	// combine(nodes[MAXN / 2],nodes[MAXN / 2 + 1],true);
	for(int i = 0;i < Q;++i) {
		long long a,b,c;
		cin >> a >> b >> c;
		b--;
		if(a == 1) {
			update(b,c);
		}else{
			c--;
			cout << query(b,c) << endl;
		}
	}
	return 0;
}

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