CCC 2021 S5 - Math Homework

1//By Timothy Shnayder, Newmarket High School2 3/*4The idea of this problem is to first interate through each index and build it based of 5the LCM of all the numbers that the index should be a GCD of.6 7This is sped up by just marking where a gcd of x starts and ends (like a difference array).8 9Then building a gcd segment tree to check the gcd of the given intervals in O(logn) time.10We then just check over each given range to see if the gcd matches. 11If any of the ranges don't work then there is no solutions and it is impossible.12If all the ranges work then print the array we originally built13*/14 15 16#include <bits/stdc++.h>17#define pii pair<int, int>18#define vpii vector<pair<int, int>>19#define vi vector<int>20#define pb push_back21#define ms(a, x) memset(a, x, sizeof(a))22#define fs first23#define sn second24const int INF = 0x3f3f3f3f;25using namespace std;26 27 28#define TLEFT index*229#define TRIGHT index*2+130 31 32struct gcdEvent {33	int x, y, z;34};35 36 37int n, m;38int diff[17][150005];39int res[150005];40 41 42vector<gcdEvent> check;43 44 45int lcm(int a, int b) {46	return a*b/__gcd(a,b);47}48 49 50int seg[4*150001];51void build(int tl, int tr, int index=1) {52	if(tl == tr) {53		seg[index] = res[tl];54	}else {55		int mid = (tl+tr)/2;56		build(tl, mid, TLEFT);57		build(mid+1, tr, TRIGHT);58		seg[index]=__gcd(seg[TLEFT],seg[TRIGHT]);59	}60}61 62 63int query(int ql, int qr, int tl, int tr, int index = 1) {64	if(tl >= ql && tr <= qr) {65		return seg[index];66	}67	if(ql > tr || qr < tl){68		return -1;69	}70	int mid = (tl+tr)/2;71	int left = query(ql,qr,tl,mid,TLEFT);72	int right = query(ql,qr,mid+1,tr,TRIGHT);73	if(left == -1) {74		return right;75	}76	if(right == -1) {77		return left;78	}79	return __gcd(left,right);80}81 82 83int main() {84	ios_base::sync_with_stdio(0);85	cin.tie(0);86	cout.tie(0);87 88 89 90 91	cin >> n >> m;92	fill(res,res+n+1, 1);93	for(int i = 0; i < m; i++) {94		int x, y, z;95		cin >> x >> y >> z;96		check.push_back({x,y,z}); //we later check these ranges to see if it works97 98		diff[z][x]++; //gcd of z starts at x99		diff[z][y+1]--; // and ends at y+1100	}101 102 103    //build the result array104	for(int i = 1; i <= n; i++) {105		for(int g = 1; g<=16; g++) {106			diff[g][i]+=diff[g][i-1];107			if(diff[g][i]>=1) {108				res[i]=lcm(res[i],g);109			}110		}111	}112 113	build(1,n);114 115    //check to see if the given ranges work on the result array116	for(auto evnt: check) {117		int eventGcd = query(evnt.x,evnt.y,1,n);118		if(eventGcd!=evnt.z) {119			cout << "Impossible";120			return 0;121		}122	}123 124    //all ranges worked so print out the array125	for(int i = 1; i <= n; i++) {126		cout << res[i] << " ";127	}128 129 130	return 0;131}