oj.uz

Submission #260258

# Submission time Handle Problem Language Result Execution time Memory
260258 2020-08-09T22:06:40 Z davitmarg Game (IOI13_game) C++17
63 / 100
 2294 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 (!t[v].l)
		{
			addNode();
			t[v].l = t.size() - 1;
		}
		if (!t[v].r)
		{
			addNode();
			t[v].r = t.size() - 1;
		}

        if (pos <= m)
            add(t[v].l, l, m, pos, val);
        else
            add(t[v].r, m + 1, r, pos, val);

        t[v].val = gcd(t[t[v].l].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 (!t[v].l)
	{
		addNode();
		t[v].l = t.size() - 1;
	}
	if (!t[v].r)
	{
		addNode();
		t[v].r = t.size() - 1;
	}

	if (pos <= m)
		add(t[v].l, l, m, pos,pos2, val);
	else
		add(t[v].r, m + 1, r, pos,pos2, val);

	t[v].val.add(0, 0, N, pos2, gcd(t[t[v].l].val.get(0, 0, N, pos2, pos2), t[t[v].r].val.get(0, 0, N, pos2, pos2)));
}


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 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 768 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 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 1131 ms 43644 KB Output is correct
5 Correct 980 ms 47636 KB Output is correct
6 Correct 1096 ms 45028 KB Output is correct
7 Correct 1196 ms 44920 KB Output is correct
8 Correct 774 ms 30184 KB Output is correct
9 Correct 1142 ms 45936 KB Output is correct
10 Correct 1078 ms 44948 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 640 KB Output is correct
3 Correct 4 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 768 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1619 ms 20844 KB Output is correct
13 Correct 2036 ms 13652 KB Output is correct
14 Correct 778 ms 6136 KB Output is correct
15 Correct 2263 ms 18644 KB Output is correct
16 Correct 805 ms 30968 KB Output is correct
17 Correct 1408 ms 23288 KB Output is correct
18 Correct 2118 ms 32684 KB Output is correct
19 Correct 1953 ms 32760 KB Output is correct
20 Correct 1981 ms 32308 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 768 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 768 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1136 ms 43592 KB Output is correct
13 Correct 964 ms 47472 KB Output is correct
14 Correct 1119 ms 44876 KB Output is correct
15 Correct 1117 ms 45088 KB Output is correct
16 Correct 734 ms 30312 KB Output is correct
17 Correct 1112 ms 46068 KB Output is correct
18 Correct 1059 ms 44796 KB Output is correct
19 Correct 1620 ms 25056 KB Output is correct
20 Correct 2078 ms 13816 KB Output is correct
21 Correct 818 ms 6136 KB Output is correct
22 Correct 2283 ms 18680 KB Output is correct
23 Correct 807 ms 30968 KB Output is correct
24 Correct 1415 ms 23416 KB Output is correct
25 Correct 2236 ms 32628 KB Output is correct
26 Correct 2070 ms 32632 KB Output is correct
27 Correct 1953 ms 32092 KB Output is correct
28 Runtime error 1145 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 768 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1103 ms 43704 KB Output is correct
13 Correct 959 ms 47468 KB Output is correct
14 Correct 1086 ms 45092 KB Output is correct
15 Correct 1131 ms 45028 KB Output is correct
16 Correct 756 ms 30572 KB Output is correct
17 Correct 1144 ms 46064 KB Output is correct
18 Correct 1047 ms 44848 KB Output is correct
19 Correct 1623 ms 24784 KB Output is correct
20 Correct 2036 ms 13560 KB Output is correct
21 Correct 776 ms 6008 KB Output is correct
22 Correct 2294 ms 18612 KB Output is correct
23 Correct 824 ms 30968 KB Output is correct
24 Correct 1405 ms 23252 KB Output is correct
25 Correct 2228 ms 32600 KB Output is correct
26 Correct 1997 ms 32504 KB Output is correct
27 Correct 1862 ms 31992 KB Output is correct
28 Runtime error 1159 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -