| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 478508 |
2021-10-07T19:53:27 Z |
KULIKOLD |
Game (IOI13_game) |
C++17 |
|
20 ms |
500 KB |
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> super_set;
int c, rl;
struct Node{
Node* lS;
Node* rS;
ll val;
Node(){
val = 0;
lS = nullptr;
rS = nullptr;
}
};
ll gcd(ll x,ll y){
if(x == 0 or y == 0) return max(x,y);
return __gcd(x,y);
}
ll get_val(Node *v){
if(v == nullptr) return 0;
return v->val;
}
struct NodeST{
Node root;
void update(Node* v,int l,int r,int t,ll val){
if (l == r){
(v->val) = val;
return;
}
ll m = (l+r)/2;
if (t <= m){
if (v->lS == nullptr) v->lS = new Node();
update(v->lS,l,m,t,val);
}else{
if (v->rS == nullptr) v->rS = new Node();
update(v->rS,m+1,r,t,val);
}
v->val = gcd(get_val(v->lS),get_val(v->rS));
}
ll get(Node *v,int l,int r,int tl,int tr){
if(v == nullptr or r < tl or tr < l) return 0;
if(tl <= l and r <= tr) {
return v->val;
}
ll m = (l+r)/2;
return gcd(get(v->rS,m+1,r,tl,tr),get(v->lS,l,m,tl,tr));
}
void update(ll t,ll val){
return update(&root,0,c,t,val);
}
ll get(ll tl,ll tr){
return get(&root,0,c,tl,tr);
}
NodeST(){
root = *new Node();
}
};
struct Node2{
Node2 *lS;
Node2 *rS;
NodeST val;
Node2(){
lS = nullptr;
rS = nullptr;
val = *new NodeST();
}
};
void update(Node2* v,int l,int r,int x,int y,ll val){
if (l == r){
(v->val).update(y,val);
return;
}
ll m = (l+r)/2;
if (x <= m){
if (v->lS == nullptr) v->lS = new Node2();
update(v->lS,l,m,x,y,val);
}else{
if (v->rS == nullptr) v->rS = new Node2();
update(v->rS,m+1,r,x,y,val);
}
ll new_val = 0;
if(v->lS) new_val=gcd(new_val,(v->lS)->val.get(y,y));
if(v->rS) new_val=gcd(new_val,(v->rS)->val.get(y,y));
v->val.update(y,new_val);
}
ll get(Node2 *v,int l,int r,int xl,int xr,int yl,int yr){
if(v == nullptr or r < xl or xr < l) return 0;
if(xl <= l and r <= xr) {
return (v->val).get(yl,yr);
}
ll m = (l+r)/2;
return gcd(get(v->lS,l,m,xl,xr,yl,yr),get(v->rS,m+1,r,xl,xr,yl,yr));
}
Node2 root;
const int SQRT = 0;
map<pair<int,int>,ll> buf,all;
super_set X,Y;
void updates(int x,int y,ll val){
if (all.count({x,y})){
update(&root,0,rl,X.order_of_key(x),Y.order_of_key(y),val);
all[{x,y}] = val;
return;
}
buf[{x,y}] = val;
if (buf.size()>SQRT){
for(auto [cord,val]:all){
update(&root,0,rl,X.order_of_key(cord.first),Y.order_of_key(cord.second),0);
}
for(auto [cord,val]:buf){
X.insert(cord.first);
Y.insert(cord.second);
all[cord] = val;
}
buf.clear();
rl = X.size();
c = Y.size();
for(auto [cord,val]:all){
update(&root,0,rl,X.order_of_key(cord.first),Y.order_of_key(cord.second),val);
}
}
}
ll get(int xl,int xr,int yl,int yr){
ll ret = 0;
for(auto [cord,val]:buf){
if (xl<=cord.first && cord.first<=xr && yl<=cord.second && cord.second<=yr)
ret = __gcd(ret,val);
}
return __gcd(ret,get(&root,0,rl,X.order_of_key(xl),X.order_of_key(xr),Y.order_of_key(yl),Y.order_of_key(yr)));
}
/*
int main() {
int R,C,n;
cin >> R >> C >> n;
rl = -1;
c = -1;
for (int i = 0; i < n; ++i) {
int type = 0;
cin >> type;
if(type == 1){
int x,y,t;
cin >> x >> y >> t;
updates(x,y,t);
}
else{
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << get(x1,x2,y1,y2) << "\n";
}
}
return 0;
}
*/
void init(int R,int C){
rl = 0;
c = 0;
root = *new Node2();
}
void update(int P,int Q,ll K){
updates(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
return get(P,U,Q,V);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
