| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260240 |
2020-08-09T21:30:44 Z |
davitmarg |
Game (IOI13_game) |
C++17 |
|
2 ms |
640 KB |
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 100000;
#ifndef death
#include "game.h"
#endif
LL gcd(LL a, LL b)
{
if (!a || !b)
return a + b;
return gcd(b, a % b);
}
struct node
{
LL val = 0;
int l = 0, r = 0;
node(LL val=0)
{
this->val = val;
l = 0;
r = 0;
}
};
struct segtree
{
vector<node> t;
void addNode(int val = 0)
{
t.push_back(node());
}
segtree()
{
addNode();
}
LL get(int v, int l, int r, int i, int j)
{
if (i > j)
return 0;
if (l == i && r == j)
return t[v].val;
int m = (l + r) / 2;
LL res = 0;
if (t[v].l)
res = get(t[v].l, l, m, i, min(m, j));
if (t[v].r)
res = gcd(res, get(t[v].r, m + 1, r, max(m + 1, i), j));
return res;
}
void add(int v, int l, int r, int pos, LL val)
{
if (l == r)
{
t[v].val = val;
return;
}
int m = (l + r) / 2;
if (!t[v].l)
{
addNode();
t[v].l = t.size() - 1;
}
if (!t[v].r)
{
addNode();
t[v].r = t.size() - 1;
}
if (pos <= m)
add(t[v].l, l, m, pos, val);
else
add(t[v].r, m + 1, r, pos, val);
t[v].val = gcd(t[t[v].l].val, t[t[v].r].val);
}
};
struct node1
{
segtree val;
int l = 0, r = 0;
node1()
{
val = segtree();
l = 0;
r = 0;
}
};
vector<node1> t;
void addNode()
{
t.push_back(node1());
}
LL get(int v, int l, int r, int i, int j,int L,int R)
{
if (i > j)
return 0;
if (l == i && r == j)
return t[v].val.get(0, 0, N, L, R);
int m = (l + r) / 2;
LL res = 0;
if (t[v].l)
res = get(t[v].l, l, m, i, min(m, j), L, R);
if (t[v].r)
res = gcd(res, get(t[v].r, m + 1, r, max(m + 1, i), j, L, R));
return res;
}
void add(int v, int l, int r, int pos,int pos2, LL val)
{
t[v].val.add(0, 0, N, pos2, val);
if (l == r)
return;
int m = (l + r) / 2;
if (!t[v].l)
{
addNode();
t[v].l = t.size() - 1;
}
if (!t[v].r)
{
addNode();
t[v].r = t.size() - 1;
}
if (pos <= m)
add(t[v].l, l, m, pos,pos2, val);
else
add(t[v].r, m + 1, r, pos,pos2, val);
}
void init(int R, int C)
{
addNode();
}
LL calculate(int P, int Q, int U, int V)
{
return get(0, 0, N, P, U, Q, V);
}
void update(int P, int Q, LL K)
{
add(0, 0, N, P, Q, K);
}
#ifdef death
int main()
{
fastIO;
init(mod, mod);
update(1, 1, 10);
update(2, 2, 5);
cout << calculate(1, 1, 1, 1) << endl;
cout << calculate(0, 0, 1, 1) << endl;
cout << calculate(1, 1, 2, 2) << endl;
update(2, 2, 7);
cout << calculate(1, 1, 2, 2) << endl;
return 0;
}
#endif
/*
2
0 3
2
1 4
2
0 2
*/
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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
