| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117511 |
2019-06-16T11:19:29 Z |
someone_aa |
Game (IOI13_game) |
C++17 |
|
2 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
int r, c;
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;
}
class node_y {
public:
ll val;
int lb, rb;
node_y *leftchild, *rightchild;
node_y(int _lb, int _rb) {
lb = _lb; rb = _rb;
leftchild = rightchild = NULL;
val = 0LL;
}
ll get_val(node_y *x) {
if(x == NULL) return 0LL;
else return x->val;
}
void update(int ind, ll uval) {
if(lb == rb) {
val = gcd2(val, uval);
}
else {
int mid = (lb + rb) / 2;
if(ind <= mid) {
if(leftchild == NULL) {
leftchild = new node_y(lb, mid);
}
leftchild -> update(ind, uval);
}
else {
if(rightchild == NULL) {
rightchild = new node_y(mid+1, rb);
}
rightchild -> update(ind, uval);
}
val = gcd2(get_val(leftchild), get_val(rightchild));
}
//cout<<"Done "<<lb<<" "<<rb<<" -> "<<val<<"\n";
}
ll query(int ql, int qr) {
if(lb > qr || rb < ql) return 0LL;
else if(lb >= ql && rb <= qr) {
//cout<<"Enter: "<<lb<<", "<<rb<<" - "<<val<<"\n";
return val;
}
else {
ll a, b;
if(leftchild == NULL) a = 0LL;
else a = leftchild->query(ql, qr);
if(rightchild == NULL) b = 0LL;
else b = rightchild->query(ql, qr);
return gcd2(a, b);
}
}
};
class node_x {
public:
node_y *root;
node_x *leftchild, *rightchild;
int lb, rb;
node_x(int _lb, int _rb, int _lby, int _rby) {
lb = _lb; rb = _rb;
leftchild = rightchild = NULL;
root = new node_y(_lby, _rby);
}
void update(int x, int y, ll val) {
//cout<<"At x: "<<lb<<", "<<rb<<"\n";
root->update(y, val);
if(lb != rb) {
int mid = (lb + rb) / 2;
if(x <= mid) {
if(leftchild == NULL) {
leftchild = new node_x(lb, mid, 0, c-1);
}
leftchild -> update(x, y, val);
}
else {
if(rightchild == NULL) {
rightchild = new node_x(mid+1, rb, 0, c-1);
}
rightchild -> update(x, y, val);
}
}
}
ll query(int qlx, int qrx, int qly, int qry) {
if(lb > qrx || rb < qlx) {
return 0LL;
}
else if(lb >= qlx && rb <= qrx) {
//<<lb<<", "<<rb<<"\n";
ll x = root -> query(qly, qry);
return x;
}
else {
int mid = (lb + rb) / 2;
ll a, b;
if(leftchild == NULL) a = 0LL;
else a = leftchild->query(qlx, qrx, qly, qry);
if(rightchild == NULL) b = 0LL;
else b = rightchild -> query(qlx, qrx, qly, qry);
return gcd2(a, b);
}
}
};
node_x *root;
void init(int R, int C) {
r = R; c = C;
/*cout<<"Init: "<<gcd2(3696878681496, 20551290769769760)<<"\n";
vector<ll> v = {20551290769769760, 23127673031438976, 287635645813796280};
ll x = 0LL;
for(ll i:v) {
x = gcd2(i, x);
}
cout<<x<<"\n";*/
root = new node_x(0, r-1, 0, c-1);
}
void update(int P, int Q, long long K) {
//cout<<"Inserting "<<K<<" at ("<<P<<", "<<Q<<")\n";
root->update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return root->query(P, U, Q, V);
}
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 member function 'long long int node_x::query(int, int, int, int)':
game.cpp:119:17: warning: unused variable 'mid' [-Wunused-variable]
int mid = (lb + rb) / 2;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
