| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 218881 |
2020-04-03T00:58:45 Z |
Lawliet |
Game (IOI13_game) |
C++14 |
|
6 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef struct node* pnode;
pnode myNULL;
struct node
{
int x, y;
lli v, gcd;
pnode e, d;
node(int x, lli val)
: e(myNULL), d(myNULL), x(x), y( rand() ), v(val), gcd(val) {}
};
lli gcd(lli A, lli B)
{
if( B == 0 ) return A;
return gcd( B , A%B );
}
class Treap
{
public:
friend class SparseSegmentTree;
void recalculate(pnode t)
{
t->gcd = gcd( t->e->gcd , t->d->gcd );
t->gcd = gcd( t->gcd , t->v );
}
bool find(pnode t, lli cur)
{
if( t == myNULL ) return false;
if( t->x == cur ) return true;
if( t->x > cur ) return find( t->e , cur );
if( t->x < cur ) return find( t->d , cur );
}
void merge(pnode& t, pnode l, pnode r)
{
if( l == myNULL ) return void( t = r );
if( r == myNULL ) return void( t = l );
if( l->y < r->y ) merge( r->e , l , r->e ), t = r;
else merge( l->d , l->d , r ), t = l;
recalculate( t );
}
void split(pnode t, pnode& l, pnode& r, int k)
{
if( t == myNULL ) return void( l = r = myNULL );
if( t->x < k ) split( t->d , t->d , r , k ), l = t;
else split( t->e , l , t->e , k ), r = t;
recalculate( t );
}
void insert(pnode& t, int i, lli v)
{
pnode a, b, c;
split( t , a , b , i );
merge( t , a , new node( i , v ) );
merge( t , t , b );
}
void modify(pnode t, int x, lli v)
{
if( t->x == x ) t->v = v;
if( t->x > x ) modify( t->e , x , v );
if( t->x < x ) modify( t->d , x , v );
recalculate( t );
}
lli query(int Y1, int Y2)
{
pnode left, center, right;
split( root , left , center , Y1 );
split( center , center , right , Y2 + 1 );
lli ans = center->gcd;
merge( root , left , center );
merge( root , root , right );
return ans;
}
lli getGCDCell(pnode t, int x)
{
if( t == myNULL ) return 0;
if( t->x == x ) return t->gcd;
if( t->x > x ) return getGCDCell( t->e , x );
if( t->x < x ) return getGCDCell( t->d , x );
}
void update(int Y, lli val)
{
if( find( root , Y ) ) modify( root , Y , val );
else insert( root , Y , val );
}
Treap() { root = myNULL; }
private:
pnode root;
};
class SparseSegmentTree
{
public:
void create()
{
e.push_back( 0 );
d.push_back( 0 );
t.push_back( Treap() );
}
int getLeft(int node)
{
if( e[node] == 0 )
{
e[node] = ++cntNode;
create();
}
return e[node];
}
int getRight(int node)
{
if( d[node] == 0 )
{
d[node] = ++cntNode;
create();
}
return d[node];
}
void update(int node, int l, int r, int X, int Y, lli v)
{
if( l == r )
{
t[node].update( Y , v );
return;
}
int m = ( l + r )/2;
if( X <= m ) update( getLeft(node) , l , m , X , Y , v );
else update( getRight(node) , m + 1 , r , X , Y , v );
lli gcdLeft = t[ e[node] ].getGCDCell( t[ e[node] ].root , Y );
lli gcdRight = t[ d[node] ].getGCDCell( t[ d[node] ].root , Y );
t[node].update( Y , gcd( gcdLeft , gcdRight ) );
}
lli query(int node, int l, int r, int X1, int Y1, int X2, int Y2)
{
if( node == 0 ) return 0;
if( X2 < l || r < X1 ) return 0;
if( X1 <= l && r <= X2 ) return t[node].query( Y1 , Y2 );
int m = ( l + r )/2;
lli gcdLeft = query( e[node] , l , m , X1 , Y1 , X2 , Y2 );
lli gcdRight = query( d[node] , m + 1 , r , X1 , Y1 , X2 , Y2 );
return gcd( gcdLeft , gcdRight );
}
void init() { create(); create(); }
SparseSegmentTree() : cntNode(1) {}
private:
int cntNode;
vector< int > e, d;
vector< Treap > t;
};
int n, m;
SparseSegmentTree SEG;
void init(int R, int C)
{
n = R - 1;
m = C - 1;
myNULL = new node( 0 , 0 );
SEG.init();
}
void update(int P, int Q, long long K) { SEG.update( 1 , 0 , n , P , Q , K ); }
long long calculate(int P, int Q, int U, int V) { return SEG.query( 1 , 0 , n , 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;
^~~
game.cpp: In constructor 'node::node(int, lli)':
game.cpp:15:14: warning: 'node::d' will be initialized after [-Wreorder]
pnode e, d;
^
game.cpp:12:9: warning: 'int node::x' [-Wreorder]
int x, y;
^
game.cpp:17:5: warning: when initialized here [-Wreorder]
node(int x, lli val)
^~~~
game.cpp: In member function 'void Treap::insert(node*&, int, lli)':
game.cpp:70:25: warning: unused variable 'c' [-Wunused-variable]
pnode a, b, c;
^
game.cpp: In member function 'lli Treap::getGCDCell(pnode, int)':
game.cpp:107:9: warning: control reaches end of non-void function [-Wreturn-type]
}
^
game.cpp: In member function 'bool Treap::find(pnode, lli)':
game.cpp:45:9: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
