oj.uz

Submission #171131

# Submission time Handle Problem Language Result Execution time Memory
171131 2019-12-27T13:27:51 Z dennisstar Game (IOI13_game) C++11
63 / 100
 3881 ms 256004 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 *l, *r;
	ll dt;
	int md;
	dt1() {l=r=NULL; dt=0;}
	inline ll upd(int y, ll val, int fr, int re) {
		if (!(fr<=y&&y<=re)) return dt;
		if (fr==re) {dt=val; return dt;}
		md=(fr+re)/2;
		if (l==NULL) l=new dt1();
		if (r==NULL) r=new dt1();
		return dt=__gcd(l->upd(y, val, fr, md), r->upd(y, val, md+1, re));
	}
	inline ll get(int y1, int y2, int fr, int re) {
		if (fr>re||y2<fr||re<y1) return 0;
		if (y1<=fr&&re<=y2) return dt;
		md=(fr+re)/2;
		return __gcd((l?l->get(y1, y2, fr, md):0), (r?r->get(y1, y2, md+1, re):0));
	}
};

struct dt2 {
	dt2 *l, *r;
	dt1 *seg;
	int md; ll L, R;
	dt2() {l=r=NULL; seg=new dt1();}
	inline ll upd(int x, int y, ll val, int fr, int re) {
		if (!(fr<=x&&x<=re)) return seg->get(y, y, 0, C-1);
		if (fr==re) {seg->upd(y, val, 0, C-1); return val;}

		md=(fr+re)/2;
		if (l==NULL) l=new dt2();
		if (r==NULL) r=new dt2();
		L=l->upd(x, y, val, fr, md); R=r->upd(x, y, val, md+1, re); seg->upd(y, __gcd(L, R), 0, C-1);
		return __gcd(L, R);
	}
	inline ll get(int x1, int x2, int y1, int y2, int fr, int re) {
		if (fr>re||x2<fr||re<x1) return 0;
		if (x1<=fr&&re<=x2) return seg->get(y1, y2, 0, C-1);
		md=(fr+re)/2;
		return __gcd((l?(l->get(x1, x2, y1, y2, fr, md)):0), (r?(r->get(x1, x2, y1, y2, md+1, re)):0));
	}
};

dt2 *root=new dt2();

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);
}

ll calculate(int P, int Q, int U, int V) {
    return root->get(P, U, Q, V, 0, R-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 252 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 396 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 937 ms 29788 KB Output is correct
5 Correct 725 ms 29672 KB Output is correct
6 Correct 1070 ms 27580 KB Output is correct
7 Correct 1166 ms 27516 KB Output is correct
8 Correct 715 ms 18768 KB Output is correct
9 Correct 1075 ms 27428 KB Output is correct
10 Correct 964 ms 27112 KB Output is correct
11 Correct 3 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 0 ms 760 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 632 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1659 ms 35900 KB Output is correct
13 Correct 2807 ms 16516 KB Output is correct
14 Correct 467 ms 6056 KB Output is correct
15 Correct 3290 ms 23688 KB Output is correct
16 Correct 399 ms 48108 KB Output is correct
17 Correct 1894 ms 31776 KB Output is correct
18 Correct 3881 ms 49716 KB Output is correct
19 Correct 2636 ms 49960 KB Output is correct
20 Correct 2913 ms 49036 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 632 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 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 968 ms 29636 KB Output is correct
13 Correct 683 ms 29576 KB Output is correct
14 Correct 928 ms 27504 KB Output is correct
15 Correct 1049 ms 27208 KB Output is correct
16 Correct 634 ms 18680 KB Output is correct
17 Correct 973 ms 27596 KB Output is correct
18 Correct 895 ms 26992 KB Output is correct
19 Correct 1620 ms 35820 KB Output is correct
20 Correct 2695 ms 16472 KB Output is correct
21 Correct 446 ms 5984 KB Output is correct
22 Correct 3263 ms 23488 KB Output is correct
23 Correct 415 ms 48020 KB Output is correct
24 Correct 1749 ms 31736 KB Output is correct
25 Correct 3487 ms 49536 KB Output is correct
26 Correct 3433 ms 49852 KB Output is correct
27 Correct 3145 ms 49180 KB Output is correct
28 Runtime error 595 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 8 ms 632 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 997 ms 29844 KB Output is correct
13 Correct 677 ms 29700 KB Output is correct
14 Correct 928 ms 27604 KB Output is correct
15 Correct 1171 ms 27532 KB Output is correct
16 Correct 711 ms 18680 KB Output is correct
17 Correct 997 ms 27508 KB Output is correct
18 Correct 934 ms 27000 KB Output is correct
19 Correct 1628 ms 35876 KB Output is correct
20 Correct 2790 ms 16608 KB Output is correct
21 Correct 457 ms 5880 KB Output is correct
22 Correct 3377 ms 23720 KB Output is correct
23 Correct 429 ms 48088 KB Output is correct
24 Correct 2013 ms 31736 KB Output is correct
25 Correct 3560 ms 49472 KB Output is correct
26 Correct 2663 ms 49772 KB Output is correct
27 Correct 2877 ms 48936 KB Output is correct
28 Runtime error 638 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -