oj.uz

Submission #395867

# Submission time Handle Problem Language Result Execution time Memory
395867 2021-04-29T04:47:56 Z pure_mem Game (IOI13_game) C++14
63 / 100
 1618 ms 256004 KB 
#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;
		ll left = (p1[0] ? p1[0]->get1(tl, tm, l, r): 0);
		ll right = (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0); 
		return gcd(left, right);
	}
	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;
		ll left = (p[0] ? p[0]->get(tl, tm, l, r): 0);
		ll right = (p[1] ? p[1]->get(tm + 1, tr, l, r): 0); 
		//cerr << tl << " " << tr << " " << left << " z " << right << "\n";
		return gcd(left, right);
	}
}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 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 208 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 272 KB Output is correct
9 Correct 2 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 204 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 623 ms 21136 KB Output is correct
5 Correct 426 ms 20932 KB Output is correct
6 Correct 526 ms 18740 KB Output is correct
7 Correct 581 ms 18388 KB Output is correct
8 Correct 424 ms 13284 KB Output is correct
9 Correct 588 ms 18536 KB Output is correct
10 Correct 539 ms 18232 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 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 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 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 958 ms 25612 KB Output is correct
13 Correct 1347 ms 12528 KB Output is correct
14 Correct 282 ms 5696 KB Output is correct
15 Correct 1531 ms 16724 KB Output is correct
16 Correct 226 ms 30820 KB Output is correct
17 Correct 1004 ms 21056 KB Output is correct
18 Correct 1496 ms 32500 KB Output is correct
19 Correct 1298 ms 32464 KB Output is correct
20 Correct 1218 ms 31764 KB Output is correct
21 Correct 1 ms 204 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 2 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 428 KB Output is correct
7 Correct 1 ms 296 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 364 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 552 ms 21120 KB Output is correct
13 Correct 408 ms 20932 KB Output is correct
14 Correct 550 ms 18708 KB Output is correct
15 Correct 604 ms 18404 KB Output is correct
16 Correct 379 ms 13244 KB Output is correct
17 Correct 563 ms 18628 KB Output is correct
18 Correct 532 ms 18144 KB Output is correct
19 Correct 867 ms 25540 KB Output is correct
20 Correct 1316 ms 12540 KB Output is correct
21 Correct 291 ms 5696 KB Output is correct
22 Correct 1618 ms 16768 KB Output is correct
23 Correct 229 ms 30784 KB Output is correct
24 Correct 927 ms 21072 KB Output is correct
25 Correct 1559 ms 32392 KB Output is correct
26 Correct 1368 ms 32344 KB Output is correct
27 Correct 1245 ms 31828 KB Output is correct
28 Runtime error 656 ms 256004 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 464 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 304 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 300 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 567 ms 21100 KB Output is correct
13 Correct 412 ms 20988 KB Output is correct
14 Correct 518 ms 18740 KB Output is correct
15 Correct 593 ms 18460 KB Output is correct
16 Correct 446 ms 13248 KB Output is correct
17 Correct 563 ms 18588 KB Output is correct
18 Correct 518 ms 18072 KB Output is correct
19 Correct 929 ms 25492 KB Output is correct
20 Correct 1388 ms 12716 KB Output is correct
21 Correct 298 ms 5868 KB Output is correct
22 Correct 1531 ms 16700 KB Output is correct
23 Correct 242 ms 30884 KB Output is correct
24 Correct 951 ms 21160 KB Output is correct
25 Correct 1538 ms 32504 KB Output is correct
26 Correct 1379 ms 32400 KB Output is correct
27 Correct 1221 ms 31904 KB Output is correct
28 Runtime error 741 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -