oj.uz

답안 #404475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404475 2021-05-14T13:10:48 Z penguinhacker Garaža (COCI17_garaza) C++14
160 / 160
 969 ms 40472 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct Node {
	ll cnt=0;
	vector<ar<int, 2>> p, s;
	static void extend(vector<ar<int, 2>>& a, const vector<ar<int, 2>>& b) {
		for (const ar<int, 2>& x : b) {
			int g=__gcd(a.back()[0], x[0]);
			if (g==a.back()[0])
				a.back()[1]+=x[1];
			else
				a.push_back({g, x[1]});
		}
	}
	friend Node operator+(const Node& a, const Node& b) {
		assert(a.p.size()&&b.p.size());
		Node res;
		res.p=a.p, res.s=b.s, res.cnt=a.cnt+b.cnt;
		extend(res.p, b.p), extend(res.s, a.s);
		int j=b.p.size()-1, cur=0;
		for (ar<int, 2> x : b.p)
			cur+=x[1];
		for (ar<int, 2> x : a.s) {
			while(~j&&__gcd(x[0], b.p[j][0])==1)
				cur-=b.p[j--][1];
			res.cnt+=(ll)cur*x[1];
		}
		return res;
	}
};

Node make(int x) {
	Node res;
	res.p=res.s={{x, 1}};
	res.cnt=x>1;
	return res;
}

const int mxN=1e5;
int n, q, a[mxN];
Node st[4*mxN];

void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u]=make(a[l]);
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid), bld(2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

void upd(int i, int x, int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u]=make(x);
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=st[2*u]+st[2*u+1];
}

Node qry(int ql, int qr, int u=1, int l=0, int r=n-1) {
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	if (qr<=mid)
		return qry(ql, qr, 2*u, l, mid);
	if (ql>mid)
		return qry(ql, qr, 2*u+1, mid+1, r);
	return qry(ql, qr, 2*u, l, mid)+qry(ql, qr, 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	bld();
	while(q--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t==1)
			upd(x-1, y);
		else
			cout << qry(x-1, y-1).cnt << "\n";
	}
	return 0;
}

Subtask #1
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 22400 KB Output is correct
2 Correct 28 ms 22728 KB Output is correct
3 Correct 41 ms 23144 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 25780 KB Output is correct
2 Correct 210 ms 27296 KB Output is correct
3 Correct 203 ms 26936 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 30640 KB Output is correct
2 Correct 490 ms 31288 KB Output is correct
3 Correct 491 ms 31816 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 829 ms 39512 KB Output is correct
2 Correct 969 ms 40472 KB Output is correct
3 Correct 898 ms 38308 KB Output is correct