oj.uz

Submission #363691

# Submission time Handle Problem Language Result Execution time Memory
363691 2021-02-06T21:39:47 Z sofapuden Game (IOI13_game) C++14
36 / 100
 3416 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

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

long long mxN = 1e9+5;

struct seg1d{
	
	ll lb, rb, val;

	seg1d *l, *r;

	seg1d () : l(NULL), r(NULL), val(0) {}

	inline void init(ll lx, ll rx){
		lb = lx, rb = rx;
	}
	
	inline void ex(){
		ll mid = (lb+rb)>>1;
		l = new seg1d;
		l->init(lb,mid);
		r = new seg1d;
		r->init(mid+1,rb);
	}

	ll getGCD(ll llb, ll rrb){
		if(llb > rb || rrb < lb)return 0;
		if(llb <= lb && rrb >= rb)return val;
		if(l == NULL && r == NULL)return 0;
		return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
	}

	void ch(ll x, ll va){
		if(rb < x || lb > x)return;
		if(rb == x && lb == x){
			val = va;
			return;
		}
		if(l == NULL)ex();
		l->ch(x,va);
		r->ch(x,va);
		val = gcd2(l->val,r->val);
	}
	void chno(seg1d *a, seg1d *b, ll x){
		if(rb < x || lb > x)return;
		if(a->l == NULL)a->ex();
		if(b->l == NULL)b->ex();
		if(l == NULL)ex();
		val = gcd2(a->val,b->val);
		if(rb == lb)return;
		l->chno(a->l,b->l,x);
		r->chno(a->r,b->r,x);
	}



};

struct seg2d{
	
	ll lb, rb;

	seg2d *l, *r;
	seg1d *c;

	seg2d () : l(NULL), r(NULL), c(NULL) {}

	inline void init(ll lx, ll rx){
		lb = lx, rb = rx;
	}

	inline void ex(){
		ll mid = (lb+rb)>>1;
		l = new seg2d;
		l->init(lb,mid);
		r = new seg2d;
		r->init(mid+1,rb);
	}
	inline void exc(){
		c = new seg1d;
		c->init(0, mxN);
	}

	ll getGCD(ll llb, ll rrb, ll uub, ll ddb){
		if(llb > rb || rrb < lb)return 0;
		if(llb <= lb && rrb >= rb){
			if(c == NULL)return 0;
			return c->getGCD(uub,ddb);
		}
		if(l == NULL && r == NULL)return 0;
		return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
	}

	void ch(ll x, ll y, ll val){
		if(rb < x || lb > x)return;
		if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
		if(l == NULL)ex();
		if(c == NULL)exc();
		l->ch(x,y,val);
		r->ch(x,y,val);
		if(l->c == NULL)l->exc();
		if(r->c == NULL)r->exc();
		c->chno(l->c,r->c,y);
	}	
};

seg2d *root = new seg2d();

void init(int R, int C) {
    root->init(0,mxN);
}

void update(int P, int Q, long long K) {
    root->ch(P+1,Q+1,K);
}

long long calculate(int P, int Q, int U, int V) {
	return root->getGCD(P+1,U+1,Q+1,V+1);
}

Compilation message

game.cpp: In constructor 'seg1d::seg1d()':
game.cpp:24:13: warning: 'seg1d::r' will be initialized after [-Wreorder]
   24 |  seg1d *l, *r;
      |             ^
game.cpp:22:13: warning:   'll seg1d::val' [-Wreorder]
   22 |  ll lb, rb, val;
      |             ^~~
game.cpp:26:2: warning:   when initialized here [-Wreorder]
   26 |  seg1d () : l(NULL), r(NULL), val(0) {}
      |  ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 2284 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 2028 KB Output is correct
10 Correct 3 ms 1388 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1 ms 492 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Runtime error 1446 ms 256004 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 2156 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 2028 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 1901 ms 75908 KB Output is correct
13 Correct 2071 ms 40940 KB Output is correct
14 Correct 939 ms 7276 KB Output is correct
15 Correct 2469 ms 64364 KB Output is correct
16 Correct 2223 ms 114552 KB Output is correct
17 Correct 2393 ms 78652 KB Output is correct
18 Correct 3416 ms 115952 KB Output is correct
19 Correct 3158 ms 115744 KB Output is correct
20 Correct 3085 ms 115196 KB Output is correct
21 Correct 1 ms 492 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 2156 KB Output is correct
3 Correct 4 ms 2156 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 2156 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 2028 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Runtime error 1406 ms 256004 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 4 ms 2156 KB Output is correct
3 Correct 5 ms 2156 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 2156 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 4 ms 2028 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Runtime error 1415 ms 256004 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -