Submission #332520

#	Time	Username	Problem	Language	Result	Execution time	Memory
332520		CaroLinda	Garaža (COCI17_garaza)	C++14	160 / 160	1514 ms	41068 KiB

garaza

#include <bits/stdc++.h>

#define ll long long
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()

const int MAX = 1e5+10 ;

using namespace std ;

int mdc(int x, int y)
{
	if( x < y ) swap(x,y) ;
	if( y == 0 ) return x ;

	return mdc( y, x%y ) ;

}

struct Node
{
	ll qtd ;
	vector< pair<int,int> > suf, pref;
} ;


struct Seg1
{

	Node crappy ;
	Node tree[MAX*4] ;
	int toBuild[MAX] ;

	int m(int l, int r ) { return (l+r)>>1 ; }

	void merge(Node &t, Node &l, Node &r , int mid )
	{
		t.qtd = r.qtd + l.qtd ;

		int toSubtractL = mid+1 ;
		for(int i = 0 ; i < sz(l.suf) ; toSubtractL = l.suf[i].second , i++ )
		{
			int toSubtractR = mid ;
			ll qtd = (ll)(toSubtractL - l.suf[i].second ) ;

			for(int j = 0 ; j < sz(r.pref) ; toSubtractR = r.pref[j].second , j++ )
			{
				if(mdc(l.suf[i].first, r.pref[j].first) == 1)
					break ;

				t.qtd += qtd * (ll)( r.pref[j].second - toSubtractR ) ;
			}
		}
		

		t.pref.clear() ;
		if(sz(l.pref) > 0 )
		{
			for(auto e : l.pref ) t.pref.push_back(e) ;

			int gcdLeft = l.pref.back().first ;
			for(int i = 0 ; i < sz(r.pref) ; )
			{
				int j = i ;
				gcdLeft = mdc(gcdLeft, r.pref[i].first) ;
				int newGcd = gcdLeft ;

				while( newGcd == gcdLeft )
				{
					j++ ;
					if(j == sz(r.pref)) break ;
					newGcd = mdc( r.pref[j].first , newGcd ) ;
				}

				if(gcdLeft == l.pref.back().first ) t.pref.back().second = r.pref[j-1].second ;
				else t.pref.push_back( make_pair( gcdLeft , r.pref[j-1].second ) ) ;

				i = j ;

			}	
		}
		else 
		{
			for(auto e : r.pref ) t.pref.push_back( e ) ;
		}

		t.suf.clear() ;
		if( sz(r.suf) > 0  )
		{
			for(auto e : r.suf ) t.suf.push_back(e) ;

			int gcdRight = r.suf.back().first ;
			for(int i = 0; i < sz(l.suf) ; )
			{

				int j = i ;
				int newGcd = mdc(gcdRight, l.suf[i].first) ;
				gcdRight = newGcd ;

				while(newGcd == gcdRight )
				{
					j++;
					if(j == sz(l.suf) ) break ;
					newGcd = mdc(gcdRight, l.suf[j].first ) ;

				}

				if(gcdRight == r.suf.back().first ) t.suf.back().second = l.suf[j-1].second ;
				else t.suf.push_back(make_pair(gcdRight, l.suf[j-1].second )) ;

				i = j ;

			}
		}
		else 
		{
			for(auto e : l.suf ) t.suf.push_back(e) ;
		}

	}

	void build(int pos, int l, int r)
	{
		if( l == r )
		{
			tree[pos].suf.push_back(make_pair(toBuild[l] , l)) ;
			tree[pos].pref.push_back(make_pair(toBuild[l] , l)) ;
			tree[pos].qtd = ( toBuild[l] > 1 ) ;
			return ;
		}

		build(pos<<1 , l , m(l,r) ) ;
		build(pos<<1|1 , m(l,r)+1, r ) ;

		merge(tree[pos] , tree[pos<<1] , tree[pos<<1|1], m(l,r) ) ;

	}

	void updPoint(int pos, int l, int r, int idx, int newVal )
	{
		if( l == r )
		{
			tree[pos].suf.clear() ;
			tree[pos].pref.clear() ;

			tree[pos].pref.push_back( make_pair(newVal, l) ) ;
			tree[pos].suf.push_back( make_pair(newVal, l) ) ;
			tree[pos].qtd = ( newVal > 1 ) ;

			return ;
		}


		if(idx <= m(l,r) ) updPoint(pos<<1 , l , m(l,r) , idx, newVal ) ;
		else updPoint(pos<<1|1 , m(l,r)+1 , r, idx, newVal ) ;

		merge( tree[pos] , tree[pos<<1] , tree[pos<<1|1] ,m(l,r) ) ;

	}


	Node qry(int pos, int l, int r, int beg, int en  )
	{


		if( l > en || r < beg ) return crappy ;
		if(l >= beg && r<= en) return tree[pos] ;

		Node t, al, ar ;

		al = qry(pos<<1  , l ,m(l,r) , beg, en ) ;
		ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;

		merge(t, al, ar , m(l,r) ) ;

		return t ;

	}

	void print(int pos, int l, int r)
	{

		printf("In the node [%d, %d], with qtd %lld:\n" , l , r , tree[pos].qtd ) ;
		for(auto e : tree[pos].pref ) printf("(%d,%d) " , e.first, e.second ) ;
		printf("\n") ;
		for(auto e : tree[pos].suf ) printf("(%d,%d) " , e.first, e.second ) ;
		printf("\n") ;

		if(l == r) return ;

		print(pos<<1 , l , m(l,r) ) ;
		print(pos<<1|1 , m(l,r)+1, r ) ;

	}

} seg1 ;

int n , m ;
int a[MAX] ;

void parcial()
{

	for(int i = 0 , t , l , r ;  i < m ; i++ )
	{
		scanf("%d %d %d", &t, &l, &r ) ;

		if(t == 1)
		{
			a[l] = r ;
			continue ;
		}

		int qtd= 0  ;

		for(int i = l ; i <= r ; i++ )
		{
			int g = a[i] ;

			for(int j = i ; j <= r ; j++ )
			{
				g = mdc(g, a[j]) ;
				if(g == 1) break ;
				qtd++ ;
			}
		}

		printf("%d\n" , qtd ) ;

	}

	exit(0) ;
}

int main()
{

	scanf("%d %d", &n, &m ) ;

	for(int i = 1 ; i <= n ; i++ )
	{
		scanf("%d", &seg1.toBuild[i] ) ;
		a[i] = seg1.toBuild[i] ;
	}

	if( max(n,m) <= 100) parcial() ;

	seg1.build(1,1,n) ;

	for(int i = 0 , t, l , r ; i < m ;i++ )
	{
		scanf("%d %d %d", &t, &l, &r ) ;

		if(t == 1)
		{
			seg1.updPoint(1,1,n, l,r) ;
			continue ;
		}

		printf("%lld\n", seg1.qry(1,1,n, l, r).qtd ) ;

	} 

}

Compilation message (stderr)

garaza.cpp: In function 'void parcial()':
garaza.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  206 |   scanf("%d %d %d", &t, &l, &r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:238:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  238 |  scanf("%d %d", &n, &m ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
garaza.cpp:242:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  242 |   scanf("%d", &seg1.toBuild[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:252:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  252 |   scanf("%d %d %d", &t, &l, &r ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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