Submission #485294

#	Time	Username	Problem	Language	Result	Execution time	Memory
485294		errorgorn	Garaža (COCI17_garaza)	C++17	160 / 160	953 ms	37340 KiB

garaza

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define ll long long

int n,q;
int arr[100005];

struct range{
	vector<ii> l,r; //maintain running gcd from left and right
	//<val, length>
	
	ll init(int i){
		l.clear(),r.clear();
		l.push_back(ii(i,1));
		r.push_back(ii(i,1));
		
		return i!=1;
	}
	
	ll merge(range i, range j){ //i hope deep copying happens
		ll res=0;
		
		for (auto &it:i.r){
			for (auto &it2:j.l){
				if (__gcd(it.first,it2.first)!=1) res+=(ll)it.second*it2.second;
			}
		}
		
		l.clear(),r.clear();
		l.insert(l.begin(),i.l.begin(),i.l.end());
		for (auto &it:j.l){
			if (__gcd(l.back().first,it.first)==l.back().first) l.back().second+=it.second;
			else l.push_back(ii(__gcd(l.back().first,it.first),it.second));
		}
		
		r.insert(r.begin(),j.r.begin(),j.r.end());
		for (auto &it:i.r){
			if (__gcd(r.back().first,it.first)==r.back().first) r.back().second+=it.second;
			else r.push_back(ii(__gcd(r.back().first,it.first),it.second));
		}
		
		return res;
	}
} temp; //we use temp for dirty work

ll ans; //this is to get answers

struct node{
	int s,e,m;
	ll val; //number of good interval here
	range dat; //info about this range
	node *l, *r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			
			val=dat.merge(l->dat,r->dat);
			val+=l->val+r->val;
		}
		else{
			val=dat.init(arr[s]);
		}

		
		//~ printf("segment: %d %d\n",s,e);
		//~ for (auto &it:dat.l) printf("%d-%d ",it.first,it.second);
		//~ printf("\n");
		//~ for (auto &it:dat.r) printf("%d-%d ",it.first,it.second);
		//~ printf("\n\n");
	}
	
	void update(int i){
		if (s==e) val=dat.init(arr[s]);
		else {
			if (i<=m) l->update(i);
			else r->update(i);
			
			val=dat.merge(l->dat,r->dat);
			val+=l->val+r->val;
		}
	}
	
	void query(int i,int j){
		if (s==i && e==j){
			ans+=val;
			ans+=temp.merge(temp,dat);
		}
		else{
			if (j<=m) l->query(i,j);
			else if (m<i) r->query(i,j);
			else l->query(i,m),r->query(m+1,j);
		}
	}
}*root;

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&q);
	for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
	
	root=new node(1,n);
	
	int a,b,c;
	while (q--){
		scanf("%d%d%d",&a,&b,&c);
		if (a==1){ //update
			arr[b]=c;
			root->update(b);
		}
		else{ //query
			ans=0;
			temp.init(1);
			root->query(b,c);
			
			printf("%lld\n",ans);
		}
	}
}

Compilation message (stderr)

garaza.cpp: In constructor 'node::node(int, int)':
garaza.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
garaza.cpp: In function 'int main()':
garaza.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
garaza.cpp:104:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  for (int x=1;x<=n;x++) scanf("%d",&arr[x]);
      |                         ~~~~~^~~~~~~~~~~~~~
garaza.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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