oj.uz

Submission #1080843

# Submission time Handle Problem Language Result Execution time Memory
1080843 2024-08-29T14:55:49 Z Gray Game (IOI13_game) C++17
63 / 100
 897 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct SegTree1D{
	struct Node{
		Node *left, *right;
		ll gcd;
		Node(){
			left=right=nullptr; gcd=0;
		}
		void update(int tl, int tr, int i, ll x, map<int, Node*> &leaves){
			if (tl==tr){
				gcd=x;
				leaves[tl]=this;
			}else{
				int tm = (tl+tr)/2;
				if (i<=tm) {
					if (!left) left=new Node();
					left->update(tl, tm, i, x, leaves);
				}else{
					if (!right) right=new Node();
					right->update(tm+1, tr, i, x, leaves);
				}
				gcd=0;
				if(left) gcd=__gcd(left->gcd, gcd);
				if (right) gcd=__gcd(right->gcd, gcd);
			}
		}
		ll query(int tl, int tr, int l, int r){
			if (tl==l and tr==r){
				return gcd;
			}else if (l>r) return 0;
			else{
				int tm = (tl+tr)/2;
				ll ret=0;
				if (left and l<=min(r, tm)) ret=__gcd(ret, left->query(tl, tm, l, min(r, tm)));
				if (right and max(l, tm+1)<=r) ret=__gcd(ret, right->query(tm+1, tr, max(l, tm+1), r));
				return ret;
			}
		}
	};
	map<int, Node*> leaves;
	Node * root;
	int rsz;
	SegTree1D(int N){
		rsz=N;
		root=new Node();
	}
	void update(int i, ll x){
		root->update(0, rsz-1, i, x, leaves);
	}
	ll query(int l, int r){
		return root->query(0, rsz-1, l, r);
	}
	ll getval(int ind){
		if (!leaves.count(ind)) return 0;
		return leaves[ind]->gcd;
	}
};
struct SegTree2D{
	struct mNode{
		mNode *left, *right;
		SegTree1D *val;
		int csz;
		mNode(int _csz){
			csz=_csz;
			left=right=nullptr;
			val = new SegTree1D(csz);
		}
		void update(int tl, int tr, int i, int j, ll x){
			if (tl==tr){
				val->update(j, x);
			}else{
				int tm = (tl+tr)/2;
				if (i<=tm){
					if (!left) left=new mNode(csz);
					left->update(tl, tm, i, j, x);
				}else{
					if (!right) right=new mNode(csz);
					right->update(tm+1, tr, i, j, x);
				}
				val->update(j, __gcd((left?left->val->getval(j):0), (right?right->val->getval(j):0)));
			}
		}
		ll query(int li, int ri, int lj, int rj, int tl, int tr){
			if (tl==li and tr==ri){
				return val->query(lj, rj);
			}else if (li>ri) return 0;
			else{
				ll ret=0;
				int tm = (tl+tr)/2;
				if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
				if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
				return ret;
			}
		}
	};
	mNode * root;
	ll csz, rsz;
	void init(int R, int C){
		rsz=R; csz=C;
		root = new mNode(csz);
	}
	void update(int i, int j, ll x){
		root->update(0, rsz-1, i, j, x);
	}
	ll query(int li, int ri, int lj, int rj){
		return root->query(li, ri, lj, rj, 0, rsz-1);
	}
} DS;
 
 
void init(int R, int C) {
	DS.init(R, C);
}
 
void update(int P, int Q, long long K) {
	DS.update(P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
	/* ... */
	return DS.query(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 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 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 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 1 ms 344 KB Output is correct
4 Correct 341 ms 19620 KB Output is correct
5 Correct 223 ms 19836 KB Output is correct
6 Correct 319 ms 17236 KB Output is correct
7 Correct 334 ms 16976 KB Output is correct
8 Correct 229 ms 12112 KB Output is correct
9 Correct 337 ms 16976 KB Output is correct
10 Correct 289 ms 16744 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 432 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 568 ms 25244 KB Output is correct
13 Correct 755 ms 12952 KB Output is correct
14 Correct 188 ms 5616 KB Output is correct
15 Correct 851 ms 16900 KB Output is correct
16 Correct 165 ms 28756 KB Output is correct
17 Correct 517 ms 19724 KB Output is correct
18 Correct 877 ms 30292 KB Output is correct
19 Correct 759 ms 30548 KB Output is correct
20 Correct 695 ms 29852 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 604 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 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 327 ms 19708 KB Output is correct
13 Correct 246 ms 19540 KB Output is correct
14 Correct 296 ms 17232 KB Output is correct
15 Correct 326 ms 16976 KB Output is correct
16 Correct 227 ms 12112 KB Output is correct
17 Correct 344 ms 17136 KB Output is correct
18 Correct 312 ms 16700 KB Output is correct
19 Correct 565 ms 24868 KB Output is correct
20 Correct 751 ms 13152 KB Output is correct
21 Correct 153 ms 5792 KB Output is correct
22 Correct 851 ms 16976 KB Output is correct
23 Correct 159 ms 28756 KB Output is correct
24 Correct 549 ms 19932 KB Output is correct
25 Correct 872 ms 30120 KB Output is correct
26 Correct 761 ms 30548 KB Output is correct
27 Correct 713 ms 29708 KB Output is correct
28 Runtime error 561 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 354 ms 19672 KB Output is correct
13 Correct 229 ms 19616 KB Output is correct
14 Correct 305 ms 17232 KB Output is correct
15 Correct 327 ms 16968 KB Output is correct
16 Correct 225 ms 12112 KB Output is correct
17 Correct 336 ms 16976 KB Output is correct
18 Correct 291 ms 16976 KB Output is correct
19 Correct 533 ms 24916 KB Output is correct
20 Correct 737 ms 12824 KB Output is correct
21 Correct 165 ms 5716 KB Output is correct
22 Correct 897 ms 16980 KB Output is correct
23 Correct 161 ms 28756 KB Output is correct
24 Correct 553 ms 20060 KB Output is correct
25 Correct 857 ms 30544 KB Output is correct
26 Correct 744 ms 30544 KB Output is correct
27 Correct 696 ms 29780 KB Output is correct
28 Runtime error 553 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -