# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
962728 |
2024-04-14T07:31:13 Z |
NValchanov |
Game (IOI13_game) |
C++17 |
|
13000 ms |
140292 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
const ll MAXN = 10;
const ll MAXM = 1e5;
const ll MAXLOG = 17;
long long gcd2(long long X, long long Y) {
if(X == 0 && Y == 0)
return 0;
else if(X == 0 && Y != 0)
return Y;
else if(X != 0 && Y == 0)
return X;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll n,m;
ll a[MAXN][MAXM];
ll sparse[MAXN][MAXM][MAXLOG];
ll lg[MAXM];
void init(int R, int C)
{
n = R;
m = C;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
for(int k = 0; k < MAXLOG; k++)
{
sparse[i][j][k] = 0;
}
}
}
for(int i = 2; i <= m; i++)
{
lg[i] = lg[i / 2] + 1;
///cout << "Logarithm base 2 from " << i << " is " << lg[i] << endl;
}
}
void calc(int i)
{
for(int k = 1; k < MAXLOG; k++)
{
for(int j = 0; j < m; j++)
{
ll first = sparse[i][j][k - 1];
ll second = sparse[i][j + (1 << (k - 1))][k - 1];
sparse[i][j][k] = gcd2(first, second);
}
}
}
void update(int i, int j, long long k)
{
a[i][j] = k;
sparse[i][j][0] = k;
calc(i);
}
ll query_sparse(ll i, ll l, ll r)
{
ll len = r - l + 1;
ll k = lg[len];
return gcd2(sparse[i][l][k], sparse[i][r - (1 << k) + 1][k]);
}
ll query(int i1, int j1, int i2, int j2)
{
///cout << "For query from " << "(" << i1 << ";" << j1 << ")" << " to " << "(" << i2 << ";" << j2 << ")" << endl;
ll result = query_sparse(i1, j1, j2);
///cout << "GCD from " << i1 << " to " << i1 << " is " << result << endl;
for(int i = i1 + 1; i <= i2; i++)
{
ll cur = query_sparse(i, j1, j2);
result = gcd2(result, cur);
///cout << "GCD for row " << i << " is " << cur << endl;
///cout << "GCD from " << i1 << " to " << i << " is " << result << endl;
}
return result;
}
ll calculate(int i1, int j1, int i2, int j2)
{
return query(i1, j1, i2, j2);
}
/**
int main()
{
ll r,c,n;
cin >> r >> c >> n;
init(r,c);
for(int i = 0; i < n; i++)
{
ll type;
cin >> type;
if(type == 1)
{
ll x,y,w;
cin >> x >> y >> w;
update(x,y,w);
cout << endl << endl << "Sparse Table : " << endl;
for(int j = 0; j < r; j++)
{
for(int k = 0; k < c; k++)
{
cout << sparse[j][k][1] << " ";
}
cout << endl;
}
cout << endl << endl;
}
else
{
ll i1,j1,i2,j2;
cin >> i1 >> j1 >> i2 >> j2;
cout << calculate(i1, j1, i2, j2) << endl;
}
}
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Runtime error |
31 ms |
46164 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
2 ms |
14684 KB |
Output is correct |
4 |
Execution timed out |
13080 ms |
140292 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Runtime error |
33 ms |
46312 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Runtime error |
24 ms |
46172 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Runtime error |
29 ms |
46172 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |