| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1013609 |
2024-07-03T17:21:48 Z |
parsadox2 |
Game (IOI13_game) |
C++17 |
|
1 ms |
436 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
struct SEG{
struct NODE{
int lc , rc , l , r;
long long g;
NODE(){
lc = 0; rc = 0;
g = 0;
}
};
vector <NODE> t;
NODE emp;
void Build()
{
t.push_back(emp);
t.push_back(emp);
t[1].l = 0;
t[1].r = M;
}
void Make_child(int par , int now)
{
int mid = (t[par].l + t[par].r) >> 1;
if(t[now].l < mid)
t[par].lc = now;
else
t[par].rc = now;
}
void Set(int id , long long vl , int par = 1 , int node = 1 , int nl = 0 , int nr = M)
{
if(par != node && t[node].l == nl && t[node].r == nr)
{
Set(id , vl , node , node , nl , nr);
return;
}
if(nr - nl == 1)
{
t[node].g = vl;
return;
}
int mid = (nl + nr) >> 1;
if(par == node)
{
if(id < mid)
{
if(t[node].lc == 0)
{
int nd = t.size(); t.push_back(emp);
t[nd].l = id; t[nd].r = id + 1; t[nd].g = vl;
t[node].lc = nd;
t[node].g = gcd2(t[t[node].rc].g , vl);
return;
}
Set(id , vl , node , t[node].lc , nl , mid);
}
else
{
if(t[node].rc == 0)
{
int nd = t.size(); t.push_back(emp);
t[nd].l = id; t[nd].r = id + 1; t[nd].g = vl;
t[node].rc = nd;
t[node].g = gcd2(t[t[node].lc].g , vl);
return;
}
Set(id , vl , node , t[node].rc , mid , nr);
}
t[node].g = gcd2(t[t[node].lc].g , t[t[node].rc].g);
return;
}
else
{
if(id < mid && t[node].l < mid)
{
Set(id , vl , par , node , nl , mid);
return;
}
else if(id >= mid && t[node].l >= mid)
{
Set(id , vl , par , node , mid , nr);
return;
}
int nd = t.size(); t.push_back(emp);
int p = t.size(); t.push_back(emp);
t[nd].l = id; t[nd].r = id + 1; t[nd].g = vl;
t[p].l = nl; t[p].r = nr;
Make_child(p , node);
Make_child(p , nd);
Make_child(par , p);
t[p].g = gcd2(t[t[p].lc].g , t[t[p].rc].g);
return;
}
}
long long Get(int l , int r , int node = 1 , int nl = 0 , int nr = M)
{
if(r <= nl || nr <= l)
return 0;
if(l <= nl && nr <= r)
{
//cout << node << " " << nl << " " << nr << " : " << t[node].g << endl;
return t[node].g;
}
long long res = 0;
if(t[node].lc != 0)
res = gcd2(res , Get(l , r , t[node].lc , t[t[node].lc].l , t[t[node].lc].r));
if(t[node].rc != 0)
res = gcd2(res , Get(l , r , t[node].rc , t[t[node].rc].l , t[t[node].rc].r));
return res;
}
};
struct SEG2{
struct NODE{
int lc , rc;
SEG s;
};
NODE emp;
vector <NODE> t;
void Build()
{
emp.s.Build();
emp.lc = 0;
emp.rc = 0;
t.push_back(emp);
t.push_back(emp);
}
void Set(int id , int a , long long b , int node = 1 , int nl = 0 , int nr = N)
{
int nd = node;
if(nr - nl == 1)
{
t[nd].s.Set(a , b);
return;
}
int mid = (nl + nr) >> 1;
if(id < mid)
{
if(t[nd].lc == 0)
{
t[nd].lc = t.size();
t.push_back(emp);
}
Set(id , a , b , t[nd].lc , nl , mid);
}
else
{
if(t[nd].rc == 0)
{
t[nd].rc = t.size();
t.push_back(emp);
}
Set(id , a , b , t[nd].rc , mid , nr);
}
t[nd].s.Set(a , gcd2(t[t[nd].lc].s.Get(a , a + 1) , t[t[nd].rc].s.Get(a , a + 1)));
}
long long Get(int l , int r , int s , int e , int node = 1 , int nl = 0 , int nr = N)
{
if(r <= nl || nr <= l)
return 0;
if(l <= nl && nr <= r)
{
long long x = t[node].s.Get(s , e);
return x;
}
int mid = (nl + nr) >> 1;
return gcd2(Get(l , r , s , e , t[node].lc , nl , mid) , Get(l , r , s , e , t[node].rc , mid , nr));
}
} seg;
void init(int R, int C) {
seg.Build();
M = C;
N = R;
}
void update(int P, int Q, long long K) {
seg.Set(P , Q , K);
}
long long calculate(int P, int Q, int U, int V) {
int l = min(P , U) , r = max(P , U);
int s = min(Q , V) , e = max(Q , V);
return seg.Get(l , r + 1 , s , e + 1);
}
/*signed main()
{
int R, C, N;
int P, Q, U, V;
long long K;
int i, type;
assert(scanf("%d", &R) == 1);
assert(scanf("%d", &C) == 1);
assert(scanf("%d", &N) == 1);
init(R, C);
std::vector<long long> answers;
for (i = 0; i < N; i++) {
assert(scanf("%d", &type) == 1);
if (type == 1) {
assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
update(P, Q, K);
} else if (type == 2) {
assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
answers.push_back(calculate(P, Q, U, V));
}
}
for (auto answer: answers) {
printf("%lld\n", answer);
}
return 0;
}*/
/*
2 3 4
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
