oj.uz

Submission #119640

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

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 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 0 ms 256 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 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 0 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 0 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 384 KB Output is correct
4 Correct 1535 ms 5256 KB Output is correct
5 Correct 371 ms 5356 KB Output is correct
6 Correct 4918 ms 2328 KB Output is correct
7 Correct 5482 ms 2096 KB Output is correct
8 Correct 3598 ms 2380 KB Output is correct
9 Correct 5228 ms 2208 KB Output is correct
10 Correct 5261 ms 1684 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 256 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 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 428 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Execution timed out 13035 ms 4168 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 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 256 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 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 1467 ms 5208 KB Output is correct
13 Correct 420 ms 5264 KB Output is correct
14 Correct 4561 ms 2244 KB Output is correct
15 Correct 5708 ms 1776 KB Output is correct
16 Correct 3736 ms 2324 KB Output is correct
17 Correct 5200 ms 1748 KB Output is correct
18 Correct 5265 ms 1408 KB Output is correct
19 Execution timed out 13029 ms 4148 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 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 256 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1589 ms 4876 KB Output is correct
13 Correct 421 ms 5112 KB Output is correct
14 Correct 4909 ms 2064 KB Output is correct
15 Correct 5960 ms 1808 KB Output is correct
16 Correct 3851 ms 2316 KB Output is correct
17 Correct 5652 ms 2016 KB Output is correct
18 Correct 5172 ms 1656 KB Output is correct
19 Execution timed out 13004 ms 3940 KB Time limit exceeded
20 Halted 0 ms 0 KB -