oj.uz

답안 #409330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409330 2021-05-20T15:12:14 Z inbarin 이상한 기계 (APIO19_strange_device) C++14
65 / 100
 711 ms 33356 KB 
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <string>
#include <stack>
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>

using namespace std;
typedef long long int63;
typedef unsigned long long int64;
#define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
#define forlb(name,start,end,jump) for(int63 name = end - 1; name >= start; name+=jump)
#define forn(name,start,end) forl(name,start,end,1)
#define fornb(name,start,end) forlb(name,start,end,-1)
#define fort(start,end) forn(i,start,end)
#define fortb(start,end) fornb(i,start,end)
#define forto(start,end) forn(j,start,end)
#define fortob(start,end) fornb(j,start,end)
#define fortoo(start,end) forn(l,start,end)
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
#define makeitem(itemname,itemtype) itemtype itemname; cin >> itemname
#define makeint(intname) int63 intname; cin >> intname
#define makeN int63 n; cin >> n
#define makeM int63 m; cin >> m
#define makeL int63 l; cin >> l
#define makeT int63 t; cin >> t
#define makeK int63 k; cin >> k
#define point pair<int63,int63>
#define dpoint pair<double,double>
#define ldpoint pair<long double,long double>
#define spoint pair<short,short>
#define ipoint pair<int,int>
#define matrix(type) vector<vector<type>>
#define in(name) cin >> name;
#define tosort(name) name.begin(),name.end()
int63 powmod(int63 base, int63 exponent, int63 mod) {
	int63 result = 1;
	while (exponent > 0) {
		if (exponent % 2 == 0) {
			exponent /= 2;
			base = (base * base) % mod;
		}
		else {
			result = (result * base) % mod;
			exponent /= 2;
			base = (base * base) % mod;
		}
	}
	return result;
}
bool decresing(int63 x, int63 y) {
	return x > y;
}
int63 modInverse(int63 a, int63 b) {//finds inverse of a mod b ...?
	int63 m = b;
	int63 y = 0, x = 1;
	while (a > 1) {
		int63 q = a / m;
		int63 t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += b;
	}
	return x;
}
int63 trin(int63 start, int63 stop) {
	return (stop - start + 1) * (stop + start) / 2;
}
int63 trin2(int63 start, int63 stop, int63 mod) {
	return (((((stop - start + 1) % mod) * ((stop + start) % mod)) % mod)*modInverse(2, mod) % mod) % mod;
}
int63 trig(int63 start, int63 stop, int63 jump, int63 mod) {
	return ((trin2((start + jump - 1) / jump, stop / jump, mod)) * (jump%mod)) % mod;
}
int63 cntot(int63 start, int63 stop, int63 jump, int63 mod) {
	return (stop / jump - (start + jump - 1) / jump + 1) % mod;
}
bool sortvectorf(point a, point b) {
	return((a.first > b.first) || (a.first == b.first && a.second > b.second));
}
bool sortvectordiv(point a, point b) {
	return a.first * b.second > b.first * a.second;
}
bool sortvectorfv(point a, point b) {
	return((a.first > b.first) || (a.first == b.first && a.second < b.second));
}
bool sortvectors(point a, point b) {
	return((a.second > b.second) || (a.second == b.second && a.first > b.first));
}
bool negasortvectorf(point a, point b) {
	return((a.first < b.first) || (a.first == b.first && a.second < b.second));
}
bool negasortvectors(point a, point b) {
	return((a.second < b.second) || (a.second == b.second && a.first < b.first));
}
vector<vector<int63>> findPermutationsI(vector<int63> &a) {
	// Sort the given array
	sort(a.begin(), a.end());
	vector<vector<int63> > sol;
	// Find all possible permutations
	do {
		sol.push_back(a);
	} while (next_permutation(a.begin(), a.end()));
	return sol;
}
vector<vector<string>> findPermutationsS(vector<string> &a) {
	// Sort the given array
	sort(a.begin(), a.end());
	vector<vector<string> > sol;
	// Find all possible permutations
	do {
		sol.push_back(a);
	} while (next_permutation(a.begin(), a.end()));
	return sol;
}
int63 gcd(int63 a, int63 b) {
	if (a == 0) {
		return b;
	}
	if (b == 0) {
		return a;
	}
	return gcd(b % a, a);
}
bool isprime(int63 n) {
	fort(2, n) {
		if (i * i > n) {
			break;
		}
		if ((n / i) * i == n) {
			return false;
		}
	}
	return true;
}
int63 fdivisor(int63 n, int63 fro) {
	fort(1, n + 1) {
		if ((n / i) * i == n && i >= fro) {
			return i;
		}
	}
	return -1;
}
vector<int63> divlist(int63 n) {
	vector<int63> curr;
	fort(1, n + 1) {
		if ((int63)i * i > n) {
			break;
		}
		if ((n / i) * i == n) {
			curr.push_back(i);
			curr.push_back(n / i);
		}
		if ((int63)i * i == n) {
			curr.pop_back();
		}
	}

	sort(all(curr));
	return curr;
}
vector<int63> pdivlist(int63 n) {
	vector<int63> curr;
	fort(2, n + 1) {
		if (i * i > n) {
			break;
		}
		if ((n % i) == 0) {
			if (isprime(i)) { curr.push_back(i); }
			int63 ni = n / i;
			if (isprime(ni)) { curr.push_back(ni); }
			if (i * i == n && isprime(i)) {
				curr.pop_back();
			}
			if (isprime(i)) {
				while ((n % i) == 0) {
					n /= i;
				}
			}
			if (isprime(ni)) {
				while ((n % ni) == 0) {
					n /= ni;
				}
			}
		}
		if (i % 2) {
			i++;
		}
	}
	if (n > 1 && (curr.size() == 0 || curr[curr.size()-1] != n) && isprime(n)) {
		curr.push_back(n);
	}
	sort(all(curr));
	return curr;
}
int63 countdivisors(int63 n, int63 divd, int63 rem) {
	vector<int63> divs = divlist(n);
	int63 tot = 0;
	fort(0, (int63)divs.size()) {
		if (divs[i] % divd == rem) {
			tot++;
		}
	}
	if (n % divd == rem) {
		tot++;
	}
	return tot;
}
int63 digsum(int63 num) {
	int63 cr = 0;
	while (num > 0) {
		cr += num % 10;
		num /= 10;
	}
	return cr;
}
vector<int63>atzeret;
int63 azeret(int63 num, int63 mod) {
	if (mod == 1000000007) {
		if ((int63)atzeret.size() > num) {
			return atzeret[num];
		}
		if (num == 0) {
			atzeret.push_back(1);
			return atzeret[num];
		}
		azeret(num - 1, mod);
		atzeret.push_back((atzeret[num-1] * num) % mod);
		return atzeret[num];
	}
	int63 sil = 1;
	while (num > 1) {
		sil *= num;
		sil %= mod;
		num--;
	}
	return sil;
}
int63 moddiv(int63 to, int63 by, int63 mod) {
	to %= mod;
	by %= mod;
	to *= modInverse(by, mod);
	return to % mod;
}
int63 choose(int63 num, int63 choice, int63 mod) {
	if (choice < 0 || choice > num) {
		return 0;
	}
	return moddiv(azeret(num, mod), (azeret(choice, mod)*azeret(num - choice, mod)) % mod, mod);
}
class node {
public:
	int data1;
	int data2;
	node* nxt;
	node* bef;
	node(int dat1, int dat2, node*bif) {
		this->nxt = NULL;
		this->bef = bif;
		this->bef->nxt = this;
		this->data1 = dat1;
		this->data2 = dat2;
	}
	node(int dat1, int dat2) {
		this->nxt = NULL;
		this->bef = NULL;
		this->data1 = dat1;
		this->data2 = dat2;
	}
	node() {
		this->nxt = NULL;
		this->bef = NULL;
		this->data1 = 0;
		this->data2 = 0;
	}
	void remove() {
		this->bef->nxt = this->nxt;
		if (this->nxt != NULL) {
			this->nxt->bef = this->bef;
		}
	}
	void push(int dat1, int dat2) {
		node* next = this->nxt;
		node* curr = new node(dat1, dat2, this);
		curr->nxt = next;
		next->bef = curr;
	}
};
bool by_first(pair<point, point> a, pair<point, point> b) {
	return a.first.first < b.first.first;
}
bool ff_fs(pair<pair<int63, bool>, int63> a, pair<pair<int63, bool>, int63> b) {
	return a.first.first < b.first.first || (a.first.first == b.first.first && a.first.second && !b.first.second);
}
bool f_s_b(pair<int63, int63> a, pair<int63, int63> b) {
	return a.first > b.first || (a.first == b.first && a.second > b.second);
}
#define make(name) int63 name; cin >> name
#define remake(name) if(name == -1){cin >> name;}

bool palindrome(string s) {
	fort(0, (int63)s.size() / 2) {
		if (s[i] != s[s.size() - 1 - i]) {
			return 0;
		}
	}
	return 1;
}
struct union_find {
	vector<int63>rot;
	vector<vector<int63>> rat;
	void init(int63 n) {
		fort(0, n) {
			rot.push_back(i);
			rat.push_back({ i });
		}
	}
	bool unio(int63 f, int63 s) {
		if (rot[f] == rot[s]) {
			return false;
		}
		//rot[f] <-> rot[s]
		if (rat[rot[f]].size() > rat[rot[s]].size()) {
			//s to f
			int63 siz = rat[rot[s]].size();
			int63 rs = rot[s];
			fort(0, siz) {
				rat[rot[f]].push_back(rat[rs][i]);
				rot[rat[rs][i]] = rot[f];
			}
			return true;
		}
		int63 siz = rat[rot[f]].size();
		int63 rf = rot[f];
		fort(0, siz) {
			rat[rot[s]].push_back(rat[rf][i]);
			rot[rat[rf][i]] = rot[s];
		}
		return true;
	}
};
//
vector<int> subsum(vector<int> items, int limit) {
	vector<vector<int> > table(items.size() + 1, vector<int>(limit + 1));
	forto(1, (int63)items.size() + 1) {
		int wt = items[j - 1];
		int val = wt;
		for (int w = 1; w < limit + 1; w++) {
			if (wt > w) {
				table[j][w] = table[j - 1][w];
			}
			else {
				table[j][w] = max(table[j - 1][w], (int)(table[j - 1][w - wt] + val));
			}
		}
	}
	vector<int> result;
	int w = limit;
	for (int j = items.size(); j > 0; j--) {
		bool was_added = table[j][w] != table[j - 1][w];
		if (was_added) {
			int wt = items[j - 1];
			result.push_back(j - 1);
			w -= wt;
		}
	}
	sort(all(result));
	return result;
}
int63 detrig(int63 num) {
	int63 minus = 0;
	while (true) {
		if (num <= 0) {
			return minus;
		}
		minus++;
		num -= minus;
	}
}
int63 palpref(string &s) {
	int63 ha1 = 0, ha2 = 0, hr1 = 0, hr2 = 0;
	int63 m1 = 1, m2 = 1;
	int63 mix = 0;
	forto(0, s.size()) {
		ha1 = (ha1 + m1 * s[j]) % 1000000007;
		ha2 = (ha2 + m2 * s[j]) % 998244353;

		hr1 = (s[j] + 359 * hr1) % 1000000007;
		hr2 = (s[j] + 401 * hr2) % 998244353;

		m1 *= 359, m1 %= 1000000007;
		m2 *= 401, m2 %= 998244353;

		if (ha1 == hr1 && ha2 == hr2) {
			mix = j + 1;
		}
	}
	return mix;
}
double diffclock(clock_t clock1, clock_t clock2)
{
	double diffticks = clock1 - clock2;
	double diffms = (diffticks) / (CLOCKS_PER_SEC / 1000);
	return diffms;
}
struct fenwick {
	int63 n;
	vector<int63> data;
	vector<int63> real;
	void init(int63 n) {
		this->n = n;
		data.resize(n);
		real.resize(n);
	}
	void add(int63 pos, int63 val) {
		real[pos] += val;
		pos++;
		int63 cur = 0;
		while (pos << cur <= this->n) {
			if (pos % 2 == 1) {
				this->data[(pos << cur) - 1] += val;
			}
			cur++;
			pos = (pos + 1) / 2;
		}
	}
	void upd(int63 pos, int63 val) {
		add(pos, val - real[pos]);
	}
	int63 query0(int63 a) {
		int63 sol = 0;
		int63 cur = 0;
		a++;
		while (a) {
			if (a % 2 == 1) {
				sol += data[(a << cur) - 1];
			}
			cur++;
			a /= 2;
		}
		return sol;
	}
	int63 query(int63 a, int63 b) {
		return query0(b) - query0(a - 1);
	}
};
struct fenwickOPT {
	int63 n;
	vector<int63> data;
	void init(int63 nn) {
		n = nn;
		data = vector<int63>(n, 0);
	}
	void add(int63 pos, int63 val) {
		pos++;
		while (pos <= n) {
			data[pos - 1] += val;
			pos += (pos & (-pos));
		}
	}
	int63 query0(int63 a) {
		int63 sol = 0;
		a++;
		while (a) {
			sol += data[a - 1];
			a -= (a & (-a));
		}
		return sol;
	}
};
void setIO(string s) { //this function is the template that redefines the standard IO
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}
point mi(point a, point b) {
	return { a.first - b.first,a.second - b.second };
}
bool isleft(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	if (a.first == b.first) {
		return (c.first < a.first) ^ (a.second > b.second);
	}
	long double m = (b.second - a.second) / ((double)b.first - a.first);
	long double y = a.second - a.first * m;
	return ((c.second - y - c.first * m) > 0) ^ (a.first > b.first);
}
bool online(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	c = mi(c, a);
	b = mi(b, a);
	a = mi(a, a);
	return ((a == b) || (b.second * c.first == c.second * b.first));
}
bool linein(point a, point b, point c) {//line from a to b, when it is 0,0 -> 0,1
	b.first -= a.first;
	c.first -= a.first;
	a.first = 0;
	b.second -= a.second;
	c.second -= a.second;
	a.second = 0;
	if (b.second < 0) {
		b.second *= -1;
		c.second *= -1;
	}
	if (b.first < 0) {
		b.first *= -1;
		c.first *= -1;
	}
	if (b.first == 0) {
		return ((c.first == 0) && (c.second >= 0) && (c.second <= b.second));
	}
	long double m = (b.second - a.second) / ((double)b.first - a.first);
	long double cy = abs(c.second - c.first * m);
	return ((abs(cy) < 1e-11) && (c.first >= 0) && (c.first <= b.first));
}
bool interhelp(point a, point b, point c, point d) {
	if (online(a, b, c) || online(a, b, d)) {
		return 1;
	}
	return (isleft(a, b, c) ^ isleft(a, b, d));
}
bool intersect(ldpoint a, ldpoint b, ldpoint c, ldpoint d) {
	if (online(a, b, c) && online(a, b, d)) {
		b.first -= a.first;
		c.first -= a.first;
		d.first -= a.first;
		a.first = 0;
		b.second -= a.second;
		c.second -= a.second;
		d.second -= a.second;
		a.second = 0;
		if (b.first == 0) {
			if (b.second < 0) {
				b.second *= -1;
				c.second *= -1;
				d.second *= -1;
			}
			if (d.second > c.second) {
				swap(c, d);
			}
			return (c.second >= 0 && d.second <= b.second);
		}
		b.second /= b.first;
		c.second /= b.first;
		d.second /= b.first;
		c.first /= b.first;
		d.first /= b.first;
		b.first = 1;
		c.second -= c.first * b.second;
		d.second -= d.first * b.second;
		b.second = 0;
		if (d.first > c.first) {
			swap(c, d);
		}
		return (c.first >= -1e-11 && d.first <= 1e-11);
	}
	return (interhelp(a, b, c, d) && interhelp(c, d, a, b));
}
int63 vci(point a, point b) {
	return abs(a.first*b.second - a.second*b.first);
}
int63 ar(point a, point b, point c) {
	point bb = mi(b, a), cc = mi(c, a);
	return vci(bb, cc);
}
bool intriangle(point a, point b, point c, point d) {
	return ((ar(a, b, c) + ar(a, b, d) + ar(a, c, d)) == ar(b, c, d));
}
int63 countlattice(point a, point b) {
	b.first -= a.first;
	b.second -= a.second;
	a.first = 0;
	a.second = 0;
	b.first = abs(b.first);
	b.second = abs(b.second);
	if (b.first == 0) {
		return b.second;
	}
	vector<int63> ops = divlist(b.first);
	fort(0, (int63)ops.size()) {
		if ((b.second * ops[i] % b.first) == 0) {
			return b.first / ops[i];
		}
	}
	return 0;
}
struct Line {
	mutable int63 m, b, p;
	const bool real;//real = comparison 1, not real = comparison 2
	bool operator<(const Line& o) const { if (real && o.real) { return (m < o.m); } else { return p < o.p; } };
};
struct cht : multiset<Line, less<Line>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const int63 inf = 9223372036854775807;
	int63 div(int63 a, int63 b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
	}
	//isect does ???
	//takes 2 iterators.
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->m == y->m) x->p = x->b > y->b ? inf : -inf;
		else x->p = div(y->b - x->b, x->m - y->m);
		return x->p >= y->p;
	}
	//adds a line...
	//how? 
	void add(int63 b, int63 m) {
		auto z = insert({ m, b, 0, 1 }), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}
	void init() {
		add(-9999999999999999, 0);
	}
	int63 query(int63 x) {
		if (empty()) exit(1);
		auto l = *(lower_bound({ 0, 0, x, 0 }));
		return l.m * x + l.b;
	}
};
bool spchfunc(point a, point b) {
	if (a.first == 0) {
		if (b.first == 0) {
			return a.second < b.second;
		}
		return 1;
	}
	if (b.first == 0) {
		return 0;
	}
	if (a.second * b.first != b.second * a.first) {
		return (a.second * b.first > b.second * a.first);
	}
	return (a.first < b.first);
}
vector<int63> ch(vector<int63> pts) {
	vector<point> ans;
	fort(0, pts.size() / 2) {
		ans.push_back({ pts[i * 2],pts[i * 2 + 1] });
	}
	sort(all(ans));
	point a0 = ans[0];
	fort(0, ans.size()) {
		ans[i] = mi(ans[i], a0);
	}
	sort(all(ans), spchfunc);
	fortb(0, ans.size() - 1) {
		if (ans[i].second * ans[i + 1].first != ans[i].first * ans[i + 1].second) {
			reverse(ans.begin() + i + 1, ans.begin() + ans.size());
			break;
		}
	}
	vector<bool>ich(ans.size(), 1);
	vector<int63> ret;
	vector<int63> st(2);
	st[0] = 0;
	st[1] = 1;
	fort(2, ans.size()) {
		while (st.size() > 1 && (!online(ans[st[st.size() - 2]], ans[st[st.size() - 1]], ans[i]) && isleft(ans[st[st.size() - 2]], ans[st[st.size() - 1]], ans[i]))) {
			ich[st[st.size() - 1]] = 0;
			st.pop_back();
		}
		st.push_back(i);
	}
	fort(0, ans.size()) {
		ans[i] = mi(ans[i], mi({ 0,0 }, a0));
	}
	fort(0, ans.size()) {
		if (!ich[i]) {
			continue;
		}
		ret.push_back(ans[i].first);
		ret.push_back(ans[i].second);
	}
	return ret;
}
struct Pqueue {
	#define Spoint pair<double,int63>
	vector<Spoint> vals;
	void add(Spoint ex) {
		vals.push_back(ex);
		int63 cr = vals.size() - 1;
		while (cr && vals[cr].first < vals[cr / 2].first) {
			swap(vals[cr], vals[cr / 2]);
			cr /= 2;
		}
	}
	void hpf() {
		int63 cr = 0;
		while (cr * 2 < vals.size()) {
			if (cr * 2 + 1 < vals.size() && vals[cr * 2 + 1].first < vals[cr * 2].first && vals[cr * 2 + 1].first < vals[cr].first) {
				swap(vals[cr], vals[cr * 2 + 1]);
				cr *= 2;
				cr++;
				continue;
			}
			if (vals[cr * 2].first < vals[cr].first) {
				swap(vals[cr], vals[cr * 2]);
				cr *= 2;
				continue;
			}
			break;
		}
	}
	void rem() {
		if (!vals.size()) {
			return;
		}
		swap(vals[0], vals[vals.size() - 1]);
		vals.pop_back();
		hpf();
	}
	int63 get() {
		if (!vals.size()) {
			return -1;
		}
		return vals[0].second;
	}
};
struct Seg {
	int63 l, r, v, t;
	Seg *lp, *rp;
	int63 v0() {
		if (t == 0) {
			return 999999999999;//min
		}
		if (t == 1) {
			return -999999999999;//max
		}
		if (t == 10) {
			return -999999999999;//min*
		}
		if (t == 11) {
			return 999999999999;//max*
		}
	}
	int63 v1() {
		if (t == 0) {
			return 999999999999;//min
		}
		if (t == 1) {
			return -999999999999;//max
		}
		if (t == 10) {
			return 999999999999;//min*
		}
		if (t == 11) {
			return -999999999999;//max*
		}
	}
	int63 act(int63 a, int63 b) {
		if (t == 0) {
			return min(a, b);
		}
		if (t == 1) {
			return max(a, b);
		}
		if (t == 10) {
			return min(a, b);
		}
		if (t == 11) {
			return max(a, b);
		}
	}
	void pull() {
		v = act(lp->v, rp->v);
	}
	Seg(int63 l, int63 r, int63 t) : l(l), r(r), t(t) {
		if (l == r) {
			v = v0();
			lp = NULL;
			rp = NULL;
			return;
		}
		lp = new Seg(l, (l + r) / 2, t);
		rp = new Seg((l + r) / 2 + 1, r, t);
		pull();
	}
	void upd(int63 p, int63 v) {
		if (l == r) {
			this->v = v;
			return;
		}
		if (p <= (l + r) / 2) {
			lp->upd(p, v);
		} else {
			rp->upd(p, v);
		}
		pull();
	}
	int63 query(int63 l, int63 r) {
		if (l > this->r || r < this->l) {
			return v1();
		}
		if (l <= this->l && r >= this->r) {
			return v;
		}

		return act(lp->query(l, r), rp->query(l, r));
	}
};
struct Dsu {
	vector<int63> f;
	vector<int63> s;
	Dsu(int63 n) {
		f = vector<int63>(n, -1);
		s = vector<int63>(n, 1);
	}
	int63 F(int63 x) {
		if (f[x] == -1) {
			return x;
		}
		return (f[x] = F(f[x]));
	}
	int63 S(int63 x) {
		return s[F(x)];
	}
	bool sm(int63 a, int63 b) {
		return F(a) == F(b);
	}
	void mrg(int63 a, int63 b) {
		a = F(a);
		b = F(b);
		if (a == b) {
			return;
		}
		if (s[a] > s[b]) {
			s[a] += s[b];
			f[b] = a;
		} else {
			s[b] += s[a];
			f[a] = b;
		}
	}
};

int63 t = 1;

bool mulK(int63 a, int63 b) {
	int63 c = a * b;
	if (c < 0 || c > (1e18 + 1e5) || c % a || c % b || ((c / a) != b) || ((c / b) != a)) {
		return 0;
	}
	return 1;
}

int main() {
	//setIO("tallbarn");
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	if (t == 0) {
		cin >> t;
	}
	do {
		make(n);
		make(A);
		make(B);
		//A,B
		//(x,y) -> ((x + B + 1) % A,y)
		//gcd(B+1,A) = ?
		//1 -> all ok
		//B = 1 -> (2t,0)
		//A * B / gcd
		A /= gcd(A, B + 1);
		int63 c;
		if (mulK(A, B)) {
			c = A * B;
		} else {
			c = 1e18 + 1e5;
		}
		vector<point> evnt;
		fort(0, n) {
			int63 a, b;
			cin >> a >> b;
			b -= a - (a % c);
			a %= c;
			if (b >= a + c) {
				evnt.push_back({ 0,-1 });
				evnt.push_back({ c - 1,1 });
			}
			if (b >= c) {
				evnt.push_back({ a,-1 });
				evnt.push_back({ c - 1,1 });
				evnt.push_back({ 0,-1 });
				evnt.push_back({ b - c,1 });
			} else {
				evnt.push_back({ a,-1 });
				evnt.push_back({ b,1 });
			}
		}
		sort(all(evnt));
		int63 ans = 0, cr = 0, pp = 0;
		fort(0, evnt.size()) {
			//cout << evnt[i].first << ' ' << -evnt[i].second << endl;
			if (cr) {
				ans += evnt[i].first - pp;
			}
			pp = evnt[i].first;
			if (evnt[i].second > 0) {
				cr--;
			} else {
				cr++;
				if (cr == 1) {
					ans++;
				}
			}
		}
		cout << ans << endl;
	} while (--t);
	return 0;
}

