oj.uz

답안 #409329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409329 2021-05-20T15:09:33 Z inbarin 이상한 기계 (APIO19_strange_device) C++14
65 / 100
 708 ms 33936 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) {
	__int128 c = ((__int128)a) * ((__int128)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 >= 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:905:3: note: in expansion of macro 'fort'
  905 |   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 1232 KB Output is correct
3 Correct 7 ms 1228 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 312 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 7 ms 1288 KB Output is correct
17 Correct 66 ms 5180 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 312 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 411 ms 33904 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 578 ms 33664 KB Output is correct
3 Correct 597 ms 33704 KB Output is correct
4 Correct 563 ms 33744 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 578 ms 33664 KB Output is correct
3 Correct 597 ms 33704 KB Output is correct
4 Correct 563 ms 33744 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 592 ms 33824 KB Output is correct
7 Correct 583 ms 33820 KB Output is correct
8 Correct 576 ms 33936 KB Output is correct
9 Correct 660 ms 33812 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 578 ms 33664 KB Output is correct
3 Correct 597 ms 33704 KB Output is correct
4 Correct 563 ms 33744 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 58 ms 5164 KB Output is correct
7 Correct 58 ms 5140 KB Output is correct
8 Correct 58 ms 5164 KB Output is correct
9 Correct 59 ms 5180 KB Output is correct
10 Correct 54 ms 5104 KB Output is correct
11 Correct 57 ms 5076 KB Output is correct
12 Correct 55 ms 5184 KB Output is correct
13 Correct 61 ms 5176 KB Output is correct
14 Correct 55 ms 5076 KB Output is correct
15 Correct 66 ms 5112 KB Output is correct
16 Correct 62 ms 5100 KB Output is correct
17 Correct 57 ms 5180 KB Output is correct
18 Correct 603 ms 33880 KB Output is correct
19 Correct 556 ms 33424 KB Output is correct
20 Correct 692 ms 33780 KB Output is correct
21 Correct 63 ms 5180 KB Output is correct
22 Correct 51 ms 5216 KB Output is correct
23 Correct 168 ms 17492 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 63 ms 5108 KB Output is correct
3 Correct 61 ms 5076 KB Output is correct
4 Correct 708 ms 33332 KB Output is correct
5 Correct 63 ms 5176 KB Output is correct
6 Correct 62 ms 5088 KB Output is correct
7 Correct 61 ms 5116 KB Output is correct
8 Correct 63 ms 5176 KB Output is correct
9 Correct 59 ms 5180 KB Output is correct
10 Correct 64 ms 5068 KB Output is correct
11 Correct 62 ms 5164 KB Output is correct
12 Correct 56 ms 5180 KB Output is correct
13 Correct 64 ms 5132 KB Output is correct
14 Correct 687 ms 33900 KB Output is correct
15 Correct 63 ms 5180 KB Output is correct
16 Correct 547 ms 33296 KB Output is correct
17 Correct 571 ms 33692 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 1232 KB Output is correct
3 Correct 7 ms 1228 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 312 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 7 ms 1288 KB Output is correct
17 Correct 66 ms 5180 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 -