oj.uz

Submission #946069

# Submission time Handle Problem Language Result Execution time Memory
946069 2024-03-14T09:55:28 Z vjudge1 Game (IOI13_game) C++17
37 / 100
 1004 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 348 KB Output is correct
2 Correct 1 ms 1460 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1460 KB Output is correct
6 Correct 1 ms 1456 KB Output is correct
7 Correct 1 ms 604 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 1624 KB Output is correct
11 Correct 1 ms 1628 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 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 496 ms 134080 KB Output is correct
5 Correct 359 ms 134076 KB Output is correct
6 Correct 445 ms 131412 KB Output is correct
7 Correct 488 ms 131064 KB Output is correct
8 Correct 387 ms 131412 KB Output is correct
9 Correct 456 ms 131096 KB Output is correct
10 Correct 405 ms 131156 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.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 1 ms 1624 KB Output is correct
4 Correct 0 ms 348 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 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 1624 KB Output is correct
11 Correct 1 ms 1624 KB Output is correct
12 Correct 623 ms 133972 KB Output is correct
13 Correct 984 ms 130408 KB Output is correct
14 Runtime error 114 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 0 ms 348 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 0 ms 348 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 0 ms 600 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 484 ms 133996 KB Output is correct
13 Correct 355 ms 134048 KB Output is correct
14 Correct 446 ms 131748 KB Output is correct
15 Correct 426 ms 131144 KB Output is correct
16 Correct 411 ms 131596 KB Output is correct
17 Correct 417 ms 131152 KB Output is correct
18 Correct 405 ms 130764 KB Output is correct
19 Correct 642 ms 133772 KB Output is correct
20 Correct 1004 ms 130264 KB Output is correct
21 Runtime error 119 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 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 1 ms 348 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 1880 KB Output is correct
12 Correct 475 ms 134184 KB Output is correct
13 Correct 334 ms 133948 KB Output is correct
14 Correct 477 ms 131324 KB Output is correct
15 Correct 443 ms 131152 KB Output is correct
16 Correct 356 ms 131412 KB Output is correct
17 Correct 434 ms 131232 KB Output is correct
18 Correct 371 ms 130896 KB Output is correct
19 Correct 630 ms 133716 KB Output is correct
20 Correct 986 ms 130384 KB Output is correct
21 Runtime error 91 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -