oj.uz

Submission #363695

# Submission time Handle Problem Language Result Execution time Memory
363695 2021-02-06T21:55:09 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2938 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+69;

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(l == NULL)ex();
		if(a == NULL){
			val = b->val;
			if(rb == lb)return;
			l->chno(a,b->l,x);
			r->chno(a,b->r,x);
			return;
		}
		if(b == NULL){
			val = a->val;
			if(rb == lb)return;
			l->chno(a->l,b,x);
			r->chno(a->r,b,x);
			return;
		}
		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);
		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 1 ms 364 KB Output is correct
2 Correct 3 ms 1388 KB Output is correct
3 Correct 3 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1516 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 1388 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1174 ms 141420 KB Output is correct
5 Correct 930 ms 141540 KB Output is correct
6 Correct 1245 ms 139500 KB Output is correct
7 Correct 1310 ms 139500 KB Output is correct
8 Correct 894 ms 82584 KB Output is correct
9 Correct 1326 ms 140140 KB Output is correct
10 Correct 1248 ms 139276 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1388 KB Output is correct
3 Correct 4 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1649 ms 46676 KB Output is correct
13 Correct 2028 ms 24468 KB Output is correct
14 Correct 680 ms 2028 KB Output is correct
15 Correct 2341 ms 38348 KB Output is correct
16 Correct 2049 ms 67308 KB Output is correct
17 Correct 2028 ms 45400 KB Output is correct
18 Correct 2938 ms 67724 KB Output is correct
19 Correct 2651 ms 67836 KB Output is correct
20 Correct 2521 ms 67112 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 4 ms 1516 KB Output is correct
3 Correct 3 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1286 ms 141556 KB Output is correct
13 Correct 954 ms 141804 KB Output is correct
14 Correct 1205 ms 139620 KB Output is correct
15 Correct 1231 ms 139372 KB Output is correct
16 Correct 833 ms 82788 KB Output is correct
17 Correct 1276 ms 140064 KB Output is correct
18 Correct 1222 ms 139244 KB Output is correct
19 Correct 1585 ms 46580 KB Output is correct
20 Correct 1921 ms 24544 KB Output is correct
21 Correct 710 ms 2208 KB Output is correct
22 Correct 2228 ms 38456 KB Output is correct
23 Correct 2008 ms 67580 KB Output is correct
24 Correct 1906 ms 45440 KB Output is correct
25 Correct 2796 ms 67828 KB Output is correct
26 Correct 2557 ms 67996 KB Output is correct
27 Correct 2556 ms 67464 KB Output is correct
28 Runtime error 479 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1388 KB Output is correct
3 Correct 4 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 2 ms 884 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1179 ms 141548 KB Output is correct
13 Correct 927 ms 141600 KB Output is correct
14 Correct 1194 ms 139644 KB Output is correct
15 Correct 1223 ms 139312 KB Output is correct
16 Correct 835 ms 82668 KB Output is correct
17 Correct 1247 ms 140132 KB Output is correct
18 Correct 1183 ms 139372 KB Output is correct
19 Correct 1584 ms 46672 KB Output is correct
20 Correct 1906 ms 24788 KB Output is correct
21 Correct 684 ms 2156 KB Output is correct
22 Correct 2209 ms 38252 KB Output is correct
23 Correct 1975 ms 67564 KB Output is correct
24 Correct 1870 ms 45688 KB Output is correct
25 Correct 2812 ms 68204 KB Output is correct
26 Correct 2614 ms 68204 KB Output is correct
27 Correct 2555 ms 67308 KB Output is correct
28 Runtime error 445 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -