oj.uz

Submission #96978

# Submission time Handle Problem Language Result Execution time Memory
96978 2019-02-13T04:39:37 Z kig9981 Game (IOI13_game) C++17
0 / 100
 194 ms 230008 KB 
#include "game.h"
#include <bits/stdc++.h>
 
using namespace std;
 
struct Seg
{
	int l, r;
	long long v;
	Seg() : l(0), r(0), v(0) {}
};
 
const int MAX=1e9;
Seg tree[222222], tree2[14444444];
int tp1=1, tp2;
 
long long GCD(long long a, long long b)
{
	for(;b;a%=b,swap(a,b));
	return a;
}
 
long long get_gcd2(int n1, int n2, int p, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(p==0 || n2<s || e<n1) return 0;
    if(tree2[p].l<0) return n1<=-tree2[p].l && -tree2[p].l<=n2 ? tree2[p].v:0;
	if(n1<=s && e<=n2) return tree2[p].v;
	return GCD(get_gcd2(n1,n2,tree2[p].l,s,m),get_gcd2(n1,n2,tree2[p].r,m+1,e));
}
 
long long get_gcd(int x1, int x2, int y1, int y2, int p=1, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(p==0 || x2<s || e<x1) return 0;
	if(x1<=s && e<=x2) return get_gcd2(y1,y2,tree[p].v);
	return GCD(get_gcd(x1,x2,y1,y2,tree[p].l,s,m),get_gcd(x1,x2,y1,y2,tree[p].r,m+1,e));
}
 
void set_tree2(int n, long long v, int p, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree2[p].v=v;
		return;
	}
	if(tree2[p].l<0) {
        int t=-tree2[p].l;
		if(t==n) {
			tree2[p].v=v;
			return;
		}
        tree2[p].l=0;
		if(t<=m) {
			tree2[tree2[p].l=++tp2].l=-t;
			tree2[tree2[p].l].v=tree2[p].v;
        }
        else {
            tree2[tree2[p].r=++tp2].l=-t;
            tree2[tree2[p].r].v=tree2[p].v;
        }
        
    }
    if(tree2[p].l==0 && tree2[p].r==0) {
        tree2[p].v=v;
        tree2[p].l=-n;
        return;
    }
	if(n<=m) {
		if(tree2[p].l==0) tree2[p].l=++tp2;
		set_tree2(n,v,tree2[p].l,s,m);
	}
	else {
		if(tree2[p].r==0) tree2[p].r=++tp2;
		set_tree2(n,v,tree2[p].r,m+1,e);
	}
	tree2[p].v=GCD(tree2[tree2[p].l].v,tree2[tree2[p].r].v);
}
 
void set_tree(int x, int y, long long v, int p=1, int s=0, int e=MAX)
{
	int m=(s+e)>>1;
	if(tree[p].v==0) tree[p].v=++tp2;
	if(s==e) {
        set_tree2(y,v,tree[p].v);
        return;
    }
	if(x<=m) {
		if(tree[p].l==0) tree[p].l=++tp1;
		set_tree(x,y,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=++tp1;
		set_tree(x,y,v,tree[p].r,m+1,e);
	}
    set_tree2(y,GCD(get_gcd2(y,y,tree[tree[p].l].v),get_gcd2(y,y,tree[tree[p].r].v)),tree[p].v);
}
 
void init(int R, int C) {}
 
void update(int P, int Q, long long K) {set_tree(P,Q,K);}
 
long long calculate(int P, int Q, int U, int V) {return get_gcd(P,U,Q,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;
      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 230008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 229880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 194 ms 229932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 229928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 229976 KB Output isn't correct
2 Halted 0 ms 0 KB -