Submission #260265

#	Time	Username	Problem	Language	Result	Execution time	Memory
260265		davitmarg	Game (IOI13_game)	C++17	80 / 100	3722 ms	256004 KiB

game

/*
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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20