oj.uz

Submission #1030035

# Submission time Handle Problem Language Result Execution time Memory
1030035 2024-07-21T16:51:05 Z tolbi Game (IOI13_game) C++17
0 / 100
 3 ms 856 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Treap{
	struct Node{
		Node *lnode, *rnode;
		ll val, gg, h;
		int pos;
		Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
	} *root;
	Treap():root(nullptr){}
	void upd(Node* nd){
		nd->gg=nd->val;
		if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg);
		if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg);
	}
	Node* merge(Node* a, Node* b){
		if (!a || !b) return (a?a:b);
		if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a;
		return b->lnode = merge(a,b->lnode),upd(b),b;
	}
	pair<Node*, Node*> split(Node* node, int x){
		if (!node) return {nullptr,nullptr};
		if (node->pos>=x){
			pair<Node*, Node*> spl = split(node->lnode,x);
			node->lnode=spl.second;
			upd(node);
			return {spl.first,node};
		}
		pair<Node*, Node*> spl = split(node->rnode,x);
		node->rnode=spl.first;
		upd(node);
		return {node,spl.second};
	}
	void update(int x, ll val){
		if (root==nullptr){
			return root = new Node(x,val), void(23);
		}
		Node* nd = root;
		while (nd){
			if (nd->pos==x) break;
			if (nd->pos>x) nd=nd->lnode;
			else nd=nd->rnode;
		}
		if (nd==nullptr){
			Node* nnode = new Node(x,val);
			pair<Node*, Node*> spl = split(root,x);
			root=merge(spl.first,nnode);
			root=merge(root,spl.second);
		}
		else {
			vector<Node*> backtrack;
			nd->val=val;
			upd(nd);
			nd = root;
			while (nd->pos!=x){
				backtrack.push_back(nd);
				if (nd->pos>x) nd=nd->lnode;
				else nd=nd->rnode;
			}
			while (backtrack.size()){
				upd(backtrack.back());
				backtrack.pop_back();
			}
		}
	}
	ll query(int l, int r){
		pair<Node*, Node*> spl = split(root, l);
		pair<Node*, Node*> spl2 = split(spl.second, r+1);
		ll ret = 0;
		if (spl2.first) ret = spl2.first->gg;
		root = merge(spl2.first,spl2.second);
		root = merge(spl.first,root);
		return ret;
	}
};
constexpr int MAXN = 1000000000;
struct SegTree{
	struct Node{
		Node *lnode, *rnode;
		Treap tr;
		Node():lnode(nullptr),rnode(nullptr){}
	} *root;
	SegTree():root(new Node){}
	void update(int x, int y, ll val){
		int l = 0, r = MAXN;
		Node *node = root;
		while (l<r){
			int mid = l+(r-l)/2;
			node->tr.update(y,val);
			if (mid>=x){
				r=mid;
				if (node->lnode==nullptr) node->lnode = new Node;
				node=node->lnode;
			}
			else {
				l=mid+1;
				if (node->rnode==nullptr) node->rnode = new Node;
				node=node->rnode;
			}
		}
		node->tr.update(y,val);
	}
	ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){
		if (l==0 && r==MAXN) node=root;
		if (l>=tl && r<=tr) return node->tr.query(a,b);
		if (l>tr || r<tl) return 0;
		int mid = l+(r-l)/2;
		ll ret = 0;
		if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode));
		if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode));
		return ret;
	}
} segtree;
void init(int R, int C) {
	//23 severim
}

void update(int P, int Q, long long K) {
	segtree.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	return segtree.query(P,U,Q,V);
}

Compilation message

game.cpp: In constructor 'Treap::Node::Node(int, ll)':
game.cpp:19:7: warning: 'Treap::Node::pos' will be initialized after [-Wreorder]
   19 |   int pos;
      |       ^~~
game.cpp:17:9: warning:   'Treap::Node* Treap::Node::lnode' [-Wreorder]
   17 |   Node *lnode, *rnode;
      |         ^~~~~
game.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
      |   ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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