| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 240698 |
2020-06-20T19:07:59 Z |
aryan12 |
Game (IOI13_game) |
C++17 |
|
164 ms |
256004 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
vector<vector<long long> >seg;
int gg, ggg;
long long gcd2(long long a, long long b) {
if(a == 0)
return b;
if(b == 0)
return a;
return gcd2(b, a % b);
}
void init(int r, int c) {
r += 79;
c += 79;
gg = r;
ggg = c;
for(long long i = 0; i <= r * 2; i++) {
vector<long long> temp;
for(long long j = 0; j <= c * 2; j++) {
temp.push_back(0);
}
seg.push_back(temp);
}
}
void updateY(long long l, long long r, long long pos, long long xpos, long long qcol, long long qval) {
//cout << "UpdateY " << l << " " << r << " " << qcol << " " << xpos << " " << pos << endl;
if(l == r && l == qcol) {
seg[xpos][pos] = qval;
//cout << seg[xpos][pos] << endl;
return;
}
else {
long long mid = (l + r) / 2;
if(qcol <= mid)
updateY(l, mid, pos * 2, xpos, qcol, qval);
else
updateY(mid + 1, r, pos * 2 + 1, xpos, qcol, qval);
seg[xpos][pos] = gcd2(seg[xpos][pos * 2], seg[xpos][pos * 2 + 1]);
}
}
void updateX(long long l, long long r, long long pos, long long qrow, long long qcol, long long val, long long col) {
//cout << "UpdateX " << l << " " << r << " " << qrow << " " << pos << endl;
if(l == r && l == qrow) {
updateY(1, col, 1, pos, qcol, val);
return;
}
else {
long long mid = (l + r) / 2;
if(qrow <= mid)
updateX(l, mid, pos * 2, qrow, qcol, val, col);
else
updateX(mid + 1, r, pos * 2 + 1, qrow, qcol, val, col);
}
for(long long i = 0; i < seg[pos].size(); i++) {
seg[pos][i] = gcd2(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}
}
long long queryY(long long l, long long r, long long pos, long long leftcol, long long rightcol, long long xpos) {
if(l > rightcol || r < leftcol)
return 0;
if(leftcol <= l && r <= rightcol)
return seg[xpos][pos];
long long mid = (l + r) / 2;
return gcd2(queryY(l, mid, pos * 2, leftcol, rightcol, xpos), queryY(mid + 1, r, pos * 2 + 1, leftcol, rightcol, xpos));
}
long long queryX(long long l, long long r, long long pos, long long leftrow, long long leftcol, long long rightrow, long long rightcol, long long y) {
if(l > rightrow || r < leftrow)
return 0;
if(leftrow <= l && r <= rightrow)
return queryY(1, y, 1, leftcol, rightcol, pos);
long long mid = (l + r) / 2;
return gcd2(queryX(l, mid, pos * 2, leftrow, leftcol, rightrow, rightcol, y), queryX(mid + 1, r, pos * 2 + 1, leftrow, leftcol, rightrow, rightcol, y));
}
int x = gg, y = ggg;
void update(int r, int c, long long val) {
r++; c++;
updateX(1, x, 1, r, c, val, y);
}
long long calculate(int r1, int c1, int r2, int c2) {
r1++; c1++;
r2++; c2++;
return queryX(1, x, 1, r1, c1, r2, c2, y);
}
/*int main() {
cin >> x >> y >> queries;
init(x, y);
while(queries--) {
// for(long long i = 1; i <= 8; i++) {
// for(long long j = 1; j <= 8; j++) {
// cout << seg[i][j] << " ";
// }
// cout << endl;
// }
int com;
cin >> com;
if(com == 1) {
int r, c;
long long val;
cin >> r >> c >> val;
update(r, c, val);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << calculate(a, b, c, d) << endl;
}
}
}*/
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;
^~~
game.cpp: In function 'void updateX(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
game.cpp:62:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long long i = 0; i < seg[pos].size(); i++) {
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
160 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
164 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
145 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
