| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52145 |
2018-06-24T09:16:57 Z |
gnoor |
Game (IOI13_game) |
C++17 |
|
4 ms |
704 KB |
#include "game.h"
#ifdef debug
#include "grader.cpp"
#endif
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;
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;
}
pair<int,int> inv(const pair<int,int> &x) {
return {x.second,x.first};
}
struct node {
pair<int,int> key; //col,row
int prior;
long long val;
long long gcd;
pair<int,int> mn;
pair<int,int> mx;
node *l, *r;
node(pair<int,int> _key,long long _val): key(_key),prior((rand()<<16)^rand()),val(_val),gcd(_val),mn(_key),mx(_key),l(0),r(0) {}
static void print(node *x) {
if (!x) return;
print(x->l);
printf("%d,%d:%d,%d:%lld,%lld ",x->key.second,x->key.first,x->mn.first,x->mx.first,x->val,x->gcd);
print(x->r);
}
static void update(node *x) {
if (!x) return;
x->gcd=x->val;
x->mn=x->mx=x->key;
if (x->l) {
x->gcd=gcd2(x->gcd,x->l->gcd);
x->mn=min(x->mn,x->l->mn);
}
if (x->r) {
x->gcd=gcd2(x->gcd,x->r->gcd);
x->mx=max(x->mx,x->r->mx);
}
}
static bool change(node *x,const pair<int,int> &key,long long newval) {
if (!x) return false;
if (x->key==key) {
x->val=newval;
update(x);
return true;
}
bool res=change((x->key<key)?x->r:x->l,key,newval);
update(x);
return res;
}
static void split(node *x,node* &l, node* &r,pair<int,int> key) {
if (!x) l=r=NULL;
else if (x->key<key) {
l=x;
split(x->r,x->r,r,key);
} else {
r=x;
split(x->l,l,x->l,key);
}
update(x);
}
static void merge(node* &x,node *l,node *r) {
if(!l||!r) x=(l)?l:r;
else if (l->prior>r->prior) {
x=l;
merge(x->r,x->r,r);
} else {
x=r;
merge(x->l,l,x->l);
}
update(x);
}
static void insert(node* &x, node *n) {
if (!x) x=n;
else if (n->prior>x->prior) {
split(x,n->l,n->r,n->key);
x=n;
} else {
insert((x->key<n->key)?x->r:x->l,n);
}
update(x);
}
static void erase(node* &x, pair<int,int> key) {
if (!x) return;
if (x->key==key) {
merge(x,x->l,x->r);
} else {
erase(x->key<key?x->r:x->l,key);
}
update(x);
}
static void insertFrom(node* &dest,node* src) {
if (!src) return;
insert(dest,new node(src->key,src->val));
insertFrom(dest,src->l);
insertFrom(dest,src->r);
}
static void eraseFrom(node* &dest,node* src) {
if (!src) return;
erase(dest,src->key);
eraseFrom(dest,src->l);
eraseFrom(dest,src->r);
}
static long long query(node *x,int lo,int hi) {
if (!x) return 0;
if (lo<=x->mn.first&&x->mx.first<=hi) return x->gcd;
long long cur=0;
if (x->key.first>=lo&&x->key.first<=hi) cur=x->val;
return gcd2(cur,gcd2(query(x->l,lo,hi),query(x->r,lo,hi)));
}
};
struct listnode {
int key;
node *val;
listnode *prv,*nxt;
listnode(int _key): key(_key),val(0),prv(0),nxt(0) {}
static void insert(listnode *x,listnode *n) {
if (x->prv) {
x->prv->nxt=n;
}
n->prv=x->prv;
n->nxt=x;
x->prv=n;
}
};
listnode* last=new listnode(1e9+7);
struct cluster {
node *big;
listnode *fst,*lst;
int size;
cluster(listnode *init): big(0),fst(init),lst(init),size(1) {}
listnode* find(int val) {
//printf("%d %d %d\n",fst->key,lst->key,val);
if (val<fst->key) return fst;
if (val>lst->key) return NULL;
for (listnode *it=fst;it!=lst;it=it->nxt) {
if (it->key>=val) return it;
}
return lst;
}
long long query(int P,int Q,int U,int V) {
long long gcd=0;
for (listnode *it=fst;it!=lst;it=it->nxt) {
if (it->key>=P&&it->key<=U) {
//printf("node query %d: %d %d\n",it->key,Q,V);
node::print(it->val);
//printf("\n");
gcd=gcd2(gcd,node::query(it->val,Q,V));
//printf("--> %lld\n",node::query(it->val,Q,V));
}
}
return gcd;
}
};
listnode* head;
int cnt;
int blk;
vector<cluster> cls;
void init(int R, int C) {
head=last;
cnt=1;
blk=1;
cls.push_back(cluster(head));
}
void update(int P, int Q, long long K) {
//printf("update %d %d %lld\n",P,Q,K);
//find which cluster
int id=-1;
for (int i=0;i<(int)cls.size();i++) {
if (cls[i].lst->key<P) continue;
id=i;
break;
}
//printf("id %d %d %d\n",id,cls[id].fst->key,cls[id].lst->key);
//check if R already exists
listnode* curR=cls[id].find(P);
//printf("curR %d\n",curR->key);
//printf("%x\n",curR);
if (curR!=NULL&&curR->key==P) {
//exists
//printf("exists\n");
bool res = node::change(curR->val,{Q,P},K);
node::change(cls[id].big,{Q,P},K);
if (!res) {
//C does not exist
//printf("C not exist\n");
node::insert(curR->val,new node({Q,P},K));
node::insert(cls[id].big,new node({Q,P},K));
}
} else {
//does not exist
//printf("not exist\n");
listnode* newR=new listnode(P);
listnode::insert(curR,newR);
if (curR==cls[id].fst) cls[id].fst=newR;
cls[id].size++;
curR=newR;
cnt++;
//printf("curR %d\n",curR->key);
//insert C in curR
node::insert(curR->val,new node({Q,P},K));
node::insert(cls[id].big,new node({Q,P},K));
head=cls[0].fst;
//if cnt is square, increase blk
//adjust block
int blkCnt=(int)cls.size();
for (int i=id;i<blkCnt;i++) {
if (cls[i].size>blk) {
//move lst to next cluster
node::eraseFrom(cls[i].big,cls[i].lst->val);
if (i==blkCnt-1) {
cls.push_back(cluster(cls[i].lst));
} else {
node::insertFrom(cls[i+1].big,cls[i].lst->val);
cls[i+1].fst=cls[i+1].fst->prv;
cls[i+1].size++;
}
cls[i].lst=cls[i].lst->prv;
cls[i].size--;
}
break;
}
}
//for (int i=0;i<(int)cls.size();i++) {
//printf("%d: %d,%d ",i,cls[i].fst->key,cls[i].lst->key);
//for (listnode* it=cls[i].fst;it!=cls[i].lst;it=it->nxt) {
//printf("%d ",it->key);
//}
//printf("%d\n",cls[i].lst->key);
//}
//for (listnode* it=head;it!=last;it=it->nxt) {
//printf("%d ",it->key);
//}
//printf("\n");
}
long long calculate(int P, int Q, int U, int V) {
//printf("ask %d %d %d %d\n",P,Q,U,V);
long long gcd=0;
for (int i=0;i<(int)cls.size();i++) {
if (P>cls[i].lst->key||U<cls[i].fst->key) continue;
//printf("%d %d\n",cls[i].fst->key,cls[i].lst->key);
if (P<=cls[i].fst->key&&cls[i].lst->key<=U) {
//printf("yay\n");
gcd=gcd2(gcd,node::query(cls[i].big,Q,V));
} else {
//printf("eiei\n");
gcd=gcd2(gcd,cls[i].query(P,Q,U,V));
}
}
return gcd;
}
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 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
496 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
564 KB |
Output is correct |
| 2 |
Correct |
2 ms |
624 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
624 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
624 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
660 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
676 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
