oj.uz

Submission #171127

# Submission time Handle Problem Language Result Execution time Memory
171127 2019-12-27T13:23:51 Z dennisstar Game (IOI13_game) C++11
0 / 100
 3 ms 632 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, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 2 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 632 KB Output isn't correct
3 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 Incorrect 3 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -