Submission #156896

#	Time	Username	Problem	Language	Result	Execution time	Memory
156896		IvanC	Garaža (COCI17_garaza)	C++17	160 / 160	1016 ms	34048 KiB

garaza

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;

const int MAXN = 1e5 + 10;
const int SEG_SZ = 262148;

inline int gcd(int a, int b){
	if(b == 0) return a;
	if(a < b) swap(a, b);
	return gcd(b, a % b);
}

struct node{

	int gcd_all;
	vii pref, suf;
	ll tot;

	node(){
		tot = 0;
		gcd_all = 0;
	}

	node operator*(const node& other)const{

		node ans;

		ans.pref = pref;
		ans.suf = other.suf;
		ans.tot = tot + other.tot;
		ans.gcd_all = gcd(gcd_all, other.gcd_all);

		/*
		printf("##############\n");
		printf("Merging: %lld + %lld\n", tot, other.tot);
		printf("Pref Left:");
		for(ii davez: pref){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		printf("Suf Left:");
		for(ii davez: suf){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		printf("Pref Right:");
		for(ii davez: other.pref){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		printf("Suf Right:");
		for(ii davez: other.suf){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		*/

		for(int i = 0; i < other.pref.size(); i++){

			int cand = gcd(gcd_all, other.pref[i].first);
			if(cand == 1) break;
			if(!ans.pref.empty() && ans.pref.back().first == cand){
				ans.pref.back().second += other.pref[i].second;
			}
			else{
				ans.pref.push_back(ii(cand, other.pref[i].second));
			}

		}

		for(int i = 0; i < suf.size(); i++){
			int cand = gcd(other.gcd_all, suf[i].first);
			if(cand == 1) break;
			ii novo = ii(cand, suf[i].second);
			if(!ans.suf.empty() && ans.suf.back().first == cand){
				ans.suf.back().second += suf[i].second;
			}
			else{
				ans.suf.push_back(novo);
			}
		}

		int j = 0, gcd_sum = 0;
		for(int i = suf.size() - 1; i >= 0; i--){
			while(j < other.pref.size() && gcd(suf[i].first, other.pref[j].first) > 1){
				gcd_sum += other.pref[j].second;
				j++;
			}
			ans.tot += 1LL*gcd_sum*suf[i].second;
			//printf("DELTA %d %lld\n", i, 1LL*gcd_sum*suf[i].second);
		}

		/*
		printf("Ans Pref:");
		for(ii davez: ans.pref){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		printf("Ans Suf:");
		for(ii davez: ans.suf){
			printf(" (%d, %d)", davez.first, davez.second);
		}
		printf("\n");
		printf("##############\n");
		*/

		return ans;

	}

};

node seg[SEG_SZ];
int arr[MAXN], N, Q;

void build(int pos, int left, int right){

	if(left == right){
		seg[pos].pref.clear();
		seg[pos].suf.clear();
		seg[pos].gcd_all = arr[left];
		if(arr[left] != 1){
			seg[pos].tot = 1;
			seg[pos].pref.push_back(ii(arr[left], 1));
			seg[pos].suf.push_back(ii(arr[left], 1));
		}
		else{
			seg[pos].tot = 0;
		}
		return;
	}

	int mid = (left+right)/2;

	build(2*pos, left, mid);
	build(2*pos+1, mid + 1, right);

	seg[pos] = seg[2*pos]*seg[2*pos+1];

	//printf("POS (%d, %d, %d) = %lld\n", pos, left, right, seg[pos].gcd_all);

}

void update(int pos, int left, int right, int x){

	if(left == right){
		seg[pos].pref.clear();
		seg[pos].suf.clear();
		seg[pos].gcd_all = arr[left];
		if(arr[left] != 1){
			seg[pos].tot = 1;
			seg[pos].pref.push_back(ii(arr[left], 1));
			seg[pos].suf.push_back(ii(arr[left], 1));
		}
		else{
			seg[pos].tot = 0;
		}
		return;
	}

	int mid = (left+right)/2;

	if(x <= mid) update(2*pos, left, mid, x);
	else update(2*pos+1, mid + 1, right, x);

	seg[pos] = seg[2*pos]*seg[2*pos+1];

}

node query(int pos, int left, int right, int i, int j){

	if(left >= i && right <= j){
		return seg[pos];
	}

	int mid = (left+right)/2;

	if(j <= mid) return query(2*pos, left, mid, i, j);
	else if(i >= mid + 1) return query(2*pos+1, mid + 1, right, i, j);
	else return query(2*pos, left, mid, i, j) * query(2*pos+1, mid + 1, right, i, j);

}

int main(){

	scanf("%d %d", &N, &Q);
	for(int i = 1; i <= N; i++){
		scanf("%d", &arr[i]);
	}

	build(1, 1, N);

	for(int q = 1; q <= Q; q++){
		
		int op, l, r;
		scanf("%d %d %d", &op, &l, &r);

		if(op == 1){
			arr[l] = r;
			update(1, 1, N, l);
		}
		else{
			node result = query(1, 1, N, l, r);
			printf("%lld\n", result.tot);
		}

	}

	return 0;

}

Compilation message (stderr)

garaza.cpp: In member function 'node node::operator*(const node&) const':
garaza.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < other.pref.size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~
garaza.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < suf.size(); i++){
                  ~~^~~~~~~~~~~~
garaza.cpp:89:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j < other.pref.size() && gcd(suf[i].first, other.pref[j].first) > 1){
          ~~^~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
garaza.cpp:192:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
garaza.cpp:200:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &op, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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