oj.uz

Submission #291248

# Submission time Handle Problem Language Result Execution time Memory
291248 2020-09-05T00:07:30 Z TMJN Game (IOI13_game) C++17
10 / 100
 13000 ms 8696 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

struct node{
	long long val;
	int lx,ly,rx,ry;
	int chl,chr;
};
 
node tree[4000000];
int c;


long long gcd2(long long X, long long Y) {
	long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void upd(int p,int q,long long k,int t){
//	cout<<t<<' '<<tree[t].lx<<' '<<tree[t].ly<<' '<<tree[t].rx<<' '<<tree[t].ry<<' '<<tree[t].val<<endl;
	if(tree[t].lx<=p&&p<=tree[t].rx&&tree[t].ly<=q&&q<=tree[t].ry){
		if(tree[t].lx==tree[t].rx&&tree[t].ly==tree[t].ry){
			tree[t].val=k;
		}
		else{
			if(tree[t].chl==-1){
				if(tree[t].rx-tree[t].lx==tree[t].ry-tree[t].ly){
					tree[c]={0,tree[t].lx,tree[t].ly,(tree[t].lx+tree[t].rx)/2,tree[t].ry,-1,-1};
					tree[c+1]={0,(tree[t].lx+tree[t].rx)/2+1,tree[t].ly,tree[t].rx,tree[t].ry,-1,-1};
					tree[t].chl=c;
					tree[t].chr=c+1;
					c+=2;
				}
				else{
					tree[c]={0,tree[t].lx,tree[t].ly,tree[t].rx,(tree[t].ly+tree[t].ry)/2,-1,-1};
					tree[c+1]={0,tree[t].lx,(tree[t].ly+tree[t].ry)/2+1,tree[t].rx,tree[t].ry,-1,-1};
					tree[t].chl=c;
					tree[t].chr=c+1;
					c+=2;
				}
			}
			upd(p,q,k,tree[t].chl);
			upd(p,q,k,tree[t].chr);
			tree[t].val=gcd2(tree[tree[t].chl].val,tree[tree[t].chr].val);
		}
	}
}

long long calc(int p,int q,int u,int v,int t){
	if(t==-1)return 0;
	if(tree[t].rx<p||u<tree[t].lx||tree[t].ry<q||v<tree[t].ly)return 0;
	if(p<=tree[t].lx&&tree[t].rx<=u&&q<=tree[t].ly&&tree[t].ry<=v)return tree[t].val;
	return gcd2(calc(p,q,u,v,tree[t].chl),calc(p,q,u,v,tree[t].chr));
}

void init(int R, int C) {
	tree[0].val=0;
	tree[0].lx=tree[0].ly=0;
	tree[0].rx=tree[0].ry=(1<<11)-1;
	tree[0].chl=-1;
	tree[0].chr=-1;
	c=1;
}

void update(int P, int Q, long long K) {
	upd(P,Q,K,0);
}

long long calculate(int P, int Q, int U, int V) {
	return calc(P,Q,U,V,0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 0 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 447 ms 1812 KB Output isn't correct
5 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 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 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 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 7493 ms 8696 KB Output is correct
13 Execution timed out 13036 ms 2676 KB Time limit exceeded
14 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 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 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 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 425 ms 1784 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 1 ms 384 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 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 469 ms 1784 KB Output isn't correct
13 Halted 0 ms 0 KB -