oj.uz

Submission #281936

# Submission time Handle Problem Language Result Execution time Memory
281936 2020-08-23T15:58:03 Z shayan_p Game (IOI13_game) C++14
37 / 100
 13000 ms 9064 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 ? B.F->g : 0);
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 2088 ms 8952 KB Output is correct
5 Correct 673 ms 8568 KB Output is correct
6 Correct 1956 ms 6264 KB Output is correct
7 Correct 2341 ms 5996 KB Output is correct
8 Correct 1567 ms 6072 KB Output is correct
9 Correct 2207 ms 6036 KB Output is correct
10 Correct 2023 ms 5744 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Execution timed out 13087 ms 5440 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2080 ms 9064 KB Output is correct
13 Correct 673 ms 8704 KB Output is correct
14 Correct 1972 ms 6148 KB Output is correct
15 Correct 2306 ms 5724 KB Output is correct
16 Correct 1559 ms 5960 KB Output is correct
17 Correct 2239 ms 6220 KB Output is correct
18 Correct 2003 ms 5600 KB Output is correct
19 Execution timed out 13017 ms 5480 KB Time limit exceeded
20 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 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 2136 ms 8688 KB Output is correct
13 Correct 712 ms 8336 KB Output is correct
14 Correct 1973 ms 5560 KB Output is correct
15 Correct 2316 ms 4896 KB Output is correct
16 Correct 1572 ms 5368 KB Output is correct
17 Correct 2234 ms 5296 KB Output is correct
18 Correct 2025 ms 4656 KB Output is correct
19 Execution timed out 13078 ms 5240 KB Time limit exceeded
20 Halted 0 ms 0 KB -