oj.uz

Submission #395868

# Submission time Handle Problem Language Result Execution time Memory
395868 2021-04-29T04:51:59 Z pure_mem Game (IOI13_game) C++14
63 / 100
 1696 ms 256008 KB 
#pragma GCC optimize("Ofast")

#include "game.h"
#include <iostream>
#include <algorithm>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

ll gcd(ll x, ll y) {
	if(x < y)
		swap(x, y);
    while(y){
    	x %= y;
    	swap(x, y);
    }
    return x;
}

int n, m, dl, dr;

struct node{
	node* p[2] = {nullptr, nullptr};
	node* p1[2] = {nullptr, nullptr};
	ll val = 0;
	node* getp(int v){
		if(!p[v])
			p[v] = new node;
		return p[v];	
	}
	node* getp1(int v){
		if(!p1[v])
			p1[v] = new node;
		return p1[v];	
	}
	void merge(int tl, int tr, node* L, node* R, int pos){
		if(!L && !R)
			return;
		if(tl == tr){
			val = 0;
			if(L)
				val = gcd(L->val, val);
			if(R)
				val = gcd(R->val, val);
			return;	
		}          
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			if(L)
				L = L->p1[0];
			if(R)
				R = R->p1[0];
			getp1(0)->merge(tl, tm, L, R, pos);
		}
		else{
			if(L)
				L = L->p1[1];
			if(R)
				R = R->p1[1];
		    getp1(1)->merge(tm + 1, tr, L, R, pos);
		}
		val = 0;
		if(p1[0])
			val = gcd(p1[0]->val, val);
		if(p1[1])
			val = gcd(p1[1]->val, val);
		//cerr << tl << " " << tr << " " << val << " " << this << "s\n";
	}
	void upd1(int tl, int tr, int pos, ll _val){
		if(tl == tr)
			return void(val = _val);
		int tm = (tl + tr) / 2;
		//cerr << tl << " s " << tr << "\n"; 
		if(pos <= tm)
			getp1(0)->upd1(tl, tm, pos, _val);
		else
			getp1(1)->upd1(tm + 1, tr, pos, _val);
		val = 0;
		if(p1[0])
			val = gcd(p1[0]->val, val);
		if(p1[1])
			val = gcd(p1[1]->val, val);
	}
	ll get1(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return 0;
		if(tl >= l && tr <= r)
			return val;
		int tm = (tl + tr) / 2;
		return gcd((p1[0] ? p1[0]->get1(tl, tm, l, r): 0), (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0));
	}
	void upd(int tl, int tr, int pos, ll _val){
		//cerr << tl << " " << tr << " b " << this << "\n";
		if(tl == tr){
			return void(upd1(1, m, dl, _val));
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			getp(0)->upd(tl, tm, pos, _val);
		else
			getp(1)->upd(tm + 1, tr, pos, _val);
		merge(1, m, p[0], p[1], dl);	
	}
	ll get(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return 0;
		if(tl >= l && tr <= r)
			return get1(1, m, dl, dr);
		int tm = (tl + tr) / 2;
		//cerr << tl << " " << tr << " " << left << " z " << right << "\n";
		return gcd((p[0] ? p[0]->get(tl, tm, l, r): 0), (p[1] ? p[1]->get(tm + 1, tr, l, r): 0));
	}
}root;

void init(int R, int C) {
	n = R, m = C;    
}

void update(int P, int Q, ll K) {
//	cerr << "was1\n";
	dl = Q + 1;
	//cerr << P + 1 << " " << Q + 1 << "\n";
	root.upd(1, n, P + 1, K);
//	cerr << "was\n";	
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    //cerr << "were\n";
    dl = Q + 1, dr = V + 1;
    //cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n";
    ll tmp = root.get(1, n, P + 1, U + 1);
 //   cerr << tmp << "\n";
    return tmp;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 296 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 592 ms 20532 KB Output is correct
5 Correct 413 ms 20900 KB Output is correct
6 Correct 523 ms 17824 KB Output is correct
7 Correct 606 ms 17524 KB Output is correct
8 Correct 396 ms 12780 KB Output is correct
9 Correct 570 ms 17780 KB Output is correct
10 Correct 601 ms 17336 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 895 ms 25320 KB Output is correct
13 Correct 1358 ms 12408 KB Output is correct
14 Correct 302 ms 4804 KB Output is correct
15 Correct 1606 ms 16068 KB Output is correct
16 Correct 269 ms 30412 KB Output is correct
17 Correct 918 ms 20028 KB Output is correct
18 Correct 1573 ms 30776 KB Output is correct
19 Correct 1386 ms 30948 KB Output is correct
20 Correct 1295 ms 30360 KB Output is correct
21 Correct 1 ms 296 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 572 ms 20544 KB Output is correct
13 Correct 428 ms 20896 KB Output is correct
14 Correct 546 ms 17936 KB Output is correct
15 Correct 579 ms 17832 KB Output is correct
16 Correct 392 ms 12752 KB Output is correct
17 Correct 602 ms 17708 KB Output is correct
18 Correct 503 ms 17416 KB Output is correct
19 Correct 887 ms 25212 KB Output is correct
20 Correct 1385 ms 12532 KB Output is correct
21 Correct 299 ms 4804 KB Output is correct
22 Correct 1696 ms 16164 KB Output is correct
23 Correct 229 ms 30412 KB Output is correct
24 Correct 1089 ms 19992 KB Output is correct
25 Correct 1557 ms 30860 KB Output is correct
26 Correct 1300 ms 30864 KB Output is correct
27 Correct 1263 ms 30196 KB Output is correct
28 Runtime error 676 ms 256008 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 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 576 ms 18296 KB Output is correct
13 Correct 464 ms 18604 KB Output is correct
14 Correct 538 ms 15616 KB Output is correct
15 Correct 607 ms 15432 KB Output is correct
16 Correct 400 ms 10588 KB Output is correct
17 Correct 620 ms 15596 KB Output is correct
18 Correct 539 ms 15204 KB Output is correct
19 Correct 915 ms 23028 KB Output is correct
20 Correct 1330 ms 10308 KB Output is correct
21 Correct 299 ms 2540 KB Output is correct
22 Correct 1574 ms 14040 KB Output is correct
23 Correct 235 ms 28228 KB Output is correct
24 Correct 945 ms 17776 KB Output is correct
25 Correct 1600 ms 28568 KB Output is correct
26 Correct 1494 ms 28812 KB Output is correct
27 Correct 1349 ms 28052 KB Output is correct
28 Runtime error 652 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -