oj.uz

Submission #281911

# Submission time Handle Problem Language Result Execution time Memory
281911 2020-08-23T15:37:31 Z shayan_p Game (IOI13_game) C++14
0 / 100
 1 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();
}

map<int, node*> mp;

void update(int x, int y, ll w){
    if(mp.count(x) == 0)
	mp[x] = new node(y, w);
    else
	mp[x] = _put(mp[x], y, w);
    
    //    root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
    vector<pair<int, node*> > tmp;
    ll ans = 0;
    for(auto it : mp){
	if(x <= it.F && it.F <= xx){
	    auto x = _ask(it.S, y, yy+1);
	    ans = __gcd(ans, x.S);
	    tmp.PB({it.F, x.F});
	}
    }
    for(auto it : tmp){
	mp[it.F] = it.S;
    }
    return ans;
    // 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;
      |      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Runtime error 1 ms 512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Runtime error 1 ms 384 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 1 ms 384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 1 ms 384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Runtime error 1 ms 384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -