oj.uz

Submission #80395

# Submission time Handle Problem Language Result Execution time Memory
80395 2018-10-20T13:28:45 Z mbvdk Garaža (COCI17_garaza) C++14
160 / 160
 2170 ms 47440 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 100000;
int a[N+5];

struct node{
	vector<pii> l, r;
	ll ans;
};
node st[4*N+5];

node merge(node a, node b){
	node res;
	int g = 0, pv = 0, cnt = 0;
	for(int i=0;i<a.l.size();i++){
		g = __gcd(g, a.l[i].first);
		cnt = a.l[i].second;
		if(g != pv) res.l.emplace_back(pii(g, cnt));
		else res.l.back().second = cnt;
		pv = g;
	}
	int last = cnt;
	for(int i=0;i<b.l.size();i++){
		g = __gcd(g, b.l[i].first);
		cnt = last + b.l[i].second;
		if(g != pv) res.l.emplace_back(pii(g, cnt));
		else res.l.back().second = cnt;
		pv = g;
	}
	g = 0, pv = 0, cnt = 0;
	for(int i=0;i<b.r.size();i++){
		g = __gcd(g, b.r[i].first);
		cnt = b.r[i].second;
		if(g != pv) res.r.emplace_back(pii(g, cnt));
		else res.r.back().second = cnt;
		pv = g;
	}
	last = cnt;
	for(int i=0;i<a.r.size();i++){
		g = __gcd(g, a.r[i].first);
		cnt = last + a.r[i].second;
		if(g != pv) res.r.emplace_back(pii(g, cnt));
		else res.r.back().second = cnt;
		pv = g;
	}

	res.ans = a.ans + b.ans;

	int j = a.r.size()-1;
	for(int i=0;i<b.l.size();i++){
		while(j >= 0 && __gcd(b.l[i].first, a.r[j].first) == 1) j--;
		if(j >= 0){
			int ri = b.l[i].second;
			int le = a.r[j].second;
			if(i != 0) ri -= b.l[i-1].second;
			res.ans += (ll)le*ri;
		}
		else break;
	}

	return res;
}

void build(int n, int s, int e){
	if(s == e){
		st[n].l.emplace_back(pii(a[s], 1));
		st[n].r.emplace_back(pii(a[s], 1));
		st[n].ans = 0;
		if(a[s] != 1) st[n].ans = 1;
	}
	else{
		int mid = (s+e)/2;
		build(n+n, s, mid);
		build(n+n+1, mid+1, e);
		st[n] = merge(st[n+n], st[n+n+1]);
	}
}

void update(int n, int s, int e, int idx, int v){
	if(s == e){
		a[s] = v;
		st[n].l.clear();
		st[n].r.clear();
		st[n].ans = 0;

		st[n].l.emplace_back(pii(a[s], 1));
		st[n].r.emplace_back(pii(a[s], 1));
		if(a[s] != 1) st[n].ans = 1;
	}
	else{
		int mid = (s+e)/2;
		if(idx <= mid) update(n+n, s, mid, idx, v);
		else update(n+n+1, mid+1, e, idx, v);
		st[n] = merge(st[n+n], st[n+n+1]);
	}
}

node query(int n, int s, int e, int l, int r){
	if(s > r || l > e) return node();
	if(l <= s && e <= r) return st[n];
	int mid = (s+e)/2;
	return merge(query(n+n, s, mid, l, r), query(n+n+1, mid+1, e, l, r));
}

int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
	}
	build(1, 1, n);
	while(q--){
		int t, l, r;
		scanf("%d%d%d", &t, &l, &r);
		if(t == 1){
			update(1, 1, n, l, r);
		}
		else{
			printf("%lld\n", query(1, 1, n, l, r).ans);
		}
	}
}

Compilation message

garaza.cpp: In function 'node merge(node, node)':
garaza.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.l.size();i++){
              ~^~~~~~~~~~~
garaza.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.l.size();i++){
              ~^~~~~~~~~~~
garaza.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.r.size();i++){
              ~^~~~~~~~~~~
garaza.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.r.size();i++){
              ~^~~~~~~~~~~
garaza.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.l.size();i++){
              ~^~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:109: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:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
garaza.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 22392 KB Output is correct
2 Correct 53 ms 23032 KB Output is correct
3 Correct 82 ms 23416 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 26156 KB Output is correct
2 Correct 536 ms 28108 KB Output is correct
3 Correct 498 ms 28492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 32568 KB Output is correct
2 Correct 1197 ms 34252 KB Output is correct
3 Correct 1052 ms 36624 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2008 ms 43876 KB Output is correct
2 Correct 2170 ms 46748 KB Output is correct
3 Correct 1775 ms 47440 KB Output is correct