oj.uz

Submission #332522

# Submission time Handle Problem Language Result Execution time Memory
332522 2020-12-02T19:04:06 Z CaroLinda Garaža (COCI17_garaza) C++14
160 / 160
 1485 ms 38652 KB 
#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 ;

	}

} seg1 ;

int n , m ;
int a[MAX] ;

int main()
{

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

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


	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

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

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22380 KB Output is correct
2 Correct 37 ms 22764 KB Output is correct
3 Correct 49 ms 23020 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 25708 KB Output is correct
2 Correct 396 ms 26988 KB Output is correct
3 Correct 251 ms 26788 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 30444 KB Output is correct
2 Correct 820 ms 30316 KB Output is correct
3 Correct 541 ms 31340 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1485 ms 38652 KB Output is correct
2 Correct 1255 ms 38648 KB Output is correct
3 Correct 946 ms 37484 KB Output is correct