oj.uz

Submission #363758

# Submission time Handle Problem Language Result Execution time Memory
363758 2021-02-07T08:24:01 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2501 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 = 1<<30;
 
struct seg1d{
	
	int lb, rb;
	ll val;
 
	seg1d *l, *r;
 
	seg1d () : l(NULL), r(NULL), val(0) {}
 
	inline void init(int lx, int rx){
		lb = lx, rb = rx;
	}
	
	inline void exl(){
		int mid = (lb+rb)>>1;
		l = new seg1d;
		l->init(lb,mid);
	}
	inline void exr(){
		int mid = (lb+rb)>>1;
		r = new seg1d;
		r->init(mid+1,rb);
	}
 
	ll getGCD(int llb, int rrb){
		if(llb > rb || rrb < lb)return 0;
		if(llb <= lb && rrb >= rb)return val;
		if(l == NULL && r == NULL)return 0;
		if(l == NULL)return r->getGCD(llb,rrb);
		if(r == NULL)return l->getGCD(llb,rrb);
		return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
	}
 
	inline void ch(int x, ll va){
		if(rb < x || lb > x)return;
		if(rb == x && lb == x){
			val = va;
			return;
		}
		int mid = (lb+rb)>>1;
		if(mid >= x){
			if(l == NULL)exl();
			l->ch(x,va);
			if(r == NULL)val = l->val;
			else val = gcd2(l->val,r->val);
		}
		else{
			if(r == NULL)exr();
			r->ch(x,va);
			if(l == NULL)val = r->val;
			else val = gcd2(l->val,r->val);
		}
	}
	inline void chno(seg1d *a, seg1d *b, int x){
		if(rb < x || lb > x)return;
		int mid = (lb+rb)>>1;
		if(mid >= x){
			if(a == NULL){
				val = b->val;
				if(rb == lb)return;
				if(l == NULL)exl();
				l->chno(a,b->l,x);
				return;
			}
			if(b == NULL){
				val = a->val;
				if(rb == lb)return;
				if(l == NULL)exl();
				l->chno(a->l,b,x);
				return;
			}
			val = gcd2(a->val,b->val);
			if(rb == lb)return;
			if(l == NULL)exl();
			l->chno(a->l,b->l,x);
		}
		else{
			if(a == NULL){
				val = b->val;
				if(rb == lb)return;
				if(r == NULL)exr();
				r->chno(a,b->r,x);
				return;
			}
			if(b == NULL){
				val = a->val;
				if(rb == lb)return;
				if(r == NULL)exr();
				r->chno(a->r,b,x);
				return;
			}
			val = gcd2(a->val,b->val);
			if(rb == lb)return;
			if(r == NULL)exr();
			r->chno(a->r,b->r,x);
		}
	}
};
 
struct seg2d{
	
	int lb, rb;
 
	seg2d *l, *r;
	seg1d *c;
 
	seg2d () : l(NULL), r(NULL), c(NULL) {}
 
	inline void init(int lx, int rx){
		lb = lx, rb = rx;
	}
 
	inline void exl(){
		int mid = (lb+rb)>>1;
		l = new seg2d;
		l->init(lb,mid);
	}
	inline void exr(){
		int mid = (lb+rb)>>1;
		r = new seg2d;
		r->init(mid+1,rb);
	}
	inline void exc(){
		c = new seg1d;
		c->init(0, mxN);
	}
 
	ll getGCD(int llb, int rrb, int uub, int 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;
		if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
		if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
		return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
	}
 
	inline void ch(int x, int y, ll val){
		if(rb < x || lb > x)return;
		if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
		int mid = (rb+lb)>>1;
		if(mid >= x){
			if(l == NULL)exl();
			if(c == NULL)exc();
			l->ch(x,y,val);
			if(r == NULL){
				exr();
			}
			c->chno(l->c,r->c,y);
		}
		else{
			if(r == NULL)exr();
			if(c == NULL)exc();
			r->ch(x,y,val);
			if(l == NULL){
				exl();
			}
			c->chno(l->c,r->c,y);
		}
	}	
};
 
seg2d root;
 
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:25:13: warning: 'seg1d::r' will be initialized after [-Wreorder]
   25 |  seg1d *l, *r;
      |             ^
game.cpp:23:5: warning:   'll seg1d::val' [-Wreorder]
   23 |  ll val;
      |     ^~~
game.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  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 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 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 364 KB Output is correct
4 Correct 921 ms 72812 KB Output is correct
5 Correct 656 ms 73964 KB Output is correct
6 Correct 965 ms 71916 KB Output is correct
7 Correct 1038 ms 71532 KB Output is correct
8 Correct 662 ms 43500 KB Output is correct
9 Correct 1016 ms 72032 KB Output is correct
10 Correct 989 ms 71276 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 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1383 ms 26676 KB Output is correct
13 Correct 1887 ms 13804 KB Output is correct
14 Correct 480 ms 2540 KB Output is correct
15 Correct 2087 ms 20844 KB Output is correct
16 Correct 1623 ms 35180 KB Output is correct
17 Correct 1491 ms 24508 KB Output is correct
18 Correct 2464 ms 35436 KB Output is correct
19 Correct 2144 ms 35948 KB Output is correct
20 Correct 2089 ms 35104 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 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 900 ms 73912 KB Output is correct
13 Correct 676 ms 74112 KB Output is correct
14 Correct 950 ms 71660 KB Output is correct
15 Correct 1028 ms 71404 KB Output is correct
16 Correct 659 ms 43500 KB Output is correct
17 Correct 1018 ms 71660 KB Output is correct
18 Correct 1004 ms 71492 KB Output is correct
19 Correct 1368 ms 26748 KB Output is correct
20 Correct 1892 ms 14232 KB Output is correct
21 Correct 482 ms 2668 KB Output is correct
22 Correct 2070 ms 20844 KB Output is correct
23 Correct 1625 ms 35436 KB Output is correct
24 Correct 1475 ms 24812 KB Output is correct
25 Correct 2410 ms 35692 KB Output is correct
26 Correct 2086 ms 35820 KB Output is correct
27 Correct 2045 ms 35180 KB Output is correct
28 Runtime error 677 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 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 909 ms 73196 KB Output is correct
13 Correct 652 ms 73452 KB Output is correct
14 Correct 961 ms 71128 KB Output is correct
15 Correct 1034 ms 71020 KB Output is correct
16 Correct 674 ms 43016 KB Output is correct
17 Correct 1051 ms 71404 KB Output is correct
18 Correct 999 ms 70764 KB Output is correct
19 Correct 1365 ms 25964 KB Output is correct
20 Correct 1891 ms 13488 KB Output is correct
21 Correct 489 ms 2156 KB Output is correct
22 Correct 2083 ms 20072 KB Output is correct
23 Correct 1631 ms 34668 KB Output is correct
24 Correct 1506 ms 23824 KB Output is correct
25 Correct 2501 ms 35308 KB Output is correct
26 Correct 2179 ms 35180 KB Output is correct
27 Correct 2099 ms 34668 KB Output is correct
28 Runtime error 676 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -