oj.uz

Submission #260265

# Submission time Handle Problem Language Result Execution time Memory
260265 2020-08-09T22:19:52 Z davitmarg Game (IOI13_game) C++17
80 / 100
 3722 ms 256004 KB 
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = mod-8;

#ifndef death
#include "game.h"
#endif

LL gcd(LL a, LL b)
{
    if (!a || !b)
        return a + b;
    return gcd(b, a % b);
}

struct node
{
	LL val = 0;
	int l = 0, r = 0;
	node(LL val=0)
	{
		this->val = val;
		l = 0;
		r = 0;
	}
};

struct segtree
{
	vector<node> t;

	void addNode(int val = 0)
	{
		t.push_back(node());
	}

	segtree()
	{
		addNode();
	}

	LL get(int v, int l, int r, int i, int j)
	{
		if (i > j)
			return 0;
		if (l == i && r == j)
			return t[v].val;
		int m = (l + r) / 2;

		LL res = 0;
		if (t[v].l)
			res = get(t[v].l, l, m, i, min(m, j));
        if (t[v].r)
            res = gcd(res, get(t[v].r, m + 1, r, max(m + 1, i), j));
		return res;
	}

	void add(int v, int l, int r, int pos, LL val)
	{

		if (l == r)
		{
            t[v].val = val;
			return;
		}
		int m = (l + r) / 2;

		if (pos <= m)
		{

			if (!t[v].l)
			{
				addNode();
				t[v].l = t.size() - 1;
			}
			add(t[v].l, l, m, pos, val);
		}
		else
		{
			if (!t[v].r)
			{
				addNode();
				t[v].r = t.size() - 1;
			}
			add(t[v].r, m + 1, r, pos, val);
		}

		t[v].val = 0;
		if (t[v].l)
			t[v].val = gcd(t[v].val, t[t[v].l].val);
		if (t[v].r)
			t[v].val = gcd(t[v].val, t[t[v].r].val);
	}

};

struct node1
{
	segtree val;
	int l = 0, r = 0;
	node1()
	{
		val = segtree();
		l = 0;
		r = 0;
	}
};

vector<node1> t;

void addNode()
{
	t.push_back(node1());
}


LL get(int v, int l, int r, int i, int j,int L,int R)
{
	if (i > j)
		return 0;
	if (l == i && r == j)
		return t[v].val.get(0, 0, N, L, R);
	int m = (l + r) / 2;

	LL res = 0;
	if (t[v].l)
		res = get(t[v].l, l, m, i, min(m, j), L, R);
	if (t[v].r)
		res = gcd(res, get(t[v].r, m + 1, r, max(m + 1, i), j, L, R));
	return res;
}

void add(int v, int l, int r, int pos,int pos2, LL val)
{
	if (l == r)
	{
		t[v].val.add(0, 0, N, pos2, val);
		return;
	}
	int m = (l + r) / 2;

	if (pos <= m)
	{

		if (!t[v].l)
		{
			addNode();
			t[v].l = t.size() - 1;
		}
		add(t[v].l, l, m, pos,pos2, val);
	}
	else
	{
		if (!t[v].r)
		{
			addNode();
			t[v].r = t.size() - 1;
		}
		add(t[v].r, m + 1, r, pos,pos2, val);
	}

	LL res = 0;

	if (t[v].l)
		res = gcd(res, t[t[v].l].val.get(0, 0, N, pos2, pos2));

	if (t[v].r)
		res = gcd(res, t[t[v].r].val.get(0, 0, N, pos2, pos2));

	t[v].val.add(0, 0, N, pos2, res);
}


void init(int R, int C)
{
	addNode();
}

LL calculate(int P, int Q, int U, int V)
{
	return get(0, 0, N, P, U, Q, V);
}

void update(int P, int Q, LL K)
{
	add(0, 0, N, P, Q, K);
}


#ifdef death
int main()
{
    fastIO;
	init(N, N);
	int Q;
	cin >> Q >> Q >> Q;
	while (Q--)
	{
		int T;
		cin >> T;
		if (T == 1)
		{
			int a, b;
			LL c;
			cin >> a >> b >> c;
			update(a, b, c);
		}
		else
		{
			int a, b, A, B;
			cin >> a >> b >> A >> B;
			cout << calculate(a, b, A, B) << endl;
		}
	}
    return 0;
}
#endif

/*
2 3 14
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
1 0 1 0
2 0 0 0 2
2 0 0 1 1
1 1 1 0
2 0 0 1 1
2 1 1 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1



*/

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1034 ms 31104 KB Output is correct
5 Correct 851 ms 31628 KB Output is correct
6 Correct 944 ms 28044 KB Output is correct
7 Correct 972 ms 27612 KB Output is correct
8 Correct 686 ms 18552 KB Output is correct
9 Correct 977 ms 27548 KB Output is correct
10 Correct 944 ms 27620 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1376 ms 16676 KB Output is correct
13 Correct 1786 ms 8380 KB Output is correct
14 Correct 612 ms 3064 KB Output is correct
15 Correct 1957 ms 11384 KB Output is correct
16 Correct 647 ms 18884 KB Output is correct
17 Correct 1166 ms 13944 KB Output is correct
18 Correct 1901 ms 19204 KB Output is correct
19 Correct 1684 ms 19192 KB Output is correct
20 Correct 1591 ms 18652 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 975 ms 31208 KB Output is correct
13 Correct 810 ms 31740 KB Output is correct
14 Correct 957 ms 27752 KB Output is correct
15 Correct 938 ms 27776 KB Output is correct
16 Correct 637 ms 18516 KB Output is correct
17 Correct 996 ms 27428 KB Output is correct
18 Correct 970 ms 27780 KB Output is correct
19 Correct 1354 ms 16376 KB Output is correct
20 Correct 1777 ms 8184 KB Output is correct
21 Correct 613 ms 3044 KB Output is correct
22 Correct 1962 ms 11144 KB Output is correct
23 Correct 636 ms 18768 KB Output is correct
24 Correct 1214 ms 13432 KB Output is correct
25 Correct 1855 ms 19200 KB Output is correct
26 Correct 1645 ms 19164 KB Output is correct
27 Correct 1607 ms 18640 KB Output is correct
28 Correct 977 ms 147724 KB Output is correct
29 Correct 1874 ms 163944 KB Output is correct
30 Correct 3722 ms 118732 KB Output is correct
31 Correct 3595 ms 96016 KB Output is correct
32 Correct 549 ms 2536 KB Output is correct
33 Correct 736 ms 4808 KB Output is correct
34 Correct 707 ms 160968 KB Output is correct
35 Correct 1315 ms 82676 KB Output is correct
36 Correct 2571 ms 161036 KB Output is correct
37 Correct 2115 ms 161100 KB Output is correct
38 Correct 2083 ms 160676 KB Output is correct
39 Correct 1719 ms 124880 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1002 ms 30816 KB Output is correct
13 Correct 832 ms 31488 KB Output is correct
14 Correct 944 ms 27556 KB Output is correct
15 Correct 955 ms 27324 KB Output is correct
16 Correct 636 ms 18436 KB Output is correct
17 Correct 956 ms 27328 KB Output is correct
18 Correct 910 ms 27436 KB Output is correct
19 Correct 1359 ms 16504 KB Output is correct
20 Correct 1804 ms 8184 KB Output is correct
21 Correct 614 ms 2660 KB Output is correct
22 Correct 1971 ms 11132 KB Output is correct
23 Correct 634 ms 18592 KB Output is correct
24 Correct 1172 ms 13560 KB Output is correct
25 Correct 1833 ms 18968 KB Output is correct
26 Correct 1822 ms 18808 KB Output is correct
27 Correct 1554 ms 18424 KB Output is correct
28 Correct 968 ms 147572 KB Output is correct
29 Correct 1884 ms 163388 KB Output is correct
30 Correct 3722 ms 118408 KB Output is correct
31 Correct 3559 ms 95828 KB Output is correct
32 Correct 545 ms 2168 KB Output is correct
33 Correct 734 ms 4620 KB Output is correct
34 Correct 724 ms 160592 KB Output is correct
35 Correct 1340 ms 82264 KB Output is correct
36 Correct 2441 ms 160688 KB Output is correct
37 Correct 2119 ms 160904 KB Output is correct
38 Correct 2269 ms 160256 KB Output is correct
39 Runtime error 1216 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -