oj.uz

Submission #260259

# Submission time Handle Problem Language Result Execution time Memory
260259 2020-08-09T22:08:44 Z davitmarg Game (IOI13_game) C++17
63 / 100
 2333 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 (!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 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 0 ms 256 KB Output is correct
6 Correct 4 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 1130 ms 43904 KB Output is correct
5 Correct 982 ms 44020 KB Output is correct
6 Correct 1111 ms 41004 KB Output is correct
7 Correct 1117 ms 40824 KB Output is correct
8 Correct 736 ms 26596 KB Output is correct
9 Correct 1114 ms 41844 KB Output is correct
10 Correct 1080 ms 40552 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 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 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 1661 ms 21076 KB Output is correct
13 Correct 2065 ms 10232 KB Output is correct
14 Correct 782 ms 1784 KB Output is correct
15 Correct 2333 ms 14596 KB Output is correct
16 Correct 812 ms 27316 KB Output is correct
17 Correct 1426 ms 18916 KB Output is correct
18 Correct 2167 ms 27756 KB Output is correct
19 Correct 2113 ms 27768 KB Output is correct
20 Correct 1913 ms 27384 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 1124 ms 43636 KB Output is correct
13 Correct 975 ms 44216 KB Output is correct
14 Correct 1083 ms 40808 KB Output is correct
15 Correct 1162 ms 40824 KB Output is correct
16 Correct 781 ms 26728 KB Output is correct
17 Correct 1132 ms 42196 KB Output is correct
18 Correct 1107 ms 40692 KB Output is correct
19 Correct 1665 ms 20984 KB Output is correct
20 Correct 2067 ms 10044 KB Output is correct
21 Correct 793 ms 1784 KB Output is correct
22 Correct 2280 ms 14428 KB Output is correct
23 Correct 828 ms 27128 KB Output is correct
24 Correct 1477 ms 18936 KB Output is correct
25 Correct 2109 ms 27492 KB Output is correct
26 Correct 1953 ms 27720 KB Output is correct
27 Correct 1946 ms 27076 KB Output is correct
28 Runtime error 1198 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 4 ms 768 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 4 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 1126 ms 43748 KB Output is correct
13 Correct 962 ms 43896 KB Output is correct
14 Correct 1106 ms 40664 KB Output is correct
15 Correct 1108 ms 40736 KB Output is correct
16 Correct 741 ms 26348 KB Output is correct
17 Correct 1171 ms 41664 KB Output is correct
18 Correct 1087 ms 40436 KB Output is correct
19 Correct 1646 ms 21212 KB Output is correct
20 Correct 2029 ms 9832 KB Output is correct
21 Correct 768 ms 1528 KB Output is correct
22 Correct 2312 ms 14428 KB Output is correct
23 Correct 901 ms 26956 KB Output is correct
24 Correct 1492 ms 18680 KB Output is correct
25 Correct 2235 ms 27696 KB Output is correct
26 Correct 2008 ms 27560 KB Output is correct
27 Correct 1969 ms 26972 KB Output is correct
28 Runtime error 1181 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -