| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 281896 |
2020-08-23T15:27:11 Z |
shayan_p |
Game (IOI13_game) |
C++14 |
|
2 ms |
512 KB |
// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "game.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int N, M;
struct node{
ll g = 0, x = 0;
node *L = 0, *R = 0;
int pos = 0, S = 0;
node(int _pos, ll _g){
pos = _pos, g = _g, x = _g;
S = 1;
}
void rest(int _pos, ll _g){
pos = _pos, g = _g, x = _g;
S = 1;
}
ll ask(int _pos){
if(pos == _pos)
return x;
if(_pos < pos)
return (L ? L->ask(_pos) : 0);
else
return (R ? R->ask(_pos) : 0);
}
};
void build(node* nw){
nw->S = (nw->L ? nw->L->S : 0) + (nw->R ? nw->R->S : 0) + 1;
nw->g = __gcd(nw->x, __gcd( nw->L ? nw->L->g : 0, nw->R ? nw->R->g : 0 ));
}
pair<node*, node*> split(node* nw, int x){
if(nw == 0)
return {0, 0};
if(nw->pos < x){
auto it = split(nw->R, x);
nw->R = it.F;
build(nw);
return {nw, it.S};
}
else{
auto it = split(nw->L, x);
nw->L = it.S;
build(nw);
return {it.F, nw};
}
assert(0);
}
node* merge(node *A, node *B){
if(A == 0)
return B;
if(B == 0)
return A;
if((rand() % (A->S + B->S)) < A->S){
A->R = merge(A->R, B);
build(A);
return A;
}
else{
B->L = merge(A, B->L);
build(B);
return B;
}
assert(0);
}
pair<node*, ll> _ask(node *nw, int f, int s){
assert(nw);
auto A = split(nw, f);
auto B = split(A.S, s);
ll ans = B.F->g;
return {merge(A.F, merge(B.F, B.S)), ans};
}
node* _put(node *nw, int pos, ll x){
// assert(nw);
auto A = split(nw, pos);
auto B = split(A.S, pos+1);
node* r = B.F;
if(r == 0)
r = new node(pos, x);
else
r->rest(pos, x);
return merge(A.F, merge(r, B.S));
}
struct node2{
node* g = 0;
node2 *L = 0, *R = 0;
void put(int posx, int posy, ll x, int l = 0, int r = N){
ll num = x;
if(r-l > 1){
int mid = (l+r) >> 1;
if(posx < mid){
if(!L)
L = new node2();
L->put(posx, posy, x, l, mid);
}
else{
if(!R)
R = new node2();
R->put(posx, posy, x, mid, r);
}
num = __gcd(L ? L->g->ask(posy) : 0, R ? R->g->ask(posy) : 0);
}
if(!g)
g = new node(posy, num);
else
g = _put(g, posy, num);
}
ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){
if(r <= f || s <= l)
return 0;
if(f <= l && r <= s){
if(!g)
return 0;
auto it = _ask(g, ff, ss);
g = it.F;
return it.S;
}
int mid = (l+r) >> 1;
return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0);
}
};
node2* root;
void init(int N, int M){
srand(time(0));
::N = N, ::M = M;
root = new node2();
}
void update(int x, int y, ll w){
root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
return root->ask(x, ++xx, y, ++yy);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
18 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
416 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
