| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 119620 |
2019-06-21T13:09:20 Z |
rajarshi_basu |
Game (IOI13_game) |
C++14 |
|
243 ms |
256000 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<<31);
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++;
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[101];
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 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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
196 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
209 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
243 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
213 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