Compilation message

strange_device.cpp: In function 'int63 palpref(std::string&)':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:25:26: note: in expansion of macro 'forn'
   25 | #define forto(start,end) forn(j,start,end)
      |                          ^~~~
strange_device.cpp:397:2: note: in expansion of macro 'forto'
  397 |  forto(0, s.size()) {
      |  ^~~~~
strange_device.cpp: In function 'std::vector<long long int> ch(std::vector<long long int>)':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:652:2: note: in expansion of macro 'fort'
  652 |  fort(0, pts.size() / 2) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:657:2: note: in expansion of macro 'fort'
  657 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:672:2: note: in expansion of macro 'fort'
  672 |  fort(2, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:679:2: note: in expansion of macro 'fort'
  679 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:682:2: note: in expansion of macro 'fort'
  682 |  fort(0, ans.size()) {
      |  ^~~~
strange_device.cpp: In member function 'void Pqueue::hpf()':
strange_device.cpp:704:17: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  704 |   while (cr * 2 < vals.size()) {
      |          ~~~~~~~^~~~~~~~~~~~~
strange_device.cpp:705:19: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<double, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  705 |    if (cr * 2 + 1 < vals.size() && vals[cr * 2 + 1].first < vals[cr * 2].first && vals[cr * 2 + 1].first < vals[cr].first) {
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:19:64: warning: comparison of integer expressions of different signedness: 'int63' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
      |                                                                ^
strange_device.cpp:21:30: note: in expansion of macro 'forl'
   21 | #define forn(name,start,end) forl(name,start,end,1)
      |                              ^~~~
strange_device.cpp:23:25: note: in expansion of macro 'forn'
   23 | #define fort(start,end) forn(i,start,end)
      |                         ^~~~
strange_device.cpp:909:3: note: in expansion of macro 'fort'
  909 |   fort(0, evnt.size()) {
      |   ^~~~
strange_device.cpp: In function 'void setIO(std::string)':
strange_device.cpp:486:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  486 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:487:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  487 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 6 ms 976 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 976 KB Output is correct
17 Correct 67 ms 4448 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 432 ms 33356 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 571 ms 33168 KB Output is correct
3 Correct 596 ms 33252 KB Output is correct
4 Correct 579 ms 33296 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 571 ms 33168 KB Output is correct
3 Correct 596 ms 33252 KB Output is correct
4 Correct 579 ms 33296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 584 ms 33260 KB Output is correct
7 Correct 577 ms 33184 KB Output is correct
8 Correct 605 ms 33296 KB Output is correct
9 Correct 667 ms 33160 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 571 ms 33168 KB Output is correct
3 Correct 596 ms 33252 KB Output is correct
4 Correct 579 ms 33296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 55 ms 4480 KB Output is correct
7 Correct 58 ms 4440 KB Output is correct
8 Correct 55 ms 4472 KB Output is correct
9 Correct 57 ms 4448 KB Output is correct
10 Correct 53 ms 4536 KB Output is correct
11 Correct 57 ms 4548 KB Output is correct
12 Correct 54 ms 4496 KB Output is correct
13 Correct 61 ms 4488 KB Output is correct
14 Correct 55 ms 4452 KB Output is correct
15 Correct 64 ms 4520 KB Output is correct
16 Correct 61 ms 4488 KB Output is correct
17 Correct 56 ms 4564 KB Output is correct
18 Correct 591 ms 33172 KB Output is correct
19 Correct 587 ms 33268 KB Output is correct
20 Correct 693 ms 33308 KB Output is correct
21 Correct 64 ms 4548 KB Output is correct
22 Correct 51 ms 4520 KB Output is correct
23 Correct 167 ms 16860 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 64 ms 4520 KB Output is correct
3 Correct 62 ms 4540 KB Output is correct
4 Correct 711 ms 33276 KB Output is correct
5 Correct 60 ms 4540 KB Output is correct
6 Correct 62 ms 4516 KB Output is correct
7 Correct 61 ms 4492 KB Output is correct
8 Correct 67 ms 4544 KB Output is correct
9 Correct 72 ms 4448 KB Output is correct
10 Correct 63 ms 4544 KB Output is correct
11 Correct 60 ms 4444 KB Output is correct
12 Correct 55 ms 4480 KB Output is correct
13 Correct 62 ms 4492 KB Output is correct
14 Correct 668 ms 33272 KB Output is correct
15 Correct 66 ms 4540 KB Output is correct
16 Correct 553 ms 33156 KB Output is correct
17 Correct 574 ms 33340 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 860 KB Output is correct
3 Correct 6 ms 976 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 976 KB Output is correct
17 Correct 67 ms 4448 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -