oj.uz

Submission #82359

# Submission time Handle Problem Language Result Execution time Memory
82359 2018-10-30T09:06:44 Z farukkastamonuda Garaža (COCI17_garaza) C++14
160 / 160
 1376 ms 55356 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000000000000
#define md 1000000007
#define li 100005
#define mp make_pair
#define pb push_back
#define mid (start+end)/2
using namespace std;
int n,q,A[li];
struct SEG{
	int bas,son;
	lo int res;
	int presiz,sufsiz;
	vector< pair<int,int> > pre,suf;
}tree[li*4];
SEG merge(SEG A,SEG B){
	SEG res1;
	res1.bas=A.bas;
	res1.son=B.son;
	res1.res=A.res+B.res;
	int last=-1;
	int now=(int)A.suf.size()-1;
	int totszB=0;
	while(now+1){
		pair<int,int> suf_el=A.suf[now];
		now--;
		while(last+1<(int)B.pre.size() && __gcd(suf_el.fi,B.pre[last+1].fi)>1){
			totszB+=B.pre[last+1].se;
			last++;
		}
		res1.res+=1ll*suf_el.se*totszB;
	}
	if(A.presiz==A.son-A.bas+1){
		int last=-1;
		while(last+1<(int)B.pre.size() && __gcd(A.pre.back().fi,B.pre[last+1].fi)){
			int tut=__gcd(A.pre.back().fi,B.pre[last+1].fi);
			last++;
			if(tut==A.pre.back().fi){
				A.pre.back().se+=B.pre[last].se;
			}
			else{
				A.pre.pb(mp(tut,B.pre[last].se));
			}
		}
	}
	if(B.sufsiz==B.son-B.bas+1){
		int last=-1;
		while(last+1<(int)A.suf.size() && __gcd(A.suf[last+1].fi,B.suf.back().fi)>1){
			last++;
			int tut=__gcd(A.suf[last].fi,B.suf.back().fi);
			if(tut==B.suf.back().fi){
				B.suf.back().se+=A.suf[last].se;
			}
			else{
				B.suf.pb(mp(tut,A.suf[last].se));
			}
		}
	}
	res1.pre=A.pre;
	res1.suf=B.suf;
	res1.presiz=res1.sufsiz=0;
	for(int i=0;i<(int)A.pre.size();i++) res1.presiz+=A.pre[i].se;
	for(int i=0;i<(int)B.suf.size();i++) res1.sufsiz+=B.suf[i].se;
	return res1;
}
void build(int node,int start,int end){
	if(start==end){
		tree[node].bas=start;
		tree[node].son=end;
		if(A[start]>1){
			tree[node].pre.pb(mp(A[start],1));
			tree[node].suf.pb(mp(A[start],1));
			tree[node].presiz=tree[node].sufsiz=tree[node].res=1;
		}
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree[node]=merge(tree[node*2],tree[node*2+1]);
}
SEG query(int node,int start,int end,int l,int r){
	if(start>=l && end<=r) return tree[node];
	if(mid>=l){
		if(mid+1<=r)
			return merge(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
		else
			return query(node*2,start,mid,l,r);
	}
	else{
		return query(node*2+1,mid+1,end,l,r);
	}
}
void update(int node,int start,int end,int l,int r,int val){
	if(start>end || start>r || end<l) return ;
	if(start>=l && end<=r){
		tree[node].pre.clear();
		tree[node].suf.clear();
		tree[node].res=tree[node].presiz=tree[node].sufsiz=0;
		if(val>1){
			tree[node].pre.pb(mp(val,1));
			tree[node].suf.pb(mp(val,1));
			tree[node].presiz=tree[node].sufsiz=tree[node].res=1;
		}
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=merge(tree[node*2],tree[node*2+1]);
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	build(1,1,n);
	while(q--){
		int ty,num1,num2;
		scanf("%d %d %d",&ty,&num1,&num2);
		if(ty==1){
			update(1,1,n,num1,num1,num2);
		}
		else{
			lo int yaz=query(1,1,n,num1,num2).res;
			printf("%lld\n",yaz);
		}
	}
	return 0;
}

Compilation message

garaza.cpp: In function 'int main()':
garaza.cpp:112: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:113:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&A[i]);
                        ~~~~~^~~~~~~~~~~~
garaza.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&ty,&num1,&num2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28664 KB Output is correct
2 Correct 61 ms 29076 KB Output is correct
3 Correct 65 ms 29480 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 32280 KB Output is correct
2 Correct 306 ms 34392 KB Output is correct
3 Correct 355 ms 34736 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 38932 KB Output is correct
2 Correct 713 ms 40516 KB Output is correct
3 Correct 777 ms 43128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1230 ms 51316 KB Output is correct
2 Correct 1376 ms 53516 KB Output is correct
3 Correct 1360 ms 55356 KB Output is correct