| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230011 |
2020-05-07T17:51:10 Z |
AQT |
Game (IOI13_game) |
C++14 |
|
5 ms |
384 KB |
#include <game.h>
#include <bits/stdc++.h>
using namespace std;
mt19937 rando (chrono::steady_clock::now().time_since_epoch().count());
struct snode {
int p;
long long x, g;
int pri;
snode * c[2];
snode (int pp, long long v){
p = pp;
x = g = v;
pri = uniform_int_distribution<int>(INT_MIN, INT_MAX) (rando);
c[0] = c[1] = NULL;
}
};
struct bnode {
snode * rt;
bnode * lft, * rht;
bnode(){
lft = rht = NULL;
rt = NULL;
}
};
bnode * rt;
int N;
long long getg(snode * n){
return n ? n->g : 0;
}
snode * pu(snode * n){
n->g = __gcd(__gcd(getg(n->c[0]), getg(n->c[1])), n->x);
return n;
}
pair<snode *, snode *> split(snode * n, int k){
if(!n){
return {n, n};
}
if(n->p >= k){
auto p = split(n->c[0], k);
n->c[0] = p.second;
return {p.first, pu(n)};
}
else{
auto p = split(n->c[1], k);
n->c[1] = p.first;
return {pu(n), p.second};
}
}
snode * merge(snode * lft, snode * rht){
if(!lft){
return rht;
}
if(!rht){
return lft;
}
if(lft->pri > rht->pri){
lft->c[1] = merge(lft->c[1], rht);
return pu(lft);
}
else{
rht->c[0] = merge(lft, rht->c[0]);
return pu(rht);
}
}
bnode * upd(int l, int r, int x, int y, long long v, bnode * n){
//cout << l << " " << r << "\n";
if(n == NULL){
n = new bnode();
}
auto p = split(n->rt, y);
auto q = split(p.second, y+1);
n->rt = merge(p.first, merge(new snode(y, v), q.second));
if(l == r){
return n;
}
int mid = l+r>>1;
if(x <= mid){
n->lft = upd(l, mid, x, y, v, n->lft);
}
else{
n->rht = upd(mid+1, r, x, y, v, n->rht);
}
return n;
}
long long query(int sl, int sr, int ql, int qr, int qsl, int qsr, bnode * n){
if(n == NULL || sr < ql || sl > qr){
return 0;
}
//cout << " " << sl << " " << sr << "\n";
if(ql <= sl && qr >= sr){
//cout << " " << n->rt->g << "\n";
auto p = split(n->rt, qsl);
auto q = split(p.second, qsr+1);
long long ret = getg(q.first);
n->rt = merge(p.first, merge(q.first, q.second));
return ret;
}
int mid = sl+sr>>1;
return __gcd(query(sl, mid, ql, qr, qsl, qsr, n->lft), query(mid+1, sr, ql, qr, qsl, qsr, n->rht));
}
void init(int R, int C){
N = R-1;
}
void update(int r, int c, long long v){
rt = upd(0, N, r, c, v, rt);
}
long long calculate(int r, int c, int sr, int sc){
return query(0, N, r, sr, c, sc, rt);
}
/*
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init(2, 3);
update(0, 0, 20);
update(0, 2, 15);
update(1, 1, 12);
cout << calculate(0, 0, 0, 2) << "\n";
cout << calculate(0, 0, 1, 1) << "\n";
update(0, 1, 6);
update(1, 1, 14);
cout << calculate(0, 0, 0, 2) << "\n";
cout << calculate(0, 0, 1, 1) << "\n";
}
*/
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;
^~~
game.cpp: In function 'bnode* upd(int, int, int, int, long long int, bnode*)':
game.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r>>1;
~^~
game.cpp: In function 'long long int query(int, int, int, int, int, int, bnode*)':
game.cpp:109:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = sl+sr>>1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
