oj.uz

Submission #946081

# Submission time Handle Problem Language Result Execution time Memory
946081 2024-03-14T09:59:49 Z mansur Game (IOI13_game) C++17
37 / 100
 1026 ms 256000 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include "game.h"
#include<bits/stdc++.h>

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 2001;

int n, m;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

vector<vector<ll>> t;

void upd1(bool is, int v, int p, ll vl, int u = 1, int tl = 0, int tr = m - 1) {
	if (tl == tr) {
		if (is) t[v][u] = vl;
		else t[v][u] = gcd2(t[v * 2][u], t[v * 2 + 1][u]);
		return;
	}
	int md = (tl + tr) / 2;
	if (p <= md) upd1(is, v, p, vl, u * 2, tl, md);
	else upd1(is, v, p, vl, u * 2 + 1, md + 1, tr);
	t[v][u] = gcd2(t[v][u * 2], t[v][u * 2 + 1]);
}

void upd(int p1, int p2, ll vl, int u = 1, int tl = 0, int tr = n - 1) {
	if (tl == tr) {
		upd1(1, u, p2, vl);
		return;
	}
	int md = (tl + tr) / 2;
	if (p1 <= md) upd(p1, p2, vl, u * 2, tl, md);
	else upd(p1, p2, vl, u * 2 + 1, md + 1, tr);
	upd1(0, u, p2, vl);
}

ll get1(int v, int l, int r, int u = 1, int tl = 0, int tr = m - 1) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t[v][u];
	int md = (tl + tr) / 2;
	return gcd2(get1(v, l, r, u * 2, tl, md), get1(v, l, r, u * 2 + 1, md + 1, tr));
}

ll get(int l1, int r1, int l2, int r2, int u = 1, int tl = 0, int tr = n - 1) {
	if (tl > r1 || tr < l1) return 0;
	if (tl >= l1 && tr <= r1) return get1(u, l2, r2);
	int md = (tl + tr) / 2;
	return gcd2(get(l1, r1, l2, r2, u * 2, tl, md), get(l1, r1, l2, r2, u * 2 + 1, md + 1, tr));
}

void init(int R, int C) {
    n = R, m = C;
    t.resize(4 * n);
    for (int i = 0; i < 4 * n; i++) t[i].resize(4 * m);
}

void update(int P, int Q, ll K) {
	upd(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return get(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 2 ms 1624 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 453 ms 132188 KB Output is correct
5 Correct 475 ms 132216 KB Output is correct
6 Correct 508 ms 129412 KB Output is correct
7 Correct 520 ms 129004 KB Output is correct
8 Correct 429 ms 129568 KB Output is correct
9 Correct 460 ms 129112 KB Output is correct
10 Correct 452 ms 128812 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 674 ms 132180 KB Output is correct
13 Correct 1026 ms 129088 KB Output is correct
14 Runtime error 112 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 2 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 450 ms 132228 KB Output is correct
13 Correct 372 ms 132312 KB Output is correct
14 Correct 483 ms 129244 KB Output is correct
15 Correct 493 ms 129024 KB Output is correct
16 Correct 407 ms 129708 KB Output is correct
17 Correct 443 ms 129108 KB Output is correct
18 Correct 422 ms 128636 KB Output is correct
19 Correct 661 ms 132284 KB Output is correct
20 Correct 1022 ms 128708 KB Output is correct
21 Runtime error 108 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1460 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 1640 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 487 ms 132356 KB Output is correct
13 Correct 350 ms 132332 KB Output is correct
14 Correct 496 ms 129312 KB Output is correct
15 Correct 479 ms 128932 KB Output is correct
16 Correct 403 ms 129488 KB Output is correct
17 Correct 478 ms 129128 KB Output is correct
18 Correct 465 ms 128660 KB Output is correct
19 Correct 726 ms 132140 KB Output is correct
20 Correct 1026 ms 128764 KB Output is correct
21 Runtime error 124 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -