Submission #677027

#	Time	Username	Problem	Language	Result	Execution time	Memory
677027		badont	Specijacija (COCI20_specijacija)	C++17	110 / 110	2846 ms	144772 KiB

Main

#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

template<class T>
struct node {
	node* l;
	node* r;
	T val = T(0);
 
	node(T val) : l(nullptr), r(nullptr), val(val) {}
	node(node* l, node* r) : l(l), r(r), val(0) {
		if (l) val += l->val;
		if (r) val += r->val;
	}
};
 
template<class T>
struct sex {
 
	LL nVal = 0;
 
	node<T>* build(vector<T>& a, int zl, int zr) {
		if (zl == zr) return new node<T>(a[zl - 1]);
		int m = (zl + zr) >> 1;
		return new node<T>(build(a, zl, m), build(a, m + 1, zr));
	} 
 
	node<T>* build(vector<T>& a) {
		this->nVal = (int)a.size();
		return build(a, 1, (int)a.size());
	}
 
	node<T>* build(int n) {
		this->nVal = n;
		vector<T> res(n, 0);
		return build(res, 1, n);
	}
 
	node<T>* upd(node<T>* c, int zl, int zr, const int& pos, const T& new_val) {
		//debug(c->val, zl, zr, pos, new_val);
		if (zl == zr) {
			//debug(zl, new_val);
			return new node<T>(new_val);
		}
		int m = (zl + zr) >> 1;
		if (pos <= m)
			return new node<T>(upd(c->l, zl, m, pos, new_val), c->r);
		else  
			return new node<T>(c->l, upd(c->r, m + 1, zr, pos, new_val));
	}
 
	T query(node<T>* c, int zl, int zr, int l, int r) {
		if (c == nullptr || l > r) 
			return T(0);
 
		if (l <= zl && zr <= r) 
			return c->val;
 
		int m = (zl + zr) >> 1;
		T ret = query(c->l, zl, m, l, min(r, m)) + 
				query(c->r, m + 1, zr, max(l, m + 1), r);
 
		return ret;
	};

	int walk(node<T>* c, int zl, int zr, T quota) {
		if (c == nullptr || c->val < quota)
			return -1;

		if (zl == zr) return zl;

		int m = (zl + zr) >> 1;
		T onLeft = c->l->val;

		//debug(zl, zr, quota, c->val, onLeft);

		if (quota <= onLeft) return walk(c->l, zl, m, quota);
		else return walk(c->r, m + 1, zr, quota - onLeft);
	};

	int walk(node<T>* c, T quota) { return walk(c, 1, nVal, quota); }
	T query(node<T>* c, int l, int r) { return query(c, 1, nVal, l, r); }
};

void solve() {
	LL n, q, t;
	cin >> n >> q >> t;

	vector<LL> bottom(n + 1, 1);
	sex<LL> tree;
	node<LL>* ptr = tree.build(bottom);
	vector<node<LL>*> roots(n + 1, ptr);
	vector<LL> a(n);
	for (auto& u : a)
		cin >> u;

	//debug(tree.walk(roots[n], 4));

	for (LL level = n - 1; level >= 0; level--) {
		LL withTwo = a[level] - ((level) * (level + 1)) / 2;
		//debug(withTwo);
		assert(withTwo <= level + 1);
		LL toZero = tree.walk(roots[level + 1], withTwo + 1);
		//assert(toZero != -1);

		roots[level] = tree.upd(roots[level + 1], 1, n + 1, toZero, 0);
		//debug(tree.query(roots[level], 1, n + 1));
	}

	vector<LL> lt(n + 1);
	FOR (i, n) {
		lt[i] = ((LL)(i) * (i + 1)) / 2;
 	}

 	//debug(lt);

	//debug(roots);
	LL pans = 0;
	while (q--) {
		LL x, y;
		cin >> x >> y;
		x = ((x - 1) + t * pans) % (((n + 1) * (n + 2))/2) + 1;
		y = ((y - 1) + t * pans) % (((n + 1) * (n + 2))/2) + 1;

		int lx = lower_bound(all(lt), x) - lt.begin() - 1;
		int ly = lower_bound(all(lt), y) - lt.begin() - 1;

		//debug(lx, ly);
		if (lx < ly) {
			//force lx deeper
			swap(lx, ly);
			swap(x, y);
		}

		int ix = x - lt[lx], iy = y - lt[ly];
		int lmx = tree.walk(roots[lx], ix);

		if (tree.query(roots[ly], 1, lmx) == iy) {
			pans = y;
			cout << y << "\n";
			continue;
		}

		int lmy = tree.walk(roots[ly], iy);
		//debug(lmx, lmy);
		//debug(ix, iy);
		{
			//jump from lmx, lmy
			auto equalJumps = [&](int jump) -> LL {
				LL res = -1;

				int jx = tree.query(roots[n - jump], 1, lmx);
				int jy = tree.query(roots[n - jump], 1, lmy);
				if (jx != jy) return -1;

				res = jx;
				res += lt[n - jump];
				return res;
			};

			int lo = 1, hi = n, mid;
			while (lo < hi) {
				mid = (lo + hi) >> 1;
				if (equalJumps(mid) != -1) hi = mid;
				else lo = mid + 1;
			}

			pans = equalJumps(lo);
			cout << pans << '\n';
		}
	}
	//cout << 69 << '\n';*/
}	

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

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60