oj.uz

Submission #677027

# Submission time Handle Problem Language Result Execution time Memory
677027 2023-01-02T06:58:36 Z badont Specijacija (COCI20_specijacija) C++17
110 / 110
 2846 ms 144772 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 137292 KB Output is correct
2 Correct 16 ms 10452 KB Output is correct
3 Correct 295 ms 138228 KB Output is correct
4 Correct 170 ms 72332 KB Output is correct
5 Correct 287 ms 138240 KB Output is correct
6 Correct 85 ms 41028 KB Output is correct
7 Correct 194 ms 138228 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 137292 KB Output is correct
2 Correct 16 ms 10452 KB Output is correct
3 Correct 295 ms 138228 KB Output is correct
4 Correct 170 ms 72332 KB Output is correct
5 Correct 287 ms 138240 KB Output is correct
6 Correct 85 ms 41028 KB Output is correct
7 Correct 194 ms 138228 KB Output is correct
8 Correct 360 ms 3804 KB Output is correct
9 Correct 307 ms 3360 KB Output is correct
10 Correct 363 ms 3860 KB Output is correct
11 Correct 205 ms 2640 KB Output is correct
12 Correct 361 ms 3816 KB Output is correct
13 Correct 256 ms 2948 KB Output is correct
14 Correct 374 ms 4412 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 137292 KB Output is correct
2 Correct 16 ms 10452 KB Output is correct
3 Correct 295 ms 138228 KB Output is correct
4 Correct 170 ms 72332 KB Output is correct
5 Correct 287 ms 138240 KB Output is correct
6 Correct 85 ms 41028 KB Output is correct
7 Correct 194 ms 138228 KB Output is correct
8 Correct 360 ms 3804 KB Output is correct
9 Correct 307 ms 3360 KB Output is correct
10 Correct 363 ms 3860 KB Output is correct
11 Correct 205 ms 2640 KB Output is correct
12 Correct 361 ms 3816 KB Output is correct
13 Correct 256 ms 2948 KB Output is correct
14 Correct 374 ms 4412 KB Output is correct
15 Correct 2761 ms 143352 KB Output is correct
16 Correct 1488 ms 30952 KB Output is correct
17 Correct 2700 ms 143380 KB Output is correct
18 Correct 1558 ms 31664 KB Output is correct
19 Correct 2846 ms 143268 KB Output is correct
20 Correct 1396 ms 28344 KB Output is correct
21 Correct 2506 ms 144772 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2731 ms 142500 KB Output is correct
2 Correct 2082 ms 69688 KB Output is correct
3 Correct 2745 ms 143580 KB Output is correct
4 Correct 2067 ms 67444 KB Output is correct
5 Correct 2757 ms 143180 KB Output is correct
6 Correct 2203 ms 75368 KB Output is correct
7 Correct 2495 ms 144728 KB Output is correct