oj.uz

Submission #1113480

# Submission time Handle Problem Language Result Execution time Memory
1113480 2024-11-16T16:17:29 Z Gray Game (IOI13_game) C++17
63 / 100
 1479 ms 256000 KB 
#include<bits/stdc++.h>
#include <type_traits>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct SegTree1D{
	struct Node{
		ll left, right, val;
		Node(){
			left=right=-1;
			val=0;
		}
	};
	vector<Node> nodes;
	ll add_node(){
	    nodes.push_back(Node());
		return nodes.size()-1;
	}
	map<int, ll> leaves;
	int rsz;
	SegTree1D(int N){
		rsz=N;
		add_node();
	}
	void update(ll tl, ll tr, ll v, ll i, ll x){
	    if (tl==tr){
			nodes[v].val=x;
			leaves[tl]=v;
		}else{
		    ll tm = (tl+tr)/2;
			if (i<=tm){
			    if (nodes[v].left==-1) nodes[v].left=add_node();
				update(tl, tm, nodes[v].left, i, x);
			}else{
			    if (nodes[v].right==-1) nodes[v].right=add_node();
				update(tm+1, tr, nodes[v].right, i, x);
			}
			nodes[v].val=0;
			if (nodes[v].left!=-1) nodes[v].val=__gcd(nodes[nodes[v].left].val, nodes[v].val);
			if (nodes[v].right!=-1) nodes[v].val=__gcd(nodes[nodes[v].right].val, nodes[v].val);
		}
	}
	void update(ll i, ll x){
	   update(0, rsz-1, 0, i, x);
	}
	ll query(ll tl, ll tr, ll v, ll l, ll r){
	    if (tl==l and tr==r){
			return nodes[v].val;
		}
		else if (l>r) return 0;
		else{
		    ll tm = (tl+tr)/2;
			ll res=0;
			if (nodes[v].left!=-1) res=__gcd(res, query(tl, tm, nodes[v].left, l, min(r, tm)));
			if (nodes[v].right!=-1) res=__gcd(res, query(tm+1, tr, nodes[v].right, max(l, tm+1), r));
			return res;
		}
	}
	ll query(int l, int r){
		return query(0, rsz-1, 0, l, r);
	}
	ll getval(int ind){
		if (!leaves.count(ind)) return 0;
		return nodes[leaves[ind]].val;
	}
};
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 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 379 ms 19188 KB Output is correct
5 Correct 250 ms 18800 KB Output is correct
6 Correct 331 ms 15724 KB Output is correct
7 Correct 348 ms 15468 KB Output is correct
8 Correct 258 ms 11924 KB Output is correct
9 Correct 347 ms 15532 KB Output is correct
10 Correct 307 ms 14992 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 594 ms 25056 KB Output is correct
13 Correct 758 ms 12872 KB Output is correct
14 Correct 171 ms 5704 KB Output is correct
15 Correct 896 ms 16764 KB Output is correct
16 Correct 184 ms 29000 KB Output is correct
17 Correct 611 ms 20048 KB Output is correct
18 Correct 940 ms 30280 KB Output is correct
19 Correct 923 ms 30536 KB Output is correct
20 Correct 788 ms 30164 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 377 ms 19084 KB Output is correct
13 Correct 275 ms 18796 KB Output is correct
14 Correct 369 ms 15688 KB Output is correct
15 Correct 368 ms 15260 KB Output is correct
16 Correct 276 ms 11896 KB Output is correct
17 Correct 381 ms 15492 KB Output is correct
18 Correct 349 ms 15036 KB Output is correct
19 Correct 637 ms 24904 KB Output is correct
20 Correct 802 ms 12768 KB Output is correct
21 Correct 185 ms 5704 KB Output is correct
22 Correct 924 ms 16656 KB Output is correct
23 Correct 184 ms 28884 KB Output is correct
24 Correct 616 ms 20036 KB Output is correct
25 Correct 890 ms 30332 KB Output is correct
26 Correct 862 ms 30536 KB Output is correct
27 Correct 751 ms 30024 KB Output is correct
28 Correct 741 ms 256000 KB Output is correct
29 Runtime error 1451 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 508 KB Output is correct
12 Correct 451 ms 19120 KB Output is correct
13 Correct 266 ms 18900 KB Output is correct
14 Correct 378 ms 16008 KB Output is correct
15 Correct 331 ms 15468 KB Output is correct
16 Correct 254 ms 11964 KB Output is correct
17 Correct 418 ms 15376 KB Output is correct
18 Correct 345 ms 15168 KB Output is correct
19 Correct 636 ms 25004 KB Output is correct
20 Correct 838 ms 12828 KB Output is correct
21 Correct 192 ms 5756 KB Output is correct
22 Correct 931 ms 16740 KB Output is correct
23 Correct 186 ms 29000 KB Output is correct
24 Correct 632 ms 19968 KB Output is correct
25 Correct 936 ms 30284 KB Output is correct
26 Correct 806 ms 30424 KB Output is correct
27 Correct 774 ms 30016 KB Output is correct
28 Correct 739 ms 256000 KB Output is correct
29 Runtime error 1479 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -