oj.uz

Submission #260257

# Submission time Handle Problem Language Result Execution time Memory
260257 2020-08-09T22:05:40 Z davitmarg Game (IOI13_game) C++17
10 / 100
 433 ms 9336 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 = 100;

#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 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 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 1 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 254 ms 5368 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 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 1 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 Incorrect 433 ms 9336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 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 1 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 Incorrect 259 ms 5276 KB Output isn't correct
13 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 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 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 1 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 Incorrect 250 ms 5368 KB Output isn't correct
13 Halted 0 ms 0 KB -