| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 45223 |
2018-04-11T22:11:26 Z |
reality |
Game (IOI13_game) |
C++17 |
|
2 ms |
652 KB |
# include <bits/stdc++.h>
using namespace std;
# include <game.h>
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define db long double
# define pp pair < int , ll >
ll gcd(ll a,ll b)
{
return !b ? a : gcd(b,a % b);
}
struct treap
{
pp key;
int pr;
ll G = 0;
treap *l,*r;
void upd(void)
{
G = key.y;
if (l) G = gcd(G,l->G);
if (r) G = gcd(G,r->G);
}
treap(pp key,int pr,treap *l,treap *r) : key(key),pr(pr),l(l),r(r) {upd();}
treap(pp key) : key(key),pr(rand()+1) {l = r = 0;upd();}
};
typedef treap * tp;
struct seg
{
seg *l,*r;
tp t;
seg(seg *l,seg *r,tp t) : l(l),r(r),t(t) {}
seg(void) : l(0),r(0),t(0) {}
};
void print(const tp Root)
{
if (!Root) return;
print(Root->l);
cerr << Root->key.x << ' ' << Root->key.y << '\n';
print(Root->r);
}
int Count = 0;
typedef seg * sg;
tp Merge(const tp a,const tp b)
{
if (!a) return b;
if (!b) return a;
if (a->pr > b->pr) return new treap(a->key,a->pr,a->l,Merge(a->r,b));
else return new treap(b->key,b->pr,Merge(a,b->l),b->r);
}
void split(const tp Root,pp K,tp &left,tp &right)
{
left = right = 0;
if (!Root) return;
if (Root->key <= K)
{
split(Root->r,K,left,right);
left = new treap(Root->key,Root->pr,Root->l,left);
}
else
{
split(Root->l,K,left,right);
right = new treap(Root->key,Root->pr,right,Root->r);
}
}
void add(tp &Root,pp Val)
{
tp left,right;
split(Root,Val,left,right);
Root = Merge(Merge(left,new treap(Val)),right);
}
void del(tp &Root,pp Val)
{
if (!Root) return;
if (Root->key == Val) Root = Merge(Root->l,Root->r);
else
if (Root->key < Val) del(Root->r,Val);
else del(Root->l,Val);
}
const ll inf = 1e18 + 5;
ll Get(const tp Root,int p,int u)
{
tp left,mid,right;
split(Root,{p-1,inf},left,mid);
split(mid,{u,inf},left,right);
return (!left ? 0 : left->G);
}
ll Acc(const tp Root,int pos)
{
if (!Root) return -1;
else
if (Root->key.x == pos) return Root->key.y;
else
if (Root->key.x < pos) return Acc(Root->r,pos);
else return Acc(Root->l,pos);
}
ll update(int p,int u,int pos1,int pos2,ll val,sg &Root)
{
if (!Root) Root = new seg();
if (p == u)
{
ll is = Acc(Root->t,pos2);
if (is != -1) del(Root->t,{pos2,is});
add(Root->t,{pos2,val});
return is;
}
else
{
int m = (p + u) / 2;
ll is = -1;
if (pos1 <= m) is = update(p,m,pos1,pos2,val,Root->l);
else is = update(m+1,u,pos1,pos2,val,Root->r);
if (is != -1) del(Root->t,{pos2,is});
add(Root->t,{pos2,val});
return is;
}
}
ll query(int p,int u,int l1,int r1,int l2,int r2,const sg Root)
{
if (!Root) return 0;
if (l1 <= p && u <= r1) return Get(Root->t,l2,r2);
int m = (p + u) / 2;
ll ans = 0;
if (l1 <= m) ans = gcd(ans,query(p,m,l1,r1,l2,r2,Root->l));
if (m+1<=r1) ans = gcd(ans,query(m+1,u,l1,r1,l2,r2,Root->r));
return ans;
}
sg Root = 0;
int n,m;
void init(int a,int b)
{
n = a;m = b;
}
void update(int l,int r,ll Val)
{
update(1,n,l,r,Val,Root);
}
ll calculate(int l1,int r1,int l2,int r2)
{
return query(1,n,l1+1,l2+1,r1+1,r2+1,Root);
}
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 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
