oj.uz

Submission #171171

# Submission time Handle Problem Language Result Execution time Memory
171171 2019-12-27T16:57:46 Z dennisstar Game (IOI13_game) C++11
37 / 100
 13000 ms 12576 KB 
#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
 
int R, C;
struct dt1 {
	dt1 *l1, *l2, *r1, *r2;
	ll dt;
	dt1() {l1=l2=r1=r2=NULL; dt=0;}
	inline void upd(int x, int y, ll val, int xs, int xe, int ys, int ye) {
		if (xs==xe&&ys==ye) {dt=val; return ;}
		int xm=(xs+xe)/2, ym=(ys+ye)/2;
		if (x<=xm) {
			if (y<=ym) {
				if (!l1) l1=new dt1();
				l1->upd(x, y, val, xs, xm, ys, ym);
			}
			else {
				if (!r1) r1=new dt1();
				r1->upd(x, y, val, xs, xm, ym+1, ye);
			}
		}
		else {
			if (y<=ym) {
				if (!l2) l2=new dt1();
				l2->upd(x, y, val, xm+1, xe, ys, ym);
			}
			else {
				if (!r2) r2=new dt1();
				r2->upd(x, y, val, xm+1, xe, ym+1, ye);
			}
		}
		ll L1, L2, R1, R2;
		L1=(l1?l1->dt:0); L2=(l2?l2->dt:0);
		R1=(r1?r1->dt:0); R2=(r2?r2->dt:0);
		dt=__gcd(__gcd(L1, L2), __gcd(R1, R2));
	}
	inline ll get(int x1, int x2, int y1, int y2, int xs, int xe, int ys, int ye) {
		if (x1<=xs&&xe<=x2&&y1<=ys&&ye<=y2) return dt;
		int xm=(xs+xe)/2, ym=(ys+ye)/2;
		ll L1, L2, R1, R2; L1=L2=R1=R2=0;
		if (!(xm<x1)) {
			if (!(ym<y1)) L1=(l1?l1->get(x1, x2, y1, y2, xs, xm, ys, ym):0);
			if (!(y2<ym+1)) R1=(r1?r1->get(x1, x2, y1, y2, xs, xm, ym+1, ye):0);
		}
		if (!(x2<xm+1)) {
			if (!(ym<y1)) L2=(l2?l2->get(x1, x2, y1, y2, xm+1, xe, ys, ym):0);
			if (!(y2<ym+1)) R2=(r2?r2->get(x1, x2, y1, y2, xm+1, xe, ym+1, ye):0);
		}
		return __gcd(__gcd(L1, L2), __gcd(R1, R2));
	}
};
 
dt1 *root=new dt1();
 
void init(int r_, int c_) {
	R=r_, C=c_;
}
 
void update(int P, int Q, ll K) {
	root->upd(P, Q, K, 0, R-1, 0, C-1);
}
 
ll calculate(int P, int Q, int U, int V) {
    return root->get(P, U, Q, V, 0, R-1, 0, C-1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 128 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1277 ms 12576 KB Output is correct
5 Correct 905 ms 12372 KB Output is correct
6 Correct 1096 ms 9848 KB Output is correct
7 Correct 1341 ms 9600 KB Output is correct
8 Correct 739 ms 8384 KB Output is correct
9 Correct 1191 ms 9632 KB Output is correct
10 Correct 1031 ms 9388 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 3 ms 424 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 6714 ms 10704 KB Output is correct
13 Execution timed out 13093 ms 3964 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1279 ms 12508 KB Output is correct
13 Correct 895 ms 12340 KB Output is correct
14 Correct 1070 ms 9896 KB Output is correct
15 Correct 1303 ms 9564 KB Output is correct
16 Correct 726 ms 8452 KB Output is correct
17 Correct 1269 ms 9728 KB Output is correct
18 Correct 1151 ms 9332 KB Output is correct
19 Correct 6725 ms 10592 KB Output is correct
20 Execution timed out 13057 ms 4016 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1309 ms 12464 KB Output is correct
13 Correct 891 ms 12224 KB Output is correct
14 Correct 1085 ms 9708 KB Output is correct
15 Correct 1371 ms 9724 KB Output is correct
16 Correct 739 ms 8312 KB Output is correct
17 Correct 1308 ms 9752 KB Output is correct
18 Correct 1115 ms 9220 KB Output is correct
19 Correct 6652 ms 10832 KB Output is correct
20 Execution timed out 13007 ms 4048 KB Time limit exceeded
21 Halted 0 ms 0 KB -