oj.uz

Submission #332796

# Submission time Handle Problem Language Result Execution time Memory
332796 2020-12-03T11:53:33 Z NaimSS Garaža (COCI17_garaza) C++14
120 / 160
 4000 ms 80692 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ff first
#define ss second
#define db(x) cerr << #x <<" == " << x << "\n",cerr.flush()
#define sz(v) ((int)v.size())
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
// __gcd(a,b);
int gcd(int a,int b){
	return __gcd(a,b);
}
struct node{
	ll tot;
	int tam;
	map<int,int> Pref,Suf;
	node(int V=1){
		tot=0;
		Pref = Suf = map<int,int>();
		tot=(V > 1);
		tam = 1;
		if(V > 1){
			Pref[V] = 1;
			Suf[V] = 1;
		}
	}
};

node operator+(const node& A,const node& B){
	node res;
	res.tot = A.tot + B.tot;
	res.tam = A.tam + B.tam;
	// atualiza o TOT:
	vector<pii> inter,inter2;
	for(auto it1 : A.Suf){
		inter.pb(pii(it1.ss,it1.ff));
	}
	for(auto it1 : B.Pref){
		inter2.pb(pii(it1.ss,it1.ff));
	}
	sort(inter.begin(),inter.end());
	sort(inter2.begin(),inter2.end());
	int last=0;
	
	for(auto it : inter){
		assert(last!=it.ff);
		ll tam = it.ff - last;
		
		int last2=0;
		for(auto it2 : inter2){
			int g = gcd(it2.ss,it.ss);
			if(g==1)break;
			int tam2 = it2.ff - last2;
			last2 = it2.ff;
			res.tot+=1ll*tam*tam2;
		}
		last = it.ff;
	}
	
	// Atualiza o prefixo:
	map<int,int> Pref = A.Pref,Suf = B.Suf;

	for(auto it1  : A.Pref){
		if(it1.ss!=A.tam)continue;
		for(auto it2 : B.Pref){

			int g = gcd(it1.ff,it2.ff);
			if(g==1)continue;

			if(Pref.count(g)){
				Pref[g]=max(Pref[g],A.tam + it2.ss);
			}else{
				Pref[g] = A.tam + it2.ss;
			}

		}
	}
	// Atualiza o Sufixo:

	for(auto it1 : B.Suf){
		if(it1.ss!=B.tam)continue;
		for(auto it2 : A.Suf){
			int g = gcd(it1.ff,it2.ff);
			if(g==1)continue;

			if(Suf.count(g)){
				Suf[g]=max(Suf[g],B.tam + it2.ss);
			}else{
				Suf[g] = B.tam + it2.ss;
			}
		}
	}

	res.Pref = Pref;
	res.Suf = Suf;
	return res;
}


const int N = 100100;
node tree[4*N];
int V[N];
/*
ll brute(int l,int r){
	ll res=0;
	for(int i=l;i<=r;i++){
		int g = V[i];
		for(int j=i;j<=r;j++){
			g = gcd(g,V[j]);
			if(g>1)res++;
		}
	}
	return res;
}

const int DB = 1;

void print(node no,int i,int j){
	cout<<"estamos em: "<<i<<" "<<j<<endl;
	cout<<"PREF"<<endl;
	for(auto it : no.Pref){
		cout << it.ff<<" "<<it.ss<<endl;
	}
	cout<<"SUF"<<endl;
	for(auto it : no.Suf){	
		cout << it.ff<<" "<<it.ss<<endl;
	}
}*/

void build(int no,int i,int j){
	if(i==j){
		tree[no] = node(V[i]);
		/*
		assert(tree[no].tot == brute(i,j));
		*/
		return;  
	}
	int mid = (i+j)/2,l=no*2,r=no*2+1;
	build(l,i,mid);
	build(r,mid+1,j);
	tree[no] = tree[l] + tree[r];
	//print(tree[no],i,j);
	//cout << i<<" "<<j<<" "<<tree[no].tot<<endl;
}

void update(int no,int i,int j,int p){
	if(i==j){
		tree[no] = node(V[i]);
		return;
	}
	int mid = (i+j)/2,l=no*2,r=no*2+1;
	if(p<=mid){
		update(l,i,mid,p);
	}else update(r,mid+1,j,p);
	tree[no] = tree[l] + tree[r];
}

inline int ok(int i,int j,int a,int b){
	if(i>j || i>b || j < a)return false;
	return true;
}
node query(int no,int i,int j,int a,int b){
	if(a<=i and j<=b)return tree[no];
	int mid = (i+j)/2,l=no*2,r=no*2+1;

	int ok1 = ok(i,mid,a,b);
	int ok2 = ok(mid+1,j,a,b);
	node L,R;
	if(ok1)L = query(l,i,mid,a,min(b,mid));
	if(ok2)R = query(r,mid+1,j,max(a,mid+1),b);


	if(ok1 and ok2){
		//cout<<"HERE"<<endl;
		node res = L+R;
		return res;
		/*print(L,i,mid);
		print(R,mid+1,j);
		cout << L.tot<<" "<<R.tot <<" "<<res.tot<<endl;
		cout << brute(3,3)<<" "<<brute(4,5) << endl;
		return res;*/
	}
	if(ok1)return L;
	return R;
}

// COMPLEXIDADE: O(M * log4) ? Kkkkk
int32_t main(){
	fastio;
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> V[i];
	} 

	build(1,1,n);
	
	while(q--){
		int op;
		cin >> op;
		if(op == 1){
			int I,vv;
			cin >> I >> vv;
			V[I] = vv;
			update(1,1,n,I);
		}else{
			int l,r;
			cin>>l>>r;
			node res = query(1,1,n,l,r);
			
			/*
			if(DB){
				if(res.tot!=brute(l,r)){
					cout<<"FUC"<<endl;
					cout << l<<" "<<r<<endl;
					for(int i=l;i<=r;i++){
						cout << V[i]<<" ";
					}
					cout <<endl;
					
					for(int i=l;i<=r;i++){
						for(int j=i;j<=r;j++){
							node R = query(1,1,n,i,j);
							if(R.tot!=brute(i,j)){
								cout<<"OI "<<i<<" "<<j<<endl;
							}
						}
					}
					

					cout << res.tot<<" "<<brute(l,r)<<endl;
					print(res,l,r);
					exit(0);
				}
				assert(res.tot == brute(l,r));
			}
			*/
			cout << res.tot << endl;
		}
	}
	return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44524 KB Output is correct
2 Correct 96 ms 45292 KB Output is correct
3 Correct 111 ms 45932 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 51032 KB Output is correct
2 Correct 931 ms 55148 KB Output is correct
3 Correct 473 ms 52204 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 62504 KB Output is correct
2 Correct 1657 ms 60140 KB Output is correct
3 Correct 1035 ms 59884 KB Output is correct

Subtask #4
0 / 40.0

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