oj.uz

Submission #42249

# Submission time Handle Problem Language Result Execution time Memory
42249 2018-02-24T09:21:43 Z milmillin Garaža (COCI17_garaza) C++14
80 / 160
 4000 ms 262144 KB 
#include <cstdio>
#include <vector>

using namespace std;

int tbl[100100];

struct p {
	int val,cnt;
};

struct node {
	~node() {
		if (l!=NULL) delete l;
		if (r!=NULL) delete r;
	}
	int cnt;
	vector<p> pre,suf;
	node *l, *r;
	void combine();
	node(node* a) {
		cnt=a->cnt;
		pre=a->pre;
		suf=a->suf;
	}

	node() {

	}
};

int gcd(int a,int b) {
	return (b==0)?a:gcd(b,a%b);
}

void node::combine() {
	if (l==NULL||r==NULL) {
		node* tmp;
		if (l==NULL) tmp=r;
		else tmp=l;
		pre = tmp->pre;
		suf = tmp->suf;
		cnt = tmp->cnt;
		return;
	}
	pre.clear();
	suf.clear();
	pre.insert(pre.begin(),l->pre.begin(),l->pre.end());
	suf.insert(suf.begin(),r->suf.begin(),r->suf.end());
	int gl=l->pre.back().val;
	int gr=r->suf.back().val;
	int xx;
	for (auto i:r->pre) {
		xx=gcd(i.val,gl);
		if (xx==pre.back().val) pre.back().cnt+=i.cnt;
		else pre.push_back(p{xx,i.cnt});
	}
	for (auto i:l->suf) {
		xx=gcd(i.val,gr);
		if (xx==suf.back().val) suf.back().cnt+=i.cnt;
		else suf.push_back(p{xx,i.cnt});
	}

	cnt=l->cnt+r->cnt;
	int cur=0;
	int c=0;
	for (int i=l->suf.size()-1;i>=0;i--) {
		auto &xx = l->suf[i];
		while (cur<r->pre.size()&&gcd(xx.val,r->pre[cur].val)>1) {
			c+=r->pre[cur].cnt;
			cur++;
		}
		if (cur>0) {
			cnt+=xx.cnt*c;
			//printf("-- %d %d\n",xx.cnt,c);
		}
	}
}

node* build(int l,int r) {
	node *tmp = new node();
	if (l+1==r) {
		tmp->pre.push_back(p{tbl[l],1});
		tmp->suf.push_back(p{tbl[l],1});
		tmp->l=NULL;
		tmp->r=NULL;
		tmp->cnt=(tbl[l]==1)?0:1;
		//printf("%d %d %d\n",l,r,tmp->cnt);
		return tmp;
	}
	int m = (l+r)>>1;
	tmp->l=build(l,m);
	tmp->r=build(m,r);
	tmp->combine();
	//printf("%d %d %d\n",l,r,tmp->cnt);
	return tmp;
}

void update(node* tmp,int l,int r,int k) {
	if (k<l||k>=r) return;
	if (l+1==r) {
		tmp->pre.clear();
		tmp->suf.clear();
		tmp->pre.push_back(p{tbl[k],1});
		tmp->suf.push_back(p{tbl[k],1});
		tmp->cnt=(tbl[k]==1)?0:1;
		return;
	}
	int m = (l+r)>>1;
	if (k<m) update(tmp->l,l,m,k);
	else update(tmp->r,m,r,k);
	tmp->combine();
}

node* query(node* now,int l,int r,int ll,int rr) {
	if (rr<=l||ll>=r) return NULL;
	if (ll<=l&&rr>=r) return new node(now);
	node* tmp = new node();
	int m = (l+r) >> 1;
	tmp->l=query(now->l,l,m,ll,rr);
	tmp->r=query(now->r,m,r,ll,rr);
	tmp->combine();
	//printf("--- %d %d %d %d %d\n",l,r,ll,rr,tmp->cnt);
	return tmp;
}

int main () {
	int n,q;
	scanf("%d%d",&n,&q);
	for (int i=0;i<n;i++) {
		scanf("%d",&tbl[i]);
	}
	node* root = build(0,n);
	//printf("yay\n");
	int a,b,c;
	while (q--) {
		scanf("%d%d%d",&a,&b,&c);
		if (a==1) {
			b--;
			tbl[b]=c;
			update(root,0,n,b);
		} else {
			b--;
			auto q = query(root,0,n,b,c);
			printf("%d\n",q->cnt);
		}	
	}
	delete root;
	return 0;
}

Compilation message

garaza.cpp: In member function 'void node::combine()':
garaza.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (cur<r->pre.size()&&gcd(xx.val,r->pre[cur].val)>1) {
             ^
garaza.cpp: In function 'int main()':
garaza.cpp:129:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
garaza.cpp:131:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&tbl[i]);
                      ^
garaza.cpp:137:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
                           ^

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2296 KB Output is correct
2 Correct 28 ms 12352 KB Output is correct
3 Correct 47 ms 14620 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 43532 KB Output is correct
2 Correct 469 ms 193196 KB Output is correct
3 Correct 361 ms 193196 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 199908 KB Output is correct
2 Execution timed out 4108 ms 262144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4123 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -