Submission #119640

#	Time	Username	Problem	Language	Result	Execution time	Memory
119640		rajarshi_basu	Game (IOI13_game)	C++14	37 / 100	13035 ms	5356 KiB

game

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>

#include "game.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector

using namespace std;

const int INF = 1e9+10;
const int MAXN = 100*100*10+10;

mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(1,1<<29);
int RAND(){
	return uid(rng);
}


ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int ctr = 0;
struct Treap{
	struct Node{
		Node* left,*right;
		int prior;
		int value;
		ll gcdval;
		ll gcdele;
		Node(int p,int v,ll g,Node* lft = NULL,Node* rght = NULL){
			ctr++;
			// check if too many nodes are getting created.
			/*
			int x = 3;
			if(ctr >= 400)while(1){
				x = x*x;
				if(x == 0){
					

					break;
				}
			}
			*/
			prior = p;
			value = v;
			gcdele = g;
			left = lft;
			right = rght;
			gcdval = g;
		}
	};

	Node* head;
	void traverse(Node* node){
		if(node == NULL)return;
		traverse(node->left);
		cout << node->value << " ";
		traverse(node->right);
	}

	inline void updateNode(Node* node){
		if(node == NULL)return;
		node->gcdval = node->gcdele;
		if(node->left == NULL and node->right == NULL)return;
		if(node->right != NULL)node->gcdval = gcd2(node->gcdval,node->right->gcdval);
		if(node->left != NULL)node->gcdval = gcd2(node->gcdval,node->left->gcdval);
	}

	void split(Node* head,Node*& leftHalf,Node*& rightHalf,int key){
		if(head == NULL){
			leftHalf = NULL;
			rightHalf = NULL;
			return;
		}
		if(key < head->value){
			rightHalf = head;
			split(head->left,leftHalf,rightHalf->left,key);
		}else{
			leftHalf = head;
			split(head->right,leftHalf->right,rightHalf,key);
		}
		updateNode(leftHalf);
		updateNode(rightHalf);
	}

	void merge(Node*& node,Node* leftHalf,Node* rightHalf){
		if(leftHalf == NULL)node = rightHalf;
		else if(rightHalf == NULL)node = leftHalf;
		else if(leftHalf == NULL and rightHalf == NULL)node = NULL;
		else{
			if(leftHalf->prior > rightHalf->prior){
				node = leftHalf;
				merge(node->right,leftHalf->right,rightHalf);
			}else{
				node = rightHalf;
				merge(node->left,leftHalf,rightHalf->left);
			}
		}
		updateNode(node);
	}
	ll search(int l,int r){
		if(head == NULL)return 0;
		Node* lft;
		Node* mid;
		Node* rgt;
		//traverse(head);
		split(head,mid,rgt,r);
		split(mid,lft,mid,l-1);
		ll ans = 0;
		if(mid != NULL)ans = mid->gcdval;
		merge(head,mid,rgt);
		merge(head,lft,head);
		return ans;
	}

	void insert(int pos,ll val){
		if(head == NULL){
			head = new Node(RAND(),pos,val);
		}else{
			Node* lft = NULL;
			Node* mid = NULL;
			Node* rgt = NULL;
			//traverse(head);
			split(head,mid,rgt,pos);
			//cout << "1split" << endl;
			split(mid,lft,mid,pos-1);
			//cout << lft << " " << mid << " " << rgt << endl;
			
			if(mid == NULL){
				if(val > 0)mid = new Node(RAND(),pos,val);
			}else{
				mid->gcdval = mid->gcdele = val;
			}
			if(val > 0){
				merge(head,mid,rgt);
				merge(head,lft,head);
			}else{
				merge(head,lft,rgt);
			}
			//traverse(head);
			//cout << endl;
		}
	}
};

Treap rows[2001];
int r,c;

void init(int R, int C) {
    r = R;
    c = C;
}

void update(int P, int Q, ll K) {
//	cout << "update started" << endl;
//	cout << P << " " << Q << " " << K << endl;
	//if(ctr > 400)while(1);
    rows[P].insert(Q,K);
   // cout << "update done" << endl;
    //rows[0].traverse(rows[0].head);cout << endl;
    //rows[1].traverse(rows[1].head);cout << endl;

}

ll calculate(int P, int Q, int U, int V) {
    ll ans = 0;
    FORE(i,P,U){
    	//rows[i].traverse(rows[i].head);
    	//cout << endl;
    	ans = gcd2(ans,rows[i].search(Q,V));
    }
    return ans;
}

int main1(){
	int r,c,n;
	cin >> r >> c >> n;
	init(r,c);
	FOR(i,n){
		int id;
		cin >> id;
		if(id == 1){
			int a,b;ll c;
			cin >> a>> b >> c;
			update(a,b,c);
		}else{
			int a,b,c,d;
			cin >> a >> b >> c >> d;
			cout << calculate(a,b,c,d) << endl;
		}
	}
	return 0;
}


int ma1in(){
	init(2,3);
	update(0,0,20);
	update(0,2,15);
	update(1,1,12);
	cout << " -------------- " << calculate(0,0,0,2) << endl;
	cout << " -------------- " << calculate(0,0,1,1) << endl;
	update(0,1,6);
	update(1,1,14);
	cout << " -------------- " << calculate(0,0,0,2) << endl;
	cout << " -------------- " << calculate(0,0,1,1) << endl;
	
	return 0;
}

Compilation message (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: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20