oj.uz

Submission #765242

# Submission time Handle Problem Language Result Execution time Memory
765242 2023-06-24T09:44:38 Z NothingXD Game (IOI13_game) C++17
100 / 100
 3054 ms 100164 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

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

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 3e5 + 10;

vector<ll> seg[maxn << 2];
vector<pll> val[maxn << 2];

void build(vector<ll> &seg, vector<pll> &val, int v, int l, int r){
	if (l + 1 == r){
		seg[v] = val[l].S;
		return;
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	build(seg, val, lc, l, mid);
	build(seg, val, rc, mid, r);
	seg[v] = gcd(seg[lc], seg[rc]);
}

void change(vector<ll> &seg, int v, int l, int r, int idx, ll val){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		seg[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	change(seg, lc, l, mid, idx, val);
	change(seg, rc, mid, r, idx, val);
	seg[v] = gcd(seg[lc], seg[rc]);
}

ll get(vector<ll> &seg, int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	return gcd(get(seg, lc, l, mid, ql, qr),
			get(seg, rc, mid, r, ql, qr));
}

vector<pll> num[maxn];

void d2build(int v, int l, int r){
	val[v].clear();
	if (l + 1 == r){
		for (auto x: num[l]) val[v].push_back(x);
	}
	else{
		int mid = (l + r) >> 1;
		int lc = v << 1;
		int rc = lc | 1;
		d2build(lc, l, mid);
		d2build(rc, mid, r);
		int ptl = 0, ptr = 0;
		while(ptl < val[lc].size() || ptr < val[rc].size()){
			if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
				val[v].push_back(val[lc][ptl]);
				ptl++;
			}
			else{
				val[v].push_back(val[rc][ptr]);
				ptr++;
			}
		}
	}
	seg[v].resize(4 * val[v].size() + 1);
	build(seg[v], val[v], 1, 0, val[v].size());
}

void d2change(int v, int l, int r, int idx, ll ptr, ll prval, ll nwval){
	if (idx < l || r <= idx) return;
	int idx2 = lower_bound(all(val[v]), MP(ptr, prval)) - val[v].begin();
	val[v][idx2].S = nwval;
	change(seg[v], 1, 0, val[v].size(), idx2, nwval);
	if (l + 1 == r) return;
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	d2change(lc, l, mid, idx, ptr, prval, nwval);
	d2change(rc, mid, r, idx, ptr, prval, nwval);
}

ll d2get(int v, int l, int r, int qu, int qd, ll ql, ll qr){
	if (qd <= l || r <= qu) return 0;
	if (qu <= l && r <= qd){
		int L = lower_bound(all(val[v]), MP(ql, 0ll)) - val[v].begin();
		int R = lower_bound(all(val[v]), MP(qr, 0ll)) - val[v].begin();
		return get(seg[v], 1, 0, val[v].size(), L, R);
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	return gcd(d2get(lc, l, mid, qu, qd, ql, qr),
			d2get(rc, mid, r, qu, qd, ql, qr));
}

const int sq = 1200;

vector<pair<pii,ll>> p1, p2;
vector<int> numx;

void init(int R, int C) {
    // ok :/
}

void reset(){
	for (int i = 0; i < numx.size(); i++) num[i].clear();
	numx.clear();
	for (auto x: p2) p1.push_back(x);
	sort(all(p1));
	p2.clear();
	int ptr = 0;
	numx.push_back(p1[0].F.F);
	num[0].push_back(MP(p1[0].F.S, p1[0].S));
	for (int i = 1; i < p1.size(); i++){
		if (p1[i].F.F != p1[i-1].F.F){
			ptr++;
			numx.push_back(p1[i].F.F);
		}
		num[ptr].push_back(MP(p1[i].F.S, p1[i].S));
	}
	d2build(1, 0, numx.size());
}

void update(int P, int Q, long long K) {
    int idx = lower_bound(all(p1), MP(MP(P,Q), 0ll)) - p1.begin();
	if (idx != p1.size() && p1[idx].F == MP(P,Q)){
		int idx2 = lower_bound(all(numx), P) - numx.begin();
		d2change(1, 0, numx.size(), idx2, Q, p1[idx].S, K);
		p1[idx].S = K;
		return;
	}
	for (int i = 0; i < p2.size(); i++){
		if (p2[i].F == MP(P, Q)){
			p2[i].S = K;
			return;
		}
	}
	p2.push_back(MP(MP(P, Q), K));
	if (p2.size() == sq) reset();
}

long long calculate(int P, int Q, int U, int V) {
    int l = lower_bound(all(numx), P) - numx.begin();
	int r = lower_bound(all(numx), U+1) - numx.begin();
	ll res = d2get(1, 0, numx.size(), l, r, Q, V+1);
	for (auto [x, y]: p2){
		if (P <= x.F && x.F <= U && Q <= x.S && x.S <= V) res = gcd(res, y);
	}
    return res;
}

Compilation message

game.cpp: In function 'void d2build(int, int, int)':
game.cpp:82:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(ptl < val[lc].size() || ptr < val[rc].size()){
      |         ~~~~^~~~~~~~~~~~~~~~
game.cpp:82:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(ptl < val[lc].size() || ptr < val[rc].size()){
      |                                 ~~~~^~~~~~~~~~~~~~~~
game.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
      |        ~~~~^~~~~~~~~~~~~~~~~
game.cpp:83:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    if (ptr == val[rc].size() || (ptl < val[lc].size() && val[lc][ptl] < val[rc][ptr])){
      |                                  ~~~~^~~~~~~~~~~~~~~~
game.cpp: In function 'void reset()':
game.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for (int i = 0; i < numx.size(); i++) num[i].clear();
      |                  ~~^~~~~~~~~~~~~
game.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 1; i < p1.size(); i++){
      |                  ~~^~~~~~~~~~~
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:154:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  if (idx != p1.size() && p1[idx].F == MP(P,Q)){
      |      ~~~~^~~~~~~~~~~~
game.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for (int i = 0; i < p2.size(); i++){
      |                  ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63700 KB Output is correct
2 Correct 26 ms 63688 KB Output is correct
3 Correct 27 ms 63700 KB Output is correct
4 Correct 26 ms 63700 KB Output is correct
5 Correct 26 ms 63636 KB Output is correct
6 Correct 25 ms 63708 KB Output is correct
7 Correct 26 ms 63656 KB Output is correct
8 Correct 25 ms 63688 KB Output is correct
9 Correct 30 ms 63612 KB Output is correct
10 Correct 32 ms 63596 KB Output is correct
11 Correct 28 ms 63664 KB Output is correct
12 Correct 27 ms 63692 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63700 KB Output is correct
2 Correct 36 ms 63644 KB Output is correct
3 Correct 27 ms 63692 KB Output is correct
4 Correct 1590 ms 71648 KB Output is correct
5 Correct 1106 ms 71996 KB Output is correct
6 Correct 777 ms 68524 KB Output is correct
7 Correct 628 ms 68240 KB Output is correct
8 Correct 618 ms 67072 KB Output is correct
9 Correct 697 ms 68048 KB Output is correct
10 Correct 631 ms 67984 KB Output is correct
11 Correct 26 ms 63700 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63576 KB Output is correct
2 Correct 27 ms 63644 KB Output is correct
3 Correct 26 ms 63696 KB Output is correct
4 Correct 31 ms 63604 KB Output is correct
5 Correct 33 ms 63604 KB Output is correct
6 Correct 26 ms 63692 KB Output is correct
7 Correct 29 ms 63576 KB Output is correct
8 Correct 26 ms 63700 KB Output is correct
9 Correct 27 ms 63596 KB Output is correct
10 Correct 26 ms 63688 KB Output is correct
11 Correct 26 ms 63700 KB Output is correct
12 Correct 1929 ms 75692 KB Output is correct
13 Correct 2995 ms 69820 KB Output is correct
14 Correct 626 ms 65268 KB Output is correct
15 Correct 3050 ms 70876 KB Output is correct
16 Correct 1838 ms 73016 KB Output is correct
17 Correct 815 ms 68600 KB Output is correct
18 Correct 1093 ms 73536 KB Output is correct
19 Correct 1062 ms 73560 KB Output is correct
20 Correct 1033 ms 72892 KB Output is correct
21 Correct 33 ms 63708 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63564 KB Output is correct
2 Correct 34 ms 63672 KB Output is correct
3 Correct 32 ms 63648 KB Output is correct
4 Correct 33 ms 63636 KB Output is correct
5 Correct 33 ms 63576 KB Output is correct
6 Correct 32 ms 63700 KB Output is correct
7 Correct 31 ms 63700 KB Output is correct
8 Correct 40 ms 63696 KB Output is correct
9 Correct 34 ms 63700 KB Output is correct
10 Correct 33 ms 63692 KB Output is correct
11 Correct 31 ms 63696 KB Output is correct
12 Correct 1587 ms 72112 KB Output is correct
13 Correct 1085 ms 72404 KB Output is correct
14 Correct 807 ms 68744 KB Output is correct
15 Correct 641 ms 68396 KB Output is correct
16 Correct 627 ms 67160 KB Output is correct
17 Correct 698 ms 68392 KB Output is correct
18 Correct 633 ms 68164 KB Output is correct
19 Correct 1922 ms 75692 KB Output is correct
20 Correct 2921 ms 69676 KB Output is correct
21 Correct 597 ms 64844 KB Output is correct
22 Correct 2960 ms 71036 KB Output is correct
23 Correct 1829 ms 72968 KB Output is correct
24 Correct 821 ms 68596 KB Output is correct
25 Correct 1066 ms 73488 KB Output is correct
26 Correct 1045 ms 73660 KB Output is correct
27 Correct 1006 ms 72844 KB Output is correct
28 Correct 757 ms 74152 KB Output is correct
29 Correct 2003 ms 77372 KB Output is correct
30 Correct 2661 ms 73916 KB Output is correct
31 Correct 2736 ms 71688 KB Output is correct
32 Correct 612 ms 65064 KB Output is correct
33 Correct 1062 ms 64972 KB Output is correct
34 Correct 1847 ms 80628 KB Output is correct
35 Correct 853 ms 79300 KB Output is correct
36 Correct 1170 ms 84784 KB Output is correct
37 Correct 1079 ms 84804 KB Output is correct
38 Correct 1071 ms 84588 KB Output is correct
39 Correct 979 ms 81760 KB Output is correct
40 Correct 33 ms 63700 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63620 KB Output is correct
2 Correct 31 ms 63700 KB Output is correct
3 Correct 34 ms 63648 KB Output is correct
4 Correct 33 ms 63660 KB Output is correct
5 Correct 38 ms 63620 KB Output is correct
6 Correct 33 ms 63692 KB Output is correct
7 Correct 33 ms 63640 KB Output is correct
8 Correct 32 ms 63656 KB Output is correct
9 Correct 31 ms 63648 KB Output is correct
10 Correct 31 ms 63632 KB Output is correct
11 Correct 31 ms 63700 KB Output is correct
12 Correct 1578 ms 72036 KB Output is correct
13 Correct 1083 ms 72436 KB Output is correct
14 Correct 779 ms 68756 KB Output is correct
15 Correct 638 ms 68516 KB Output is correct
16 Correct 617 ms 67220 KB Output is correct
17 Correct 685 ms 68308 KB Output is correct
18 Correct 642 ms 68068 KB Output is correct
19 Correct 1924 ms 75676 KB Output is correct
20 Correct 2909 ms 69768 KB Output is correct
21 Correct 613 ms 64880 KB Output is correct
22 Correct 2947 ms 70796 KB Output is correct
23 Correct 1830 ms 73020 KB Output is correct
24 Correct 809 ms 68576 KB Output is correct
25 Correct 1072 ms 73752 KB Output is correct
26 Correct 1028 ms 73568 KB Output is correct
27 Correct 998 ms 72832 KB Output is correct
28 Correct 742 ms 74232 KB Output is correct
29 Correct 1997 ms 77504 KB Output is correct
30 Correct 2609 ms 73976 KB Output is correct
31 Correct 2724 ms 71432 KB Output is correct
32 Correct 613 ms 64836 KB Output is correct
33 Correct 1059 ms 64748 KB Output is correct
34 Correct 1859 ms 80576 KB Output is correct
35 Correct 861 ms 79300 KB Output is correct
36 Correct 1157 ms 84676 KB Output is correct
37 Correct 1072 ms 84880 KB Output is correct
38 Correct 1069 ms 84248 KB Output is correct
39 Correct 892 ms 98088 KB Output is correct
40 Correct 2551 ms 100164 KB Output is correct
41 Correct 3054 ms 94940 KB Output is correct
42 Correct 2946 ms 86080 KB Output is correct
43 Correct 2067 ms 94768 KB Output is correct
44 Correct 1342 ms 73736 KB Output is correct
45 Correct 998 ms 81496 KB Output is correct
46 Correct 1540 ms 98924 KB Output is correct
47 Correct 1528 ms 98844 KB Output is correct
48 Correct 1625 ms 98524 KB Output is correct
49 Correct 34 ms 63688 KB Output is correct