oj.uz

Submission #363694

# Submission time Handle Problem Language Result Execution time Memory
363694 2021-02-06T21:51:31 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2925 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(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 5 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 3 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 1212 ms 141420 KB Output is correct
5 Correct 961 ms 141472 KB Output is correct
6 Correct 1199 ms 139260 KB Output is correct
7 Correct 1309 ms 143952 KB Output is correct
8 Correct 823 ms 86764 KB Output is correct
9 Correct 1270 ms 144268 KB Output is correct
10 Correct 1281 ms 143612 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 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 1708 ms 46544 KB Output is correct
13 Correct 1955 ms 24412 KB Output is correct
14 Correct 687 ms 2028 KB Output is correct
15 Correct 2221 ms 38012 KB Output is correct
16 Correct 2017 ms 67436 KB Output is correct
17 Correct 1901 ms 45036 KB Output is correct
18 Correct 2925 ms 67808 KB Output is correct
19 Correct 2622 ms 67728 KB Output is correct
20 Correct 2656 ms 67200 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 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 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 1292 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 1197 ms 145772 KB Output is correct
13 Correct 947 ms 145516 KB Output is correct
14 Correct 1233 ms 143992 KB Output is correct
15 Correct 1269 ms 143956 KB Output is correct
16 Correct 860 ms 86764 KB Output is correct
17 Correct 1257 ms 144240 KB Output is correct
18 Correct 1231 ms 143692 KB Output is correct
19 Correct 1612 ms 50464 KB Output is correct
20 Correct 1973 ms 28392 KB Output is correct
21 Correct 706 ms 6548 KB Output is correct
22 Correct 2229 ms 42420 KB Output is correct
23 Correct 2029 ms 71404 KB Output is correct
24 Correct 1953 ms 50028 KB Output is correct
25 Correct 2897 ms 72872 KB Output is correct
26 Correct 2687 ms 72940 KB Output is correct
27 Correct 2587 ms 72172 KB Output is correct
28 Runtime error 446 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 5 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 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 1191 ms 145716 KB Output is correct
13 Correct 947 ms 145388 KB Output is correct
14 Correct 1302 ms 144048 KB Output is correct
15 Correct 1256 ms 143628 KB Output is correct
16 Correct 846 ms 86716 KB Output is correct
17 Correct 1291 ms 144660 KB Output is correct
18 Correct 1243 ms 143776 KB Output is correct
19 Correct 1601 ms 50480 KB Output is correct
20 Correct 1950 ms 28268 KB Output is correct
21 Correct 683 ms 6512 KB Output is correct
22 Correct 2239 ms 42652 KB Output is correct
23 Correct 2040 ms 71748 KB Output is correct
24 Correct 1832 ms 50104 KB Output is correct
25 Correct 2879 ms 73000 KB Output is correct
26 Correct 2476 ms 72976 KB Output is correct
27 Correct 2389 ms 72172 KB Output is correct
28 Runtime error 436 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -