Submission #36533

#	Time	Username	Problem	Language	Result	Execution time	Memory
36533		szawinis	Garaža (COCI17_garaza)	C++14	160 / 160	1753 ms	37736 KiB

garaza

#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
using ll = long long;
const int N = 1 << 17;

int n, q, a[N], lb[2*N], rb[2*N];
ll t[2*N];
vector<pair<int,int> > pref[2*N], suff[2*N];

void build(int pos, int l, int r) {
	lb[pos] = l; rb[pos] = r;
	if(l == r) {
		pref[pos] = suff[pos] = {{a[l], l}};
		t[pos] = a[l] > 1;
		return;
	}
	int mid = l+r >> 1;
	build(pos<<1, l, mid);
	build(pos<<1|1, mid+1, r);
	// init t
	t[pos] = t[pos<<1] + t[pos<<1|1];
	// cout << pos << ' ' << l << ' ' << r << ' ' << t[pos] << endl;
	for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
		while(j >= 0 && __gcd(suff[pos<<1][j].fs, pref[pos<<1|1][i].fs) == 1) --j;
		if(j < 0) continue;
		ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
		res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
		t[pos] += res;
		// cout << res << endl;
	}
	// init pref
	pref[pos] = pref[pos<<1];
	for(int i = 0; i < pref[pos<<1|1].size(); i++) {
		int new_gcd = __gcd(pref[pos<<1|1][i].fs, pref[pos<<1].back().fs);
		if(new_gcd != pref[pos].back().fs)
			pref[pos].emplace_back(new_gcd, pref[pos<<1|1][i].sc);
	}
	// for(int i = 0; i < pref[pos].size(); i++) cout << pref[pos][i].fs << ' ' << pref[pos][i].sc << endl;
	// init suff
	suff[pos] = suff[pos<<1|1];
	for(int i = 0; i < suff[pos<<1].size(); i++) {
		int new_gcd = __gcd(suff[pos<<1][i].fs, suff[pos<<1|1].back().fs);
		if(new_gcd != suff[pos].back().fs)
			suff[pos].emplace_back(new_gcd, suff[pos<<1][i].sc);
	}
	// cout << endl;
	// for(int i = 0; i < suff[pos].size(); i++) cout << suff[pos][i].fs << ' ' << suff[pos][i].sc << endl;
	// cout << pos << ' ' << l << ' ' << r << ' ' << t[pos] << endl;
	// cout << endl;
}

void update(int pos, int l, int r, int idx, int v) {
	if(l == r) {
		pref[pos] = suff[pos] = {{v, l}};
		t[pos] = v > 1;
		return;
	}
	int mid = l+r >> 1;
	if(idx <= mid) update(pos<<1, l, mid, idx, v);
	else update(pos<<1|1, mid+1, r, idx, v);
	// update t
	t[pos] = t[pos<<1] + t[pos<<1|1];
	for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
		while(j >= 0 && __gcd(suff[pos<<1][j].fs, pref[pos<<1|1][i].fs) == 1) --j;
		if(j < 0) continue;
		ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
		res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
		t[pos] += res;
	}
	// update pref
	pref[pos] = pref[pos<<1];
	for(int i = 0; i < pref[pos<<1|1].size(); i++) {
		int new_gcd = __gcd(pref[pos<<1|1][i].fs, pref[pos<<1].back().fs);
		if(new_gcd != pref[pos].back().fs)
			pref[pos].emplace_back(new_gcd, pref[pos<<1|1][i].sc);
	}
	// update suff
	suff[pos] = suff[pos<<1|1];
	for(int i = 0; i < suff[pos<<1].size(); i++) {
		int new_gcd = __gcd(suff[pos<<1][i].fs, suff[pos<<1|1].back().fs);
		if(new_gcd != suff[pos].back().fs)
			suff[pos].emplace_back(new_gcd, suff[pos<<1][i].sc);
	}
}

ll query(int l, int r) {
	int tmpl = l, tmpr = r;
	ll ret = 0;
	vector<int> segs;
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) {
			ret += t[l];
			segs.push_back(l);
			++l;
		}
		if(r & 1) {
			--r;
			ret += t[r];
			segs.push_back(r);
		}
	}
	l = tmpl, r = tmpr;
	sort(segs.begin(), segs.end(), [] (int i, int j) { return lb[i] < lb[j]; });
	vector<pair<int,int> > loc_suff;
	for(int pos: segs) {
		for(int i = 0, j = loc_suff.size()-1; i < pref[pos].size(); i++) {
			while(j >= 0 && __gcd(loc_suff[j].fs, pref[pos][i].fs) == 1) --j;
			if(j < 0) continue;
			ll res = lb[pos]-1 - (j < loc_suff.size()-1 ? loc_suff[j+1].sc : l-1);
			res *= (i < pref[pos].size()-1 ? pref[pos][i+1].sc : rb[pos]+1) - pref[pos][i].sc;
			ret += res;
		}
		vector<pair<int,int> > tmp = suff[pos];
		for(int i = 0; i < loc_suff.size(); i++) {
			int new_gcd = __gcd(loc_suff[i].fs, suff[pos].back().fs);
			if(new_gcd != tmp.back().fs)
				tmp.emplace_back(new_gcd, loc_suff[i].sc);
		}
		loc_suff = tmp;
	}
	return ret;
}

int main() {
	scanf("%d %d", &n, &q);
	fill(a, a+N, 1);
	for(int i = 0; i < n; i++) scanf("%d", a+i);
	build(1, 0, N-1);
	while(q--) {
		int type; cin >> type;
		if(type == 1) {
			int idx, v; scanf("%d %d", &idx, &v); --idx;
			update(1, 0, N-1, idx, v);
		} else {
			int l, r; scanf("%d %d", &l, &r); --l; --r;
			printf("%lld\n", query(l, r));
		}
	}
}

Compilation message (stderr)

garaza.cpp: In function 'void build(int, int, int)':
garaza.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
garaza.cpp:25:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
                                              ^
garaza.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
                     ^
garaza.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
             ^
garaza.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pref[pos<<1|1].size(); i++) {
                   ^
garaza.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < suff[pos<<1].size(); i++) {
                   ^
garaza.cpp: In function 'void update(int, int, int, int, int)':
garaza.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
garaza.cpp:65:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, j = suff[pos<<1].size()-1; i < pref[pos<<1|1].size(); i++) {
                                              ^
garaza.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   ll res = mid - (j < suff[pos<<1].size()-1 ? suff[pos<<1][j+1].sc : l-1);
                     ^
garaza.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   res *= (i < pref[pos<<1|1].size()-1 ? pref[pos<<1|1][i+1].sc : r+1) - pref[pos<<1|1][i].sc;
             ^
garaza.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pref[pos<<1|1].size(); i++) {
                   ^
garaza.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < suff[pos<<1].size(); i++) {
                   ^
garaza.cpp: In function 'll query(int, int)':
garaza.cpp:108:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0, j = loc_suff.size()-1; i < pref[pos].size(); i++) {
                                           ^
garaza.cpp:111:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    ll res = lb[pos]-1 - (j < loc_suff.size()-1 ? loc_suff[j+1].sc : l-1);
                            ^
garaza.cpp:112:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    res *= (i < pref[pos].size()-1 ? pref[pos][i+1].sc : rb[pos]+1) - pref[pos][i].sc;
              ^
garaza.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < loc_suff.size(); i++) {
                    ^
garaza.cpp: In function 'int main()':
garaza.cpp:127:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
                        ^
garaza.cpp:129:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < n; i++) scanf("%d", a+i);
                                             ^
garaza.cpp:134:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int idx, v; scanf("%d %d", &idx, &v); --idx;
                                        ^
garaza.cpp:137:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l, r; scanf("%d %d", &l, &r); --l; --r;
                                    ^

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