| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 140297 |
2019-08-02T13:45:45 Z |
Noam527 |
Game (IOI13_game) |
C++17 |
|
4 ms |
376 KB |
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;
#include "game.h"
ll gcd(ll x, ll y) {
return !y ? x : gcd(y, x % y);
}
int rnd() {
return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}
struct node {
node *l, *r;
int pos, key, mn, mx;
ll val, g;
node(int position, ll value) {
l = r = nullptr;
mn = mx = pos = position;
key = rnd();
val = g = value;
}
void upd() {
g = val;
if (l) g = gcd(g, l->g);
if (r) g = gcd(g, r->g);
mn = (l ? l->mn : pos);
mx = (r ? r->mx : pos);
}
};
struct treap {
node *root;
treap() {
root = nullptr;
srand(rnd());
}
void split(node *t, int pos, node *&l, node *&r) {
if (t == nullptr) {
l = r = nullptr;
return;
}
if (t->pos < pos) {
split(t->r, pos, l, r);
t->r = l;
l = t;
}
else {
split(t->l, pos, l, r);
t->l = r;
r = t;
}
t->upd();
}
node* merge(node *l, node *r) {
if (!l || !r) return l ? l : r;
if (l->key < r->key) {
l->r = merge(l->r, r);
l->upd();
return l;
}
r->l = merge(l, r->l);
r->upd();
return r;
}
bool find(int pos) {
node *t = root;
while (t) {
if (t->pos == pos) return true;
if (t->pos > pos) t = t->l;
else t = t->r;
}
return false;
}
void upd(node *t, int pos, ll val) {
if (t->pos == pos) {
t->val = val;
t->upd();
return;
}
if (t->pos > pos)
upd(t->l, pos, val);
else
upd(t->r, pos, val);
t->upd();
}
void insert(int pos, ll val) {
if (find(pos)) upd(root, pos, val);
else {
node *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new node(pos, val)), r);
}
}
ll query(node *t, int st, int en) {
if (t->mx < st || en < t->mn) return 0;
if (st <= t->mn && t->mx <= en) return t->g;
ll rtn = (st <= t->pos && t->pos <= en ? t->val : 0);
if (t->l) rtn = gcd(rtn, query(t->l, st, en));
if (t->r) rtn = gcd(rtn, query(t->r, st, en));
return rtn;
}
ll query(int st, int en) {
if (!root) return 0;
return query(root, st, en);
}
void print(node *t) {
if (!t) return;
print(t->l);
cout << t->val << " ";
print(t->r);
}
};
struct segtree {
segtree *l, *r;
treap T;
int lo, hi;
segtree() {
l = r = nullptr;
}
segtree(int st, int en) {
l = r = nullptr;
lo = st, hi = en;
}
void createl() {
if (!l) l = new segtree(lo, (lo + hi) / 2);
}
void creater() {
if (!r) r = new segtree((lo + hi) / 2 + 1, hi);
}
void fix(int pos) {
ll val = 0;
if (l) val = gcd(val, l->T.query(pos, pos));
if (r) val = gcd(val, r->T.query(pos, pos));
T.insert(pos, val);
}
void upd(int x, int y, ll val) {
if (hi < x || x < lo) return;
if (lo == hi) {
T.insert(y, val);
return;
}
if (lo != hi) {
if (x <= (lo + hi) / 2) {
createl();
l->upd(x, y, val);
}
else {
creater();
r->upd(x, y, val);
}
}
fix(y);
}
ll query(int t, int b, int st, int en) {
if (hi < t || b < lo) return 0;
if (t <= lo && hi <= b) return T.query(st, en);
ll rtn = 0;
if (l)
rtn = gcd(rtn, l->query(t, b, st, en));
if (r)
rtn = gcd(rtn, r->query(t, b, st, en));
return rtn;
}
};
int r, c, q;
segtree T;
void init(int R, int C) {
srand(12341234);
r = R;
c = C;
T = segtree(0, r - 1);
}
void update(int P, int Q, ll K) {
T.upd(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return T.query(P, Q, U, 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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
360 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
