oj.uz

Submission #639555

# Submission time Handle Problem Language Result Execution time Memory
639555 2022-09-10T15:34:38 Z ghostwriter Strange Device (APIO19_strange_device) C++14
35 / 100
 3745 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int N = 1e6 + 1;
int n;
ll A, B, S = 0, L = 0;
pll a[N];
namespace subtask1 {
	map<pll, bool> d;
	void solve() {
		int rs = 0;
		FOR(i, 1, n) {
			ll l = a[i].st, r = a[i].nd;
			for (ll t = l; t <= r; ++t) {
				ll x = (t + t / B) % A, y = t % B;
				if (d.count({x, y})) continue;
				d[{x, y}] = 1;
				++rs;
			}
		}
		cout << rs;
	}
}
namespace subtask2 {
	ll rs = 0;
	void solve() {
		ll l = a[1].st, r = a[1].nd;
		ll C = A / gcd(A, B + 1);
		ll pr = max(r - (r % B - l % B + B) % B - 1, l - 1);
		rs += (r - pr) * min((r - l + 1) / B + 1, C);
		rs += (min(B, r - l + 1) - r + pr) * min(r / B - l / B, C);
		cout << rs;
	}
}
struct Query {
	ll l, r, l1, r1;
	Query() {}
	Query(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {}
};
struct Event {
	bool type;
	ll t, l1, r1;
	Event() {}
	Event(bool type, ll t, ll l1, ll r1) : type(type), t(t), l1(l1), r1(r1) {}
};
bool cmp(Event &a, Event &b) {
	if (a.t != b.t) return a.t < b.t;
	return a.type < b.type;
}
namespace subtask3456 {
	const int T = 4e6 + 1;
	vector<Query> query;
	vector<Event> e;
	int tr[T], f[T];
	ll rs = 0;
	void upd(int i, int l, int r, int ql, int qr, int v) {
		if (r < ql || l > qr) return;
		if (ql <= l && r <= qr) {
			tr[i] += v;
			f[i] = (tr[i]? r - l + 1 : l != r? f[i * 2] + f[i * 2 + 1] : 0);
			return;
		}
		int mid = l + (r - l) / 2;
		upd(i * 2, l, mid, ql, qr, v);
		upd(i * 2 + 1, mid + 1, r, ql, qr, v);
		f[i] = (tr[i]? r - l + 1 : l != r? f[i * 2] + f[i * 2 + 1] : 0);
	}
	void solve() {
		ll C = A / gcd(A, B + 1);
		FOR(i, 1, n) {
			ll l = a[i].st, r = a[i].nd;
			if ((r - l + 1) >= B * C) {
				cout << B * C;
				return;
			}
		}
		FOR(i, 1, n) {
			ll l = a[i].st, r = a[i].nd;
			if (l % B != 0) {
				ll nr = min(r, l + B - 1 - l % B);
				ll l1 = l / B % C, r1 = nr / B % C;
				if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
				else {
					query.pb(Query(l1, C - 1, l % B, nr % B));
					query.pb(Query(0, r1, l % B, nr % B));
				}
				l = nr + 1;
			}
			if (l > r) continue;
			if (r % B != B - 1) {
				ll nr = r - (r % B) - 1;
				if (l <= nr) {
					ll l1 = l / B % C, r1 = nr / B % C;
					if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
					else {
						query.pb(Query(l1, C - 1, l % B, nr % B));
						query.pb(Query(0, r1, l % B, nr % B));
					}
					l = nr + 1;
				}
			}
			if (l > r) continue;
			ll l1 = l / B % C, r1 = r / B % C;
			if (l1 <= r1) query.pb(Query(l1, r1, l % B, r % B));
			else {
				query.pb(Query(l1, C - 1, l % B, r % B));
				query.pb(Query(0, r1, l % B, r % B));
			}
		}
		EACH(i, query) {
			ll l = i.l, r = i.r, l1 = i.l1, r1 = i.r1;
			e.pb(Event(0, l, l1, r1));
			e.pb(Event(1, r, l1, r1));
		}
		sort(all(e), cmp);
		int m = sz(e);
		ll pre = e[0].t - 1;
		FOR(i, 0, m - 1) {
			bool type = e[i].type;
			ll t = e[i].t, l1 = e[i].l1, r1 = e[i].r1;
			if (type == 1 && (i == 0 || e[i - 1].type == 0 || e[i - 1].t != t)) {
				rs += f[1] * (t - pre);
			}
			upd(1, 0, B - 1, l1, r1, type == 0? 1 : -1);
			if (type == 0 && i > 0 && e[i - 1].type == 1) pre = e[i].t - 1;
			if (i < m - 1 && e[i + 1].type == type && e[i + 1].t == t) continue;
			if (type == 0) {
				rs += f[1] * (t - pre);
			}
			pre = t;
		}
		cout << rs;
	}
}
namespace subtask78 {
	struct Node {
		ll mid;
		int cnt;
		ll mrk;
		Node *left, *right;
		Node() : mid(0), cnt(0), mrk(0), left(0), right(0) {}
		Node(ll mid, int cnt, ll mrk, Node *left, Node *right) : mid(mid), cnt(0), mrk(0), left(left), right(right) {}
	};
	vector<Query> query;
	vector<Event> e;
	ll rs = 0;
	Node *root;
	map<ll, bool> c;
	vll v;
	void build(Node *cur, ll nl, ll nr) {
		int l = lb(all(v), nl) - v.begin(), r = ub(all(v), nr) - v.begin() - 1;
		if (l > r) return;
		if (l == r) {
			if (nl == nr) return;
			if (nl == v[l]) {
				Node *left = new Node(0, 0, 0, 0, 0);
				Node *right = new Node(0, 0, 0, 0, 0);
				cur -> left = left;
				cur -> right = right;
				cur -> mid = v[l];
				build(cur -> left, nl, v[l]);
				build(cur -> right, v[l] + 1, nr);
				return;
			}
			if (nr == v[l]) {
				Node *left = new Node(0, 0, 0, 0, 0);
				Node *right = new Node(0, 0, 0, 0, 0);
				cur -> left = left;
				cur -> right = right;
				cur -> mid = v[l] - 1;
				build(cur -> left, nl, v[l] - 1);
				build(cur -> right, v[l], nr);
				return;
			}
			return;
		}
		int mid = (l + r) / 2;
		Node *left = new Node(0, 0, 0, 0, 0);
		Node *right = new Node(0, 0, 0, 0, 0);
		cur -> left = left;
		cur -> right = right;
		cur -> mid = v[mid];
		build(cur -> left, nl, v[mid]);
		build(cur -> right, v[mid] + 1, nr);
	}
	void upd(Node *cur, ll l, ll r, ll ql, ll qr, int v) {
		if (r < ql || l > qr) return;
		if (ql <= l && r <= qr) {
			cur -> cnt += v;
			cur -> mrk =
			(cur -> cnt? r - l + 1 : (cur -> left? cur -> left -> mrk : 0) + (cur -> right? cur -> right -> mrk : 0));
			return;
		}
		if (cur -> left) upd(cur -> left, l, cur -> mid, ql, qr, v);
		if (cur -> right) upd(cur -> right, cur -> mid + 1, r, ql, qr, v);
		cur -> mrk = (cur -> cnt? r - l + 1 : (cur -> left? cur -> left -> mrk : 0) + (cur -> right? cur -> right -> mrk : 0));
	}
	void solve() {
		ll C = A / gcd(A, B + 1);
		FOR(i, 1, n) {
			ll l = a[i].st, r = a[i].nd;
			if ((ldb)(r - l + 1) / C >= B) {
				cout << B * C;
				return;
			}
		}
		FOR(i, 1, n) {
			ll l = a[i].st, r = a[i].nd;
			if (l % B != 0) {
				ll nr = min(r, l + B - 1 - l % B);
				ll l1 = l / B % C, r1 = nr / B % C;
				if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
				else {
					query.pb(Query(l1, C - 1, l % B, nr % B));
					query.pb(Query(0, r1, l % B, nr % B));
				}
				l = nr + 1;
			}
			if (l > r) continue;
			if (r % B != B - 1) {
				ll nr = r - (r % B) - 1;
				if (l <= nr) {
					ll l1 = l / B % C, r1 = nr / B % C;
					if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
					else {
						query.pb(Query(l1, C - 1, l % B, nr % B));
						query.pb(Query(0, r1, l % B, nr % B));
					}
					l = nr + 1;
				}
			}
			if (l > r) continue;
			ll l1 = l / B % C, r1 = r / B % C;
			if (l1 <= r1) query.pb(Query(l1, r1, l % B, r % B));
			else {
				query.pb(Query(l1, C - 1, l % B, r % B));
				query.pb(Query(0, r1, l % B, r % B));
			}
		}
		EACH(i, query) {
			ll l = i.l, r = i.r, l1 = i.l1, r1 = i.r1;
			if (!c.count(l1)) {
				v.pb(l1);
				c[l1] = 1;
			}
			if (!c.count(r1)) {
				v.pb(r1);
				c[r1] = 1;
			}
			e.pb(Event(0, l, l1, r1));
			e.pb(Event(1, r, l1, r1));
		}
		sort(all(e), cmp);
		int m = sz(e);
		ll pre = e[0].t - 1;
		sort(all(v));
		root = new Node(0, 0, 0, 0, 0);
		build(root, v[0], v[sz(v) - 1]);
		FOR(i, 0, m - 1) {
			bool type = e[i].type;
			ll t = e[i].t, l1 = e[i].l1, r1 = e[i].r1;
			if (type == 1 && (i == 0 || e[i - 1].type == 0 || e[i - 1].t != t)) {
				rs += root -> mrk * (t - pre);
			}
			upd(root, v[0], v[sz(v) - 1], l1, r1, type == 0? 1 : -1);
			if (type == 0 && i > 0 && e[i - 1].type == 1) pre = e[i].t - 1;
			if (i < m - 1 && e[i + 1].type == type && e[i + 1].t == t) continue;
			if (type == 0) {
				rs += root -> mrk * (t - pre);
			}
			pre = t;
		}
		cout << rs;
	}
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> A >> B;
    FOR(i, 1, n) {
    	cin >> a[i].st >> a[i].nd;
    	S += a[i].nd - a[i].st + 1;
    	L = max(L, a[i].nd - a[i].st + 1);
    }
    // if (S <= 1e6) {
    // 	subtask1::solve();
    // 	return 0;
    // }
    // if (n == 1) {
    // 	subtask2::solve();
    // 	return 0;
    // }
    // if (B <= 1e6) {
    // 	subtask3456::solve();
    // 	return 0;
    // }
    subtask78::solve();
    return 0;
}
/*
2 920016 914385
34129 655405
1212938 1781362
*/

Compilation message

strange_device.cpp: In function 'void subtask1::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:44:3: note: in expansion of macro 'FOR'
   44 |   FOR(i, 1, n) {
      |   ^~~
strange_device.cpp: In function 'void subtask3456::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:102:3: note: in expansion of macro 'FOR'
  102 |   FOR(i, 1, n) {
      |   ^~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:109:3: note: in expansion of macro 'FOR'
  109 |   FOR(i, 1, n) {
      |   ^~~
strange_device.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
strange_device.cpp:142:3: note: in expansion of macro 'EACH'
  142 |   EACH(i, query) {
      |   ^~~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:150:3: note: in expansion of macro 'FOR'
  150 |   FOR(i, 0, m - 1) {
      |   ^~~
strange_device.cpp: In function 'void subtask78::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:232:3: note: in expansion of macro 'FOR'
  232 |   FOR(i, 1, n) {
      |   ^~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:239:3: note: in expansion of macro 'FOR'
  239 |   FOR(i, 1, n) {
      |   ^~~
strange_device.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
strange_device.cpp:272:3: note: in expansion of macro 'EACH'
  272 |   EACH(i, query) {
      |   ^~~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:291:3: note: in expansion of macro 'FOR'
  291 |   FOR(i, 0, m - 1) {
      |   ^~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
strange_device.cpp:313:5: note: in expansion of macro 'FOR'
  313 |     FOR(i, 1, n) {
      |     ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 12 ms 2408 KB Output is correct
3 Correct 13 ms 2512 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 799 ms 113160 KB Output is correct
3 Correct 814 ms 113056 KB Output is correct
4 Correct 774 ms 113088 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 799 ms 113160 KB Output is correct
3 Correct 814 ms 113056 KB Output is correct
4 Correct 774 ms 113088 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2058 ms 372648 KB Output is correct
7 Correct 782 ms 113088 KB Output is correct
8 Correct 1881 ms 372696 KB Output is correct
9 Correct 2256 ms 372748 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 799 ms 113160 KB Output is correct
3 Correct 814 ms 113056 KB Output is correct
4 Correct 774 ms 113088 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 116 ms 24688 KB Output is correct
7 Correct 193 ms 44212 KB Output is correct
8 Correct 182 ms 44232 KB Output is correct
9 Correct 177 ms 44204 KB Output is correct
10 Correct 114 ms 23844 KB Output is correct
11 Correct 181 ms 44220 KB Output is correct
12 Correct 178 ms 44260 KB Output is correct
13 Correct 215 ms 44240 KB Output is correct
14 Correct 263 ms 53504 KB Output is correct
15 Correct 227 ms 32892 KB Output is correct
16 Correct 311 ms 53632 KB Output is correct
17 Correct 416 ms 72760 KB Output is correct
18 Correct 2290 ms 372908 KB Output is correct
19 Correct 2097 ms 372832 KB Output is correct
20 Correct 2754 ms 372876 KB Output is correct
21 Correct 253 ms 44204 KB Output is correct
22 Correct 161 ms 44284 KB Output is correct
23 Correct 193 ms 49296 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 195 ms 31748 KB Output is correct
3 Correct 320 ms 53788 KB Output is correct
4 Correct 3745 ms 348188 KB Output is correct
5 Correct 340 ms 54428 KB Output is correct
6 Correct 335 ms 54304 KB Output is correct
7 Correct 322 ms 54320 KB Output is correct
8 Correct 293 ms 39112 KB Output is correct
9 Correct 337 ms 55600 KB Output is correct
10 Correct 323 ms 53644 KB Output is correct
11 Correct 261 ms 53524 KB Output is correct
12 Correct 276 ms 53560 KB Output is correct
13 Correct 248 ms 28208 KB Output is correct
14 Correct 2699 ms 274276 KB Output is correct
15 Correct 185 ms 22632 KB Output is correct
16 Runtime error 1735 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 12 ms 2408 KB Output is correct
3 Correct 13 ms 2512 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -