oj.uz

Submission #171172

# Submission time Handle Problem Language Result Execution time Memory
171172 2019-12-27T17:00:39 Z dennisstar Game (IOI13_game) C++11
37 / 100
 13000 ms 8440 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 (xs>xe||ys>ye) return 0;
		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 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 380 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1350 ms 8084 KB Output is correct
5 Correct 919 ms 8440 KB Output is correct
6 Correct 1084 ms 5288 KB Output is correct
7 Correct 1284 ms 5012 KB Output is correct
8 Correct 733 ms 4092 KB Output is correct
9 Correct 1153 ms 5008 KB Output is correct
10 Correct 1038 ms 4600 KB Output is correct
11 Correct 5 ms 376 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 6 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 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 6759 ms 6556 KB Output is correct
13 Execution timed out 13097 ms 1940 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 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 348 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 376 KB Output is correct
8 Correct 2 ms 428 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 256 KB Output is correct
12 Correct 1298 ms 8176 KB Output is correct
13 Correct 912 ms 8312 KB Output is correct
14 Correct 1092 ms 5280 KB Output is correct
15 Correct 1303 ms 5120 KB Output is correct
16 Correct 723 ms 4020 KB Output is correct
17 Correct 1171 ms 4988 KB Output is correct
18 Correct 1062 ms 4452 KB Output is correct
19 Correct 6974 ms 6496 KB Output is correct
20 Execution timed out 13093 ms 1996 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 3 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 2 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 256 KB Output is correct
11 Correct 2 ms 252 KB Output is correct
12 Correct 1331 ms 8020 KB Output is correct
13 Correct 927 ms 8320 KB Output is correct
14 Correct 1066 ms 5240 KB Output is correct
15 Correct 1323 ms 4956 KB Output is correct
16 Correct 732 ms 4056 KB Output is correct
17 Correct 1213 ms 4960 KB Output is correct
18 Correct 1066 ms 4668 KB Output is correct
19 Correct 6928 ms 6540 KB Output is correct
20 Execution timed out 13073 ms 1880 KB Time limit exceeded
21 Halted 0 ms 0 KB -