# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
924899 |
2024-02-10T03:37:10 Z |
12345678 |
Game (IOI13_game) |
C++17 |
|
3 ms |
860 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e9+5;
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;
}
struct segtree
{
struct node
{
ll vl;
node *l, *r, *t;
node(): vl(0), l(0), r(0), t(0){}
};
typedef node* pnode;
pnode rt=0;
ll value(pnode x) {return x?x->vl:0;}
void updatey(int l, int r, pnode &k, int y, ll vl)
{
if (!k) k=new node();
if (l==r) return k->vl=vl, void();
int md=(l+r)/2;
if (y<=md) updatey(l, md, k->l, y, vl);
else updatey(md+1, r, k->r, y, vl);
k->vl=gcd2(value(k->l), value(k->r));
}
void updatex(int l, int r, pnode &k, int x, int y, ll vl)
{
//printf("update x %d %d\n", l, r);
if (!k) k=new node();
updatey(0, nx, k->t, y, vl);
if (l==r) return k->vl=value(k->t), void();
int md=(l+r)/2;
if (x<=md) updatex(l, md, k->l, x, y, vl);
else updatex(md+1, r, k->r, x, y, vl);
k->vl=gcd2(value(k->l), value(k->r));
}
ll queryy(int l, int r, pnode &k, int ql, int qr)
{
if (r<ql||qr<l||!k) return 0;
if (ql<=l&&r<=qr) return k->vl;
int md=(l+r)/2;
return gcd2(queryy(l, md, k->l, ql, qr), queryy(md+1, r, k->r, ql, qr));
}
ll queryx(int l, int r, pnode &k, int ql, int a, int qr, int b)
{
if (r<ql||qr<l||!k) return 0;
if (ql<=l&&r<=qr) return queryy(0, nx, k->t, a, b);
int md=(l+r)/2;
return gcd2(queryx(l, md, k->l, ql, a, qr, b), queryx(md+1, r, k->r, ql, a, qr, b));
}
} s;
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
s.updatex(0, nx, s.rt, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return s.queryx(0, nx, s.rt, P, Q, U, V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |