oj.uz

Submission #332590

# Submission time Handle Problem Language Result Execution time Memory
332590 2020-12-02T22:30:24 Z Lawliet Garaža (COCI17_garaza) C++17
160 / 160
 798 ms 7336 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 100010;

int myGCD(int a, int b)
{
	while( b != 0 )
		swap( a , b ), b %= a;

	return a;
}

class SegmentTreeOpts
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void merge(int node, int idLeft, int idRight)
		{
			sum[node] = sum[idLeft] + sum[idRight];
			mx[node] = max( mx[idLeft] , mx[idRight] );
		}

		void refresh(int node, int l, int r)
		{
			if( lazy[node] == -1 ) return;

			lli lz = lazy[node];
			lazy[node] = -1;

			mx[node] = lz;
			sum[node] = lz*(r - l + 1);

			if( l == r ) return;

			lazy[ getLeft(node) ] = lz;
			lazy[ getRight(node) ] = lz;
		}

		void build(int node, int l, int r)
		{
			lazy[node] = -1;

			if( l == r )
			{
				mx[node] = sum[node] = l;
				return;
			}

			int m = ( l + r )/2;

			build( getLeft(node) , l , m );
			build( getRight(node) , m + 1 , r );

			merge( node , getLeft(node) , getRight(node) );
		}

		void updateSet(int node, int l, int r, int i, int j, int v)
		{
			refresh( node , l , r );

			if( j < l || r < i ) return;

			if( i <= l && r <= j )
			{
				lazy[node] = v;
				refresh( node , l , r );

				return;
			}

			int m = ( l + r )/2;

			updateSet( getLeft(node) , l , m , i , j , v );
			updateSet( getRight(node) , m + 1 , r , i , j , v );

			merge( node , getLeft(node) , getRight(node) );
		}

		int bs(int node, int l, int r, int k)
		{
			refresh( node , l , r );

			if( mx[node] < k ) return r + 1;
			if( l == r ) return l;

			int m = ( l + r )/2;

			refresh( getLeft(node) , l , m );

			if( mx[ getLeft(node) ] >= k ) return bs( getLeft(node) , l , m , k );
			return bs( getRight(node) , m + 1 , r , k );
		}

		lli querySum(int node, int l, int r, int i, int j)
		{
			refresh( node , l , r );

			if( j < l || r < i ) return 0;
			if( i <= l && r <= j ) return sum[node];

			int m = ( l + r )/2;

			lli sumLeft = querySum( getLeft(node) , l , m , i , j );
			lli sumRight = querySum( getRight(node) , m + 1 , r , i , j );

			return sumLeft + sumRight;
		}

	protected:

		int mx[4*MAXN];
		int lazy[4*MAXN];

		lli sum[4*MAXN];
};

class SegmentTreeGCD
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void getNodes(int node, int l, int r, int i, int j);

		void updateSet(int node, int l, int r, int i, int v)
		{
			if( i < l || r < i ) return;

			if( l == r )
			{
				mdc[node] = v;
				return;
			}

			int m = ( l + r )/2;

			updateSet( getLeft(node) , l , m , i , v );
			updateSet( getRight(node) , m + 1 , r , i , v );

			mdc[node] = myGCD( mdc[ getLeft(node) ] , mdc[ getRight(node) ] );
		}

		int bsMultiple(int node, int l, int r, int k)
		{
			if( l == r ) return l;

			int m = ( l + r )/2;
			int valRight = mdc[ getRight(node) ];

			if( valRight%k == 0 ) return bsMultiple( getLeft(node) , l , m , k );
			return bsMultiple( getRight(node) , m + 1 , r , k );
		}

		int bsCoprime(int node, int l, int r, int k)
		{
			if( l == r ) return l;

			int m = ( l + r )/2;

			int valLeft = mdc[ getLeft(node) ];
			int newValue = myGCD( valLeft , k );

			if( newValue == 1 ) return bsCoprime( getLeft(node) , l , m , k );
			return bsCoprime( getRight(node) , m + 1 , r , newValue );
		}

		int getMDC(int node) { return mdc[node]; }

		SegmentTreeGCD()
		{
			for(int i = 0 ; i < 4*MAXN ; i++)
				mdc[i] = 1;
		}

	protected:

		int mdc[4*MAXN];
};

int n, q;

int v[MAXN];

vector<pii> intervals;
vector<int> intervalNodes;

vector< pair<pii,int> > breaks;

SegmentTreeGCD vGCD;
SegmentTreeOpts opts;

