oj.uz

Submission #119639

# Submission time Handle Problem Language Result Execution time Memory
119639 2019-06-21T14:14:21 Z rajarshi_basu Game (IOI13_game) C++14
37 / 100
 13000 ms 9360 KB 
#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<<16);
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

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 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1484 ms 9136 KB Output is correct
5 Correct 451 ms 9120 KB Output is correct
6 Correct 5109 ms 6648 KB Output is correct
7 Correct 6267 ms 6384 KB Output is correct
8 Correct 3686 ms 6688 KB Output is correct
9 Correct 5290 ms 6552 KB Output is correct
10 Correct 5093 ms 6168 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Execution timed out 13025 ms 7176 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1514 ms 9360 KB Output is correct
13 Correct 429 ms 9080 KB Output is correct
14 Correct 4635 ms 6636 KB Output is correct
15 Correct 5584 ms 6368 KB Output is correct
16 Correct 3751 ms 6396 KB Output is correct
17 Correct 5633 ms 6364 KB Output is correct
18 Correct 5211 ms 6160 KB Output is correct
19 Execution timed out 13077 ms 7204 KB Time limit exceeded
20 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 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1680 ms 9300 KB Output is correct
13 Correct 405 ms 9080 KB Output is correct
14 Correct 4919 ms 6716 KB Output is correct
15 Correct 6104 ms 6304 KB Output is correct
16 Correct 3714 ms 6504 KB Output is correct
17 Correct 5093 ms 6604 KB Output is correct
18 Correct 5631 ms 6048 KB Output is correct
19 Execution timed out 13081 ms 7476 KB Time limit exceeded
20 Halted 0 ms 0 KB -