| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38627 |
2018-01-05T07:02:46 Z |
alenam0161 |
Game (IOI13_game) |
C++14 |
|
13 ms |
127156 KB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include "game.h"
#define pn node*
#define ps segtree*
using namespace std;
const int N = 1e9;
typedef long long ll;
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 node {
ll val;
int key;//index
int prior;
ll ans_tree;
node *l, *r;
node(int _X = 0, ll valu = 0ll) {
key = _X;
val = valu;
ans_tree = val;
prior = rand();
l = r = NULL;
}
};
void upd_ans(pn &t) {
if (t) {
t->ans_tree = gcd2(t->val,
gcd2(t->l ? t->l->ans_tree : 0ll, t->r ? t->r->ans_tree : 0ll)
);
}
}
void split(pn t, pn &l, pn &r, int key) {
if (!t) {
l = r = NULL; return;
}
if (t->key > key) {
split(t->l, l, t->l, key); r = t;
}
else {
split(t->r, t->r, r, key); l = t;
}
upd_ans(l);
upd_ans(r);
}
void merge(pn &t, pn l, pn r) {
if (!l || !r) {
t = l ? l : r;
}
else {
if (l->prior > r->prior) {
merge(l->r, l->r, r); t = l;
}
else {
merge(r->l, l, r->l); t = r;
}
}
upd_ans(t);
}
void insert(pn &t, pn it) {
if (!t) {
t = it;
}
else {
if (t->prior < it->prior) {
split(t, it->l, it->r, it->key); t = it;
}
else{
if (t->key > it->key) {
insert(t->l, it);
}
else insert(t->r, it);
}
}
upd_ans(t);
}
void erase(pn &t, int key) {
if (!t)return;
if (t->key == key) {
merge(t, t->l, t->r);
}
else {
if (t->key > key)erase(t->l, key);
else erase(t->r, key);
}
upd_ans(t);
}
struct segtree {
node *down;
segtree *l, *r;
segtree(node *U = NULL) {
down = U;
l = r = NULL;
}
};
ps root;
ps next_sg() {
static segtree SEG[2000 * 1000];
static int c1 = 0;
return &SEG[c1++];
}
pn next_node() {
static node an[2000 * 1000];
static int c2 = 0;
return &an[c2++];
}
void init(int R, int C) {
/* ... */
}
void printt(pn t, int lv = 0) {
if (!t)return;
printt(t->l, lv + 1);
cout <<" LEVEL "<<lv<<" "<< t->val << " " << t->ans_tree << " " << t->key << " " << t->prior << endl;
printt(t->r, lv + 1);
}
ll get_ans(pn t, int key) {
if (!t)return 0ll;
if (t->key == key)return t->val;
else {
if (t->key > key) {
return get_ans(t->l, key);
}
else return get_ans(t->r, key);
}
}
void update_sg(int x, int y, long long vl, ps& t, int l, int r) {
if (!t) {
t = next_sg();
}
if (l == r) {
erase(t->down, y);
pn cur = new node(y, vl);
insert(t->down, cur);
}
else {
int m = (l + r) / 2;
if (x <= m)update_sg(x, y, vl, t->l, l, m);
else update_sg(x, y, vl, t->r, m + 1, r);
ll a1 = t->l ? get_ans(t->l->down, y):0ll;
ll a2 = t->r ? get_ans(t->r->down, y):0ll;
erase(t->down, y);
pn cur = new node(y, gcd2(a1,a2));
insert(t->down, cur);
}
}
void update(int P, int Q, long long K) {
update_sg(P, Q, K,root, 0, N);
}
long long query_y(int l, int r, pn t) {
pn tl; pn tr;
split(t, tl, t, l - 1);
split(t, t, tr, r);
long long ans = t ? t->ans_tree:0ll;
merge(t, tl, t);
merge(t, t, tr);
return ans;
}
long long query_x(int xx, int xy, int yx, int yy, ps t, int l, int r) {
if (!t)return 0ll;
if (xx <= l&&r <= xy) {
return query_y(yx, yy, t->down);
}
else {
int m = (l + r) / 2;
long long cur = 0;
if (xx <= m)cur = gcd2(cur,query_x(xx, xy, yx, yy, t->l, l, m));
if (xy> m)cur = gcd2(cur, query_x(xx, xy, yx, yy, t->l, l, m));
return cur;
}
}
long long calculate(int P, int Q, int U, int V) {
return query_x(P,U,Q,V,root,0,N);
}
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 |
6 ms |
127156 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
127156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
127156 KB |
Output is correct |
| 2 |
Correct |
3 ms |
127024 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
127024 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
127156 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
127156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
127156 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
127156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
127156 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
127156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
