| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1104886 |
2024-10-24T15:45:52 Z |
spycoderyt |
Game (IOI13_game) |
C++17 |
|
1 ms |
336 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// point update of val, 2d range gcd
long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
struct node{
node *l,*r;
int pos,key,ll,rr;
long long val,g;
node(int pos,long long k) {
g = val = k;
ll = rr = pos;
key = rand();
};
void update(){
g = val;
if(l) g = gcd(g,l->g);
if(r) g = gcd(g,r->g);
ll = (l?l->ll : pos);
rr = (r?r->rr : pos);
}
};
struct treap{
typedef node* pnode;
pnode root;
treap() {
root=nullptr;
}
void split(pnode t, int pos,pnode& l,pnode& r) {
if(!t) return void(l = r = nullptr);
if(t->pos < pos) {
split(t->r,pos,t->r,r);
t->update();
l = t;
} else {
split(t->l,pos,l,t->l);
t->update();
r = t;
}
}
void merge(pnode& t,pnode l,pnode r) {
if(!l || !r) return void(t = (l ? l : r));
if(l->key > r->key) {
merge(l->r,l->r,r);
t = l;
} else {
merge(r->l,l,r->l);
t = r;
}
t->update();
}
void upd(pnode& t, int pos,long long val) {
if(t->pos == pos) {
t->val = val;
t->update();
return;
}
if(pos > t->pos) upd(t->r,pos,val);
else upd(t->l,pos,val);
t->update();
}
bool find(int pos) {
pnode t = root;
while(t) {
if(t->pos == pos) return 1;
else if(pos > t->pos) t = t->r;
else t = t->l;
}
return 0;
}
void insert(int pos,long long val) {
if(find(pos)) upd(root,pos,val);
else {
pnode l,r,tmp;
split(root,pos,l,r);
merge(tmp,l,new node(pos,val));
merge(root,tmp,r);
}
}
long long query(pnode t,int ll,int rr) {
if(t->rr < ll || t->ll > rr) return 0;
if(t->ll >= ll && t->rr <= rr) return t->g;
long long ans = (t->pos >= ll && t->pos <= rr ? t->val : 0);
if(t->l) ans = gcd(ans,query(t->l,ll,rr));
if(t->r) ans = gcd(ans,query(t->r,ll,rr));
return ans;
}
long long qry(int ll,int rr) {
if(!root)return 0;
else return query(root,ll,rr);
}
};
struct seg{
seg *l,*r;
treap t;
int ll,rr;
seg() {
l = r = nullptr;
}
seg(int a,int b) {
ll = a, rr = b;
l = r = nullptr;
}
void new_left(){
if(!l) l = new seg(ll,(ll+rr)/2);
}
void new_right(){
if(!r) r = new seg((ll+rr)/2+1,rr);
}
void upd(int pos) {
long long ans = 0;
if(l) ans = gcd(ans,l->t.qry(pos,pos));
if(r) ans = gcd(ans,r->t.qry(pos,pos));
t.insert(pos,ans);
}
void upd(int x,int y,long long val) {
if(x < ll || x > rr) return;
if(ll==rr){
t.insert(y,val);
return;
}
if(x <= (ll+rr)/2) {
new_left();
l->upd(x,y,val);
} else {
new_right();
r->upd(x,y,val);
}
upd(y);
}
long long query(int a,int b,int c,int d) {
if(a > rr || b < ll) return 0;
if(a >= ll && b <= rr) return t.qry(c,d);
long long ans = 0;
if(l) ans = gcd(ans,l->query(a,b,c,d));
if(r) ans = gcd(ans,r->query(a,b,c,d));
return ans;
}
};
seg tree;
void init(int R, int C) {
tree = seg(0,R-1);
}
void update(int P, int Q, long long K) {
tree.upd(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return tree.query(P,U,Q,V);
}
/*
/usr/bin/g++ -Wall -lm -static -DEVAL -o game -O2 -DEVAL grader.c game.cpp -std=c++11
./test
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
