oj.uz

Submission #901597

# Submission time Handle Problem Language Result Execution time Memory
901597 2024-01-09T16:24:08 Z trMatherz Game (IOI13_game) C++17
100 / 100
 2163 ms 82348 KB 
//#include <iostream> //cin, cout
#include "game.h"
/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>



//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRe(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define Fe(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)
int Y, X;
struct Xnode{
	Xnode(int x, int y) : l(x), r(y), v(0), lc(NULL), rc(NULL) {}
	int l, r;
	ll v;
	Xnode *lc, *rc;
};
struct Ynode{
	Ynode() : kid(1, X), lc(NULL), rc(NULL) {}
	Xnode kid;
	Ynode *lc, *rc;
} *root;


ll gcd2(ll x, ll y){
	if(y == 0) return x;
	return gcd2(y, x % y);
}



void upd2(Xnode *cur, int x, ll k){
	int l = cur->l, r = cur->r, m = (l + r) / 2;
	if(l == r) {
		cur->v = k;
		return;
	}
	Xnode **kid = &(x <= m ? cur->lc : cur->rc);
	if(*kid == NULL){
		*kid = new Xnode(x, x);
		(*kid)->v = k;
	} else if((*kid)->l <= x && x <= (*kid)->r){
		upd2(*kid, x, k);
	} else {
		do{
			if(x <= m) r = m;
			else l = m + 1;
			m = (r + l) / 2;
		} while ((x <= m) == ((*kid)->r <= m));
		Xnode *ncur = new Xnode(l, r);
		if((*kid)->r <= m) ncur->lc = *kid;
		else ncur->rc = *kid;
		*kid = ncur;
		upd2(*kid, x, k);
	}
	cur->v = gcd2(cur->lc ? cur->lc->v : 0, cur->rc ? cur->rc->v : 0);
}

ll get2(Xnode *cur, int rl, int rr){
	if(cur == NULL || cur->l > rr || cur->r < rl) return 0;
	if(rl <= cur->l && cur->r <= rr) return cur->v;
	return gcd2(get2(cur->lc, rl, rr), get2(cur->rc, rl, rr));
}


void upd1(Ynode *cur, int l, int r, int y, int x, ll k){
	if(l == r) {
		upd2(&cur->kid, x, k);
		return;
	}
	int m = (l + r) / 2;
	if(y <= m){
		if(cur->lc == NULL) cur->lc = new Ynode;
		upd1(cur->lc, l, m, y, x, k);
	} else {
		if(cur->rc == NULL) cur->rc = new Ynode;
		upd1(cur->rc, m + 1, r, y, x, k);
	}
	ll z = gcd2(cur->lc ? get2(&cur->lc->kid, x, x) : 0, cur->rc ? get2(&cur->rc->kid, x, x) : 0);
	upd2(&cur->kid, x, z);
}

ll get1(Ynode *cur, int l, int r, int rl, int rr, int xl, int xr){
	if(cur == NULL || r < rl || l > rr) return 0;
	if(rl <= l && r <= rr) return get2(&cur->kid, xl, xr);
	int m = (l + r) / 2;
	return gcd2(get1(cur->lc, l, m, rl, rr, xl, xr), get1(cur->rc, m + 1, r, rl, rr, xl, xr));
}



void init(int R, int C){
	Y = R, X = C;
	root = new Ynode;
}

void update(int P, int Q, ll K){
	P++; Q++;
	upd1(root, 1, Y, P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
	P++; Q++; U++; V++;
	return get1(root, 1, Y, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 373 ms 8484 KB Output is correct
5 Correct 242 ms 8532 KB Output is correct
6 Correct 315 ms 5500 KB Output is correct
7 Correct 353 ms 5236 KB Output is correct
8 Correct 274 ms 4032 KB Output is correct
9 Correct 335 ms 5108 KB Output is correct
10 Correct 305 ms 5208 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 586 ms 11496 KB Output is correct
13 Correct 1064 ms 4960 KB Output is correct
14 Correct 178 ms 1036 KB Output is correct
15 Correct 1214 ms 6192 KB Output is correct
16 Correct 141 ms 10032 KB Output is correct
17 Correct 488 ms 6120 KB Output is correct
18 Correct 827 ms 10216 KB Output is correct
19 Correct 681 ms 10324 KB Output is correct
20 Correct 623 ms 9812 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 355 ms 8220 KB Output is correct
13 Correct 239 ms 8748 KB Output is correct
14 Correct 306 ms 5456 KB Output is correct
15 Correct 350 ms 5160 KB Output is correct
16 Correct 229 ms 3920 KB Output is correct
17 Correct 337 ms 5204 KB Output is correct
18 Correct 304 ms 4948 KB Output is correct
19 Correct 613 ms 11548 KB Output is correct
20 Correct 1096 ms 4916 KB Output is correct
21 Correct 180 ms 848 KB Output is correct
22 Correct 1229 ms 6484 KB Output is correct
23 Correct 140 ms 9804 KB Output is correct
24 Correct 479 ms 6224 KB Output is correct
25 Correct 827 ms 10276 KB Output is correct
26 Correct 688 ms 10372 KB Output is correct
27 Correct 647 ms 9808 KB Output is correct
28 Correct 320 ms 43092 KB Output is correct
29 Correct 879 ms 45292 KB Output is correct
30 Correct 1612 ms 35252 KB Output is correct
31 Correct 1438 ms 28656 KB Output is correct
32 Correct 257 ms 10164 KB Output is correct
33 Correct 357 ms 10940 KB Output is correct
34 Correct 192 ms 39252 KB Output is correct
35 Correct 615 ms 26960 KB Output is correct
36 Correct 1172 ms 43232 KB Output is correct
37 Correct 940 ms 43604 KB Output is correct
38 Correct 894 ms 42972 KB Output is correct
39 Correct 763 ms 35788 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 356 ms 8252 KB Output is correct
13 Correct 247 ms 8700 KB Output is correct
14 Correct 305 ms 5456 KB Output is correct
15 Correct 358 ms 5244 KB Output is correct
16 Correct 228 ms 3844 KB Output is correct
17 Correct 350 ms 5328 KB Output is correct
18 Correct 299 ms 4952 KB Output is correct
19 Correct 580 ms 11604 KB Output is correct
20 Correct 1068 ms 5044 KB Output is correct
21 Correct 180 ms 848 KB Output is correct
22 Correct 1179 ms 6232 KB Output is correct
23 Correct 141 ms 9800 KB Output is correct
24 Correct 482 ms 6356 KB Output is correct
25 Correct 773 ms 10588 KB Output is correct
26 Correct 678 ms 10492 KB Output is correct
27 Correct 623 ms 9812 KB Output is correct
28 Correct 328 ms 43128 KB Output is correct
29 Correct 874 ms 45008 KB Output is correct
30 Correct 1620 ms 35356 KB Output is correct
31 Correct 1444 ms 28632 KB Output is correct
32 Correct 256 ms 10320 KB Output is correct
33 Correct 350 ms 10664 KB Output is correct
34 Correct 189 ms 39252 KB Output is correct
35 Correct 593 ms 27000 KB Output is correct
36 Correct 1144 ms 43184 KB Output is correct
37 Correct 896 ms 43828 KB Output is correct
38 Correct 944 ms 43112 KB Output is correct
39 Correct 413 ms 81092 KB Output is correct
40 Correct 1409 ms 82348 KB Output is correct
41 Correct 2163 ms 67156 KB Output is correct
42 Correct 1969 ms 52628 KB Output is correct
43 Correct 343 ms 76884 KB Output is correct
44 Correct 322 ms 10784 KB Output is correct
45 Correct 751 ms 35860 KB Output is correct
46 Correct 1617 ms 81136 KB Output is correct
47 Correct 1600 ms 80980 KB Output is correct
48 Correct 1562 ms 80760 KB Output is correct
49 Correct 0 ms 348 KB Output is correct