void SegmentTreeGCD::getNodes(int node, int l, int r, int i, int j)
{
	if( j < l || r < i ) return;

	if( i <= l && r <= j ) 
	{
		intervalNodes.push_back( node );
		intervals.push_back( { l , r } );

		return;
	}

	int m = ( l + r )/2;

	getNodes( getLeft(node) , l , m , i , j );
	getNodes( getRight(node) , m + 1 , r , i , j );
}

void getNodes(int L, int R)
{
	intervals.clear();
	intervalNodes.clear();
	vGCD.getNodes( 1 , 1 , n , L , R );
}

int findOpt(int ind, int curVal)
{
	for(int i = 0 ; i < (int)intervalNodes.size() ; i++)
	{
		int node = intervalNodes[i];
		int curG = vGCD.getMDC(node);

		if( myGCD( curVal , curG ) == 1 )
		{
			int L = intervals[i].first;
			int R = intervals[i].second;

			return vGCD.bsCoprime( node , L , R , curVal );
		}

		curVal = myGCD( curVal , curG );
	}

	return n + 1;
}

void update(int ind, int val)
{
	v[ind] = val;
	vGCD.updateSet( 1 , 1 , n , ind , val );

	getNodes( 1 , ind );

	int last = ind + 1;
	int curVal = v[ind];

	breaks.clear();

	for(int i = (int)intervals.size() - 1 ; i >= 0 ; i--)
	{
		int node = intervalNodes[i];
		int curG = vGCD.getMDC(node);

		if( curG%curVal != 0 )
		{
			int L = intervals[i].first;
			int R = intervals[i].second;

			int p = vGCD.bsMultiple( node , L , R , curVal ) + 1;

			breaks.push_back( { {p , last - 1} , curVal } );

			last = p; i++;
			curVal = myGCD( curVal , v[p - 1] );
		}
	}

	if( last != 1 )
		breaks.push_back( { {1 , last - 1} , curVal } );

	getNodes( ind , n );

	for(int i = 0 ; i < (int)breaks.size() ; i++)
	{
		int valBreak = breaks[i].second;

		if( valBreak == 1 ) continue;

		int Lbreak = breaks[i].first.first;
		int Rbreak = breaks[i].first.second;

		int optBreak = findOpt( ind , valBreak );

		opts.updateSet( 1 , 1 , n , Lbreak , Rbreak , optBreak );
	}

	if( breaks.empty() || breaks.back().second != 1 ) return;

	int getFirst = opts.bs( 1 , 1 , n , ind + 1 );

	int R = breaks.back().first.second;

	if( getFirst <= R )
		opts.updateSet( 1 , 1 , n , getFirst , R , ind );
}

lli getSumPA(int L, int R)
{
	lli sz = R - L + 1;
	lli sum = L + R;

	return ( sz*sum )/2;
}

lli query(int L, int R)
{
	lli ans = -getSumPA( L , R );
	int last = opts.bs( 1 , 1 , n , R + 1 );

	if( L <= last - 1 ) 
		ans += opts.querySum( 1 , 1 , n , L , last - 1 );

	if( last <= R )
	{
		lli diff = R - max( L , last ) + 1;
		ans += diff*(R + 1);
	}

	return ans;
}

int main()
{
	scanf("%d %d",&n,&q);

	opts.build( 1 , 1 , n );

	for(int i = 1 ; i <= n ; i++)
	{
		int val;
		scanf("%d",&val);

		update( i , val );
	}

	for(int i = 1 ; i <= q ; i++)
	{
		int type;
		scanf("%d",&type);

		if( type == 1 )
		{
			int ind, val;
			scanf("%d %d",&ind,&val);

			update( ind , val );
		}
		if( type == 2 )
		{
			int L, R;
			scanf("%d %d",&L,&R);

			printf("%lld\n",query( L , R ));
		}
	}
}

Compilation message

garaza.cpp: In function 'int main()':
garaza.cpp:333:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  333 |  scanf("%d %d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
garaza.cpp:340:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  340 |   scanf("%d",&val);
      |   ~~~~~^~~~~~~~~~~
garaza.cpp:348:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  348 |   scanf("%d",&type);
      |   ~~~~~^~~~~~~~~~~~
garaza.cpp:353:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  353 |    scanf("%d %d",&ind,&val);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
garaza.cpp:360:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  360 |    scanf("%d %d",&L,&R);
      |    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1900 KB Output is correct
2 Correct 15 ms 2156 KB Output is correct
3 Correct 26 ms 2156 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 3052 KB Output is correct
2 Correct 132 ms 3308 KB Output is correct
3 Correct 106 ms 3180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 4332 KB Output is correct
2 Correct 348 ms 4716 KB Output is correct
3 Correct 220 ms 4332 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 7336 KB Output is correct
2 Correct 798 ms 6892 KB Output is correct
3 Correct 391 ms 6764 KB Output is correct