CCC '21 S5 - Math Homework Solution

//By Timothy Shnayder, Newmarket High School

/*
The idea of this problem is to first interate through each index and build it based of 
the LCM of all the numbers that the index should be a GCD of.

This is sped up by just marking where a gcd of x starts and ends (like a difference array).

Then building a gcd segment tree to check the gcd of the given intervals in O(logn) time.
We then just check over each given range to see if the gcd matches. 
If any of the ranges don't work then there is no solutions and it is impossible.
If all the ranges work then print the array we originally built
*/


#include <bits/stdc++.h>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vi vector<int>
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define fs first
#define sn second
const int INF = 0x3f3f3f3f;
using namespace std;


#define TLEFT index*2
#define TRIGHT index*2+1


struct gcdEvent {
	int x, y, z;
};


int n, m;
int diff[17][150005];
int res[150005];


vector<gcdEvent> check;


int lcm(int a, int b) {
	return a*b/__gcd(a,b);
}


int seg[4*150001];
void build(int tl, int tr, int index=1) {
	if(tl == tr) {
		seg[index] = res[tl];
	}else {
		int mid = (tl+tr)/2;
		build(tl, mid, TLEFT);
		build(mid+1, tr, TRIGHT);
		seg[index]=__gcd(seg[TLEFT],seg[TRIGHT]);
	}
}


int query(int ql, int qr, int tl, int tr, int index = 1) {
	if(tl >= ql && tr <= qr) {
		return seg[index];
	}
	if(ql > tr || qr < tl){
		return -1;
	}
	int mid = (tl+tr)/2;
	int left = query(ql,qr,tl,mid,TLEFT);
	int right = query(ql,qr,mid+1,tr,TRIGHT);
	if(left == -1) {
		return right;
	}
	if(right == -1) {
		return left;
	}
	return __gcd(left,right);
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);




	cin >> n >> m;
	fill(res,res+n+1, 1);
	for(int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		check.push_back({x,y,z}); //we later check these ranges to see if it works

		diff[z][x]++; //gcd of z starts at x
		diff[z][y+1]--; // and ends at y+1
	}

 
    //build the result array
	for(int i = 1; i <= n; i++) {
		for(int g = 1; g<=16; g++) {
			diff[g][i]+=diff[g][i-1];
			if(diff[g][i]>=1) {
				res[i]=lcm(res[i],g);
			}
		}
	}

	build(1,n);

    //check to see if the given ranges work on the result array
	for(auto evnt: check) {
		int eventGcd = query(evnt.x,evnt.y,1,n);
		if(eventGcd!=evnt.z) {
			cout << "Impossible";
			return 0;
		}
	}

    //all ranges worked so print out the array
	for(int i = 1; i <= n; i++) {
		cout << res[i] << " ";
	}


	return 0;
}