제출 #140300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140300		Noam527	게임 (IOI13_game)	C++17	100 / 100	6036 ms	73516 KiB

game

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

#include "game.h"
// moving code from wcipeg is pain

ll gcd(ll x, ll y) {
	return !y ? x : gcd(y, x % y);
}
int rnd() {
	return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}

struct node {
	node *l, *r;
	int pos, key, mn, mx;
	ll val, g;
	node(int position, ll value) {
		l = r = nullptr;
		mn = mx = pos = position;
		key = rnd();
		val = g = value;
	}
	void upd() {
		g = val;
		if (l) g = gcd(g, l->g);
		if (r) g = gcd(g, r->g);
		mn = (l ? l->mn : pos);
		mx = (r ? r->mx : pos);
	}
};
struct treap {
	node *root;
	treap() {
		root = nullptr;
		srand(rnd());
	}
	void split(node *t, int pos, node *&l, node *&r) {
		if (t == nullptr) {
			l = r = nullptr;
			return;
		}
		if (t->pos < pos) {
			split(t->r, pos, l, r);
			t->r = l;
			l = t;
		}
		else {
			split(t->l, pos, l, r);
			t->l = r;
			r = t;
		}
		t->upd();
	}
	node* merge(node *l, node *r) {
		if (!l || !r) return l ? l : r;
		if (l->key < r->key) {
			l->r = merge(l->r, r);
			l->upd();
			return l;
		}
		r->l = merge(l, r->l);
		r->upd();
		return r;
	}
	bool find(int pos) {
		node *t = root;
		while (t) {
			if (t->pos == pos) return true;
			if (t->pos > pos) t = t->l;
			else t = t->r;
		}
		return false;
	}
	void upd(node *t, int pos, ll val) {
		if (t->pos == pos) {
			t->val = val;
			t->upd();
			return;
		}
		if (t->pos > pos)
			upd(t->l, pos, val);
		else
			upd(t->r, pos, val);
		t->upd();
	}
	void insert(int pos, ll val) {
		if (find(pos)) upd(root, pos, val);
		else {
			node *l, *r;
			split(root, pos, l, r);
			root = merge(merge(l, new node(pos, val)), r);
		}
	}
	ll query(node *t, int st, int en) {
		if (t->mx < st || en < t->mn) return 0;
		if (st <= t->mn && t->mx <= en) return t->g;
		ll rtn = (st <= t->pos && t->pos <= en ? t->val : 0);
		if (t->l) rtn = gcd(rtn, query(t->l, st, en));
		if (t->r) rtn = gcd(rtn, query(t->r, st, en));
		return rtn;
	}
	ll query(int st, int en) {
		if (!root) return 0;
		return query(root, st, en);
	}
	void print(node *t) {
		if (!t) return;
		print(t->l);
		cout << t->val << " ";
		print(t->r);
	}
};
struct segtree {
	segtree *l, *r;
	treap T;
	int lo, hi;
	segtree() {
		l = r = nullptr;
	}
	segtree(int st, int en) {
		l = r = nullptr;
		lo = st, hi = en;
	}
	void createl() {
		if (!l) l = new segtree(lo, (lo + hi) / 2);
	}
	void creater() {
		if (!r) r = new segtree((lo + hi) / 2 + 1, hi);
	}
	void fix(int pos) {
		ll val = 0;
		if (l) val = gcd(val, l->T.query(pos, pos));
		if (r) val = gcd(val, r->T.query(pos, pos));
		T.insert(pos, val);
	}
	void upd(int x, int y, ll val) {
		if (hi < x || x < lo) return;
		if (lo == hi) {
			T.insert(y, val);
			return;
		}
		if (lo != hi) {
			if (x <= (lo + hi) / 2) {
				createl();
				l->upd(x, y, val);
			}
			else {
				creater();
				r->upd(x, y, val);
			}
		}
		fix(y);
	}
	ll query(int t, int b, int st, int en) {
		if (hi < t || b < lo) return 0;
		if (t <= lo && hi <= b) return T.query(st, en);
		ll rtn = 0;
		if (l)
			rtn = gcd(rtn, l->query(t, b, st, en));
		if (r)
			rtn = gcd(rtn, r->query(t, b, st, en));
		return rtn;
	}
};

int r, c, q;
segtree T;

void init(int R, int C) {
	srand(12341234);
	r = R;
	c = C;
	T = segtree(0, r - 1);
}
void update(int P, int Q, ll K) {
	T.upd(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
	return T.query(P, U, Q, V);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20