oj.uz

Submission #913892

# Submission time Handle Problem Language Result Execution time Memory
913892 2024-01-20T12:08:25 Z FelixMP Game (IOI13_game) C++17
63 / 100
 1421 ms 256000 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

// Either globally or in a single class:
static char buf[250 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}



struct Node {
	typedef long long T;
	static constexpr T unit = 0;
	T f(T a, T b) { return gcd2(a, b); } 
	Node *l = 0, *r = 0;
	int lo, hi;
	T val = unit;

	//Lazy variables
	// T mset = -unit;
	// T madd = 0;

	//Multi-dimensional variables
	Node *N;
	static int LO2;
	static int HI2;

	Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of unit
    /*
	Node(vector<T>& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = f(l->val, r->val);
		}
		else val = v[lo];
	}
    */
	//Multi-dimensional initialization
	Node(int lo1, int hi1, int lo2, int hi2) : lo(lo1), hi(hi1) {
		N = new Node(lo2, hi2);
	}
	

	T query(int L, int R) {
		if (R <= lo || hi <= L) return unit;
		if (L <= lo && hi <= R) return val;
        if (!l) {
            return unit;
        }
		push();
		return f(l->query(L, R), r->query(L, R));
	}
	//Multi-dimensional query
	T query(int L1, int R1, int L2, int R2) {
		if (R1 <= lo || hi <= L1) return unit;
		if (L1 <= lo && hi <= R1) return N->query(L2, R2);
        if (!l) {
            return unit;
        }
		push();
		return f(l->query(L1, R1, L2, R2), r->query(L1, R1, L2, R2));
	}
    void update_single(int X, T v) {
        if (X < lo || hi <= X) return;
        if (lo == X && hi == X+1) {
            val = v;
            return;
        }
        push();
        l->update_single(X, v);
        r->update_single(X, v);
        val = f(l->val, r->val);
    }
    void update_multiple(int X, Node* _l, Node* _r) {
        if (X < lo || hi <= X) return;
        if (lo == X && hi == X+1) {
            val = f(_l->N->query(X, X+1), _r->N->query(X, X+1));
            return;
        }
        push();
        l->update_multiple(X, _l, _r);
        r->update_multiple(X, _l, _r);
        val = f(l->val, r->val);
    }
    void update(int X, int Y, T v) {
        if (X < lo || hi <= X) return;
        
        if (lo == X && hi == X+1) {
            N->update_single(Y, v); 
            return;
        }
        push();
        l->update(X, Y, v);
        r->update(X, Y, v);
        N->update_multiple(Y, l, r); 
    }

	void push() {
        
		if (!l) {
			int mid = lo + (hi - lo)/2;
			
			//Multi-dimensional:
			if (N) {l = new Node(lo, mid, LO2, HI2); r = new Node(mid, hi, LO2, HI2);}
            else { l = new Node(lo, mid); r = new Node(mid, hi);}
		}
        
		//Range Add Functions
		/*
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
		else if (madd)
			l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
		*/
	}
	//Range Add Functions
	/*
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = f(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = f(l->val, r->val);
		}
	}
	*/
	
};

int Node::LO2 = 0;
int Node::HI2 = 1e9;

Node* tree;


void init(int R, int C) {

    //cerr << "init(" << R << ", " << C << ")" << endl;

    Node::LO2 = 0;
    Node::HI2 = C;

    tree = new Node(0, R, 0, C);
}

void update(int P, int Q, long long K) {
    //cerr << "update(" << P << ", " << Q << ", " << K << ")" << endl;

    tree->update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    //cerr << "calculate(" << P << ", " << Q << ", " << U << ", " << V << ")" << endl;
    return tree->query(P, U+1, Q, V+1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 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 1 ms 344 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 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 429 ms 22752 KB Output is correct
5 Correct 277 ms 22892 KB Output is correct
6 Correct 380 ms 19692 KB Output is correct
7 Correct 430 ms 19548 KB Output is correct
8 Correct 276 ms 14164 KB Output is correct
9 Correct 383 ms 19580 KB Output is correct
10 Correct 407 ms 19096 KB Output is correct
11 Correct 1 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 655 ms 29212 KB Output is correct
13 Correct 996 ms 11464 KB Output is correct
14 Correct 226 ms 1108 KB Output is correct
15 Correct 1167 ms 17496 KB Output is correct
16 Correct 172 ms 37932 KB Output is correct
17 Correct 654 ms 24308 KB Output is correct
18 Correct 1302 ms 43356 KB Output is correct
19 Correct 1092 ms 44220 KB Output is correct
20 Correct 1039 ms 43228 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 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 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 418 ms 22768 KB Output is correct
13 Correct 274 ms 23168 KB Output is correct
14 Correct 358 ms 19792 KB Output is correct
15 Correct 436 ms 19472 KB Output is correct
16 Correct 295 ms 14068 KB Output is correct
17 Correct 414 ms 19608 KB Output is correct
18 Correct 375 ms 19236 KB Output is correct
19 Correct 657 ms 28716 KB Output is correct
20 Correct 996 ms 11208 KB Output is correct
21 Correct 227 ms 1108 KB Output is correct
22 Correct 1167 ms 17416 KB Output is correct
23 Correct 172 ms 37920 KB Output is correct
24 Correct 652 ms 24268 KB Output is correct
25 Correct 1421 ms 43772 KB Output is correct
26 Correct 1076 ms 43928 KB Output is correct
27 Correct 983 ms 42908 KB Output is correct
28 Runtime error 210 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 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 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 445 ms 22696 KB Output is correct
13 Correct 274 ms 22864 KB Output is correct
14 Correct 372 ms 19768 KB Output is correct
15 Correct 435 ms 20020 KB Output is correct
16 Correct 275 ms 13988 KB Output is correct
17 Correct 396 ms 19644 KB Output is correct
18 Correct 373 ms 19140 KB Output is correct
19 Correct 658 ms 28908 KB Output is correct
20 Correct 1006 ms 11220 KB Output is correct
21 Correct 234 ms 1172 KB Output is correct
22 Correct 1222 ms 17376 KB Output is correct
23 Correct 171 ms 37716 KB Output is correct
24 Correct 681 ms 23888 KB Output is correct
25 Correct 1418 ms 43520 KB Output is correct
26 Correct 1103 ms 43676 KB Output is correct
27 Correct 1027 ms 43104 KB Output is correct
28 Runtime error 209 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -