oj.uz

Submission #897986

# Submission time Handle Problem Language Result Execution time Memory
897986 2024-01-04T06:48:37 Z MuhammadSaram Game (IOI13_game) C++17
0 / 100
 1 ms 860 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
 
#define ll long long
 
int r,c;
const int M = 2000;
 
struct nodey
{
	int mny,mxy;
	ll val=0;
	nodey *le;
	nodey *ri;
	void modify(int y,ll va)
	{
		if (mny+1==mxy)
		{
			val=va;
			return;
		}
		int mid=(mny+mxy)/2;
		if (y<mid)
		{
			if (le==NULL)
			{
				le=new nodey;
				le->mny=mny,le->mxy=mid;
			}
			le->modify(y,va);
		}
		else
		{
			if (ri==NULL)
			{
				ri=new nodey;
				ri->mny=mid,ri->mxy=mxy;
			}
			ri->modify(y,va);
		}
		if(le==NULL)
			val=ri->val;
		else if(ri==NULL)
			val=le->val;
		else
			val=__gcd(le->val,ri->val);
	}
	int get(int l,int r)
	{
		if (mxy<=l or r<=mny)
			return (ll)0;
		if (l<=mny and mxy<=r)
			return val;
		if (le==NULL and ri==NULL)
			return (ll)0;
		else if(le==NULL)
			return ri->get(l,r);
		else if(ri==NULL)
			return le->get(l,r);
		return __gcd(ri->get(l,r),le->get(l,r));
	}
};
 
struct nodex
{
	nodey *segy;
};
 
 
nodex seg[M*4];
 
void modify(int x,int y,ll va,int v=1,int s=0,int e=M)
{
	seg[v].segy->modify(y,va);
	if (s+1==e)
		return;
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (x<mid)
		modify(x,y,va,lc,s,mid);
	else
		modify(x,y,va,rc,mid,e);
}
 
ll get(int lx,int rx,int ly,int ry,int v=1,int s=0,int e=M)
{
	if (e<=lx or rx<=s)
		return (ll)0;
	if (lx<=s and e<=rx)
		return seg[v].segy->get(ly,ry);
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	return __gcd(get(lx,rx,ly,ry,lc,s,mid),get(lx,rx,ly,ry,rc,mid,e));
}
 
void init(int R, int C)
{
	r=R,c=C;
	for (int i=0;i<M*4;i++)
	{
		seg[i].segy=new nodey;
		seg[i].segy->mny=0,seg[i].segy->mxy=M;
	}
}
void update(int P, int Q, long long K)
{
	modify(P,Q,K);
}
long long calculate(int P, int Q, int U, int V)
{
	return get(P,U+1,Q,V+1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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