oj.uz

Submission #260261

# Submission time Handle Problem Language Result Execution time Memory
260261 2020-08-09T22:12:45 Z davitmarg Game (IOI13_game) C++17
80 / 100
 3932 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;

#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


2 3 13
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
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 640 KB Output is correct
3 Correct 3 ms 632 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 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 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 960 ms 30004 KB Output is correct
5 Correct 896 ms 30236 KB Output is correct
6 Correct 1047 ms 26256 KB Output is correct
7 Correct 978 ms 26412 KB Output is correct
8 Correct 627 ms 16988 KB Output is correct
9 Correct 983 ms 26020 KB Output is correct
10 Correct 939 ms 26256 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 712 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 1 ms 384 KB Output is correct
12 Correct 1331 ms 15224 KB Output is correct
13 Correct 1860 ms 6860 KB Output is correct
14 Correct 624 ms 1528 KB Output is correct
15 Correct 1968 ms 9792 KB Output is correct
16 Correct 637 ms 17400 KB Output is correct
17 Correct 1189 ms 12096 KB Output is correct
18 Correct 1810 ms 17660 KB Output is correct
19 Correct 1725 ms 17780 KB Output is correct
20 Correct 1586 ms 17080 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 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 640 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 2 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1010 ms 29920 KB Output is correct
13 Correct 837 ms 30176 KB Output is correct
14 Correct 947 ms 26364 KB Output is correct
15 Correct 961 ms 26252 KB Output is correct
16 Correct 659 ms 17116 KB Output is correct
17 Correct 1002 ms 26076 KB Output is correct
18 Correct 980 ms 26228 KB Output is correct
19 Correct 1339 ms 15096 KB Output is correct
20 Correct 1786 ms 6836 KB Output is correct
21 Correct 618 ms 1528 KB Output is correct
22 Correct 1952 ms 9848 KB Output is correct
23 Correct 638 ms 17400 KB Output is correct
24 Correct 1249 ms 12152 KB Output is correct
25 Correct 1966 ms 17656 KB Output is correct
26 Correct 1753 ms 17704 KB Output is correct
27 Correct 1584 ms 17104 KB Output is correct
28 Correct 967 ms 157240 KB Output is correct
29 Correct 1924 ms 172700 KB Output is correct
30 Correct 3932 ms 124624 KB Output is correct
31 Correct 3697 ms 102212 KB Output is correct
32 Correct 550 ms 10360 KB Output is correct
33 Correct 748 ms 12664 KB Output is correct
34 Correct 1244 ms 166600 KB Output is correct
35 Correct 1379 ms 91224 KB Output is correct
36 Correct 2593 ms 170832 KB Output is correct
37 Correct 2182 ms 170956 KB Output is correct
38 Correct 2079 ms 170556 KB Output is correct
39 Correct 1784 ms 134256 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 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 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 968 ms 30540 KB Output is correct
13 Correct 902 ms 30884 KB Output is correct
14 Correct 1012 ms 26704 KB Output is correct
15 Correct 980 ms 26592 KB Output is correct
16 Correct 640 ms 17628 KB Output is correct
17 Correct 956 ms 26476 KB Output is correct
18 Correct 900 ms 26852 KB Output is correct
19 Correct 1334 ms 15672 KB Output is correct
20 Correct 1811 ms 7732 KB Output is correct
21 Correct 633 ms 2040 KB Output is correct
22 Correct 1974 ms 10408 KB Output is correct
23 Correct 657 ms 17980 KB Output is correct
24 Correct 1231 ms 12664 KB Output is correct
25 Correct 1806 ms 18272 KB Output is correct
26 Correct 1625 ms 18296 KB Output is correct
27 Correct 1600 ms 17760 KB Output is correct
28 Correct 976 ms 157368 KB Output is correct
29 Correct 2048 ms 172868 KB Output is correct
30 Correct 3917 ms 124888 KB Output is correct
31 Correct 3656 ms 102384 KB Output is correct
32 Correct 562 ms 10368 KB Output is correct
33 Correct 837 ms 12664 KB Output is correct
34 Correct 1266 ms 166600 KB Output is correct
35 Correct 1403 ms 91420 KB Output is correct
36 Correct 2454 ms 170776 KB Output is correct
37 Correct 2066 ms 171088 KB Output is correct
38 Correct 2077 ms 170576 KB Output is correct
39 Runtime error 1214 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -