| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 399289 |
2021-05-05T14:10:55 Z |
cfalas |
Game (IOI13_game) |
C++14 |
|
29 ms |
6348 KB |
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
int t, n;
vi a, b;
static int M;
vector<ii> changed;
static map<ii, int> mapper[100000];
template<typename Q>
struct seg_tree_2d{
template<typename T>
struct seg_tree{
struct node{
T val;
int left=-1;
int right=-1;
node() {val=0, left=-1, right=-1;}
node(T v) {val=v, right=-1, left=-1;}
};
int parent;
vector<node> seg;
T RAND_VALUE=0;
seg_tree(){seg.assign(1, node());}
inline node merge(node& par, node& a, node& b){
node ret;
ret.left = par.left, ret.right = par.right;
ret.val = __gcd(a.val , b.val);
return ret;
}
inline void update_node(int ind, T val, int l, int r){
seg[ind].val = val;
changed.push_back({l,r});
}
inline void create_children(int ind, int l, int r){
if(seg[ind].left==-1) seg[ind].left=seg.size(), mapper[parent][{l,MID}] = seg[ind].left, seg.push_back(node());
if(seg[ind].right==-1) seg[ind].right=seg.size(), mapper[parent][{MID+1,r}] = seg[ind].right, seg.push_back(node());
}
void print(int l=0, int r=M-1, int ind=0){
cout<<"("<<l<<" "<<r<<" "<<ind<<": "<<seg[ind].val<<") ";
if(seg[ind].left!=-1) print(l, MID, seg[ind].left);
if(seg[ind].right!=-1) print(MID+1, r, seg[ind].right);
}
void build(vector<T>& arr, int l=0, int r=M-1, int ind=0){
//cout<<"Bob the builder "<<l<<" "<<r<<" "<<ind<<endl;
//if(l==r) cout<<"node "<<arr[l]<<endl;
if(l==r) seg[ind] = node(arr[l]), changed.push_back({l,r});
else{
create_children(ind, l, r);
changed.push_back({l,r});
build(arr,l,MID,seg[ind].left);
build(arr,MID+1,r,seg[ind].right);
seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
}
}
void update(int rl, int rr, T val, int l=0, int r=M-1, int ind=0){
if(rl<=l && r<=rr) update_node(ind, val,l,r);
else if(rr<l || r<rl) return;
else{
create_children(ind, l, r);
changed.push_back({l,r});
update(rl,rr,val,l,MID,seg[ind].left);
update(rl,rr,val,MID+1,r,seg[ind].right);
seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
}
}
T query(int rl, int rr, int l=0, int r=M-1, int ind=0){
if(rl<=l && r<=rr) return seg[ind].val;
else if(rl>r || l>rr) return RAND_VALUE;
else{
create_children(ind, l, r);
return __gcd(query(rl, rr, l, MID, seg[ind].left) , query(rl,rr,MID+1,r,seg[ind].right));
}
}
};
struct node{
seg_tree<Q> val;
int left=-1;
int right=-1;
node() {left=-1, right=-1;}
};
vector<node> seg2d;
static inline int N;
Q RAND_VALUE_2d=0;
seg_tree_2d(int n){N=n, seg2d.assign(1, node()); seg2d[0].val.parent = 0;}
inline void merge(node &par, node &a, node &b, int ind){
//a.val.print();
//cout<<endl;
//cout<<ind<<": \n";
if(par.val.seg.size()==1){
par.val = a.val;
par.val.parent = ind;
vi ar(N);
mapper[ind] = mapper[a.val.parent];
//FOA(v,mapper) if(v.F.F==a.val.parent) mapper[{ind, v.F.S}] = v.S;
FOR(i,par.val.seg.size()) par.val.seg[i].val = __gcd(par.val.seg[i].val, b.val.seg[i].val);
}
else{
//assert(a.val.parent==seg2d[ind].left);
FOA(v,changed){
//cout<<v.F<<" "<<v.S<<endl;
par.val.seg[mapper[ind][v]].val = __gcd(a.val.seg[mapper[seg2d[ind].left][v]].val , b.val.seg[mapper[seg2d[ind].right][v]].val);
}
}
}
void print(int l=0, int r=N-1, int ind=0){
cout<<"L R "<<l<<" "<<r<<" "<<ind<<endl;
seg2d[ind].val.print();
cout<<endl;
if(seg2d[ind].left!=-1) print(l, MID, seg2d[ind].left);
if(seg2d[ind].right!=-1) print(MID+1, r, seg2d[ind].right);
}
inline void create_children(int ind){
if(seg2d[ind].left==-1){
seg2d[ind].left=seg2d.size();
seg2d.push_back(node());
seg2d.back().val.parent = seg2d[ind].left;
mapper[seg2d[ind].left][{0,M-1}] = 0;
}
if(seg2d[ind].right==-1){
seg2d[ind].right=seg2d.size();
seg2d.push_back(node());
seg2d.back().val.parent = seg2d[ind].right;
mapper[seg2d[ind].right][{0,M-1}] = 0;
}
//if(seg2d[ind].right==-1) seg2d[ind].right=seg2d.size(), seg2d.push_back(node()), seg2d.back().val.parent = seg2d[ind].right;
}
void build(vector<vector<Q> >& arr, int l=0, int r=N-1, int ind=0){
if(l==r){
seg2d[ind].val.build(arr[l]);
}
else{
create_children(ind);
build(arr,l,MID,seg2d[ind].left);
build(arr,MID+1,r,seg2d[ind].right);
merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
}
}
void update(int y, int x, Q val, int l=0, int r=N-1, int ind=0){
if(y==l && y==r) seg2d[ind].val.update(x, x, val);
else if(y<l || r<y) return;
else{
create_children(ind);
update(y,x,val,l,MID,seg2d[ind].left);
update(y,x,val,MID+1,r,seg2d[ind].right);
merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
}
}
Q query(int rl, int rr, int xl, int xr, int l=0, int r=N-1, int ind=0){
if(rl<=l && r<=rr){
//cout<<"Querying "<<ind<<" "<<l<<" "<<r<<endl;
//seg[ind].val.print();
//cout<<endl;
Q val = seg2d[ind].val.query(xl, xr);
//cout<<"ans="<<val<<endl;
return val;
}
else if(rl>r || l>rr) return RAND_VALUE_2d;
else{
create_children(ind);
return __gcd(query(rl, rr, xl, xr, l, MID, seg2d[ind].left), query(rl,rr,xl, xr, MID+1,r,seg2d[ind].right));
}
}
};
seg_tree_2d<ll> seg(n);
/*
string s[n];
vector<vector<int> > a(n, vi(n, 0));
FOR(i,n) cin>>s[i];
FOR(i,n) FOR(j,n){
if(s[i][j]=='*') a[i][j] = 1;
else a[i][j] = 0;
}
cerr<<"Read"<<endl;
seg.build(a);
cerr<<"Built\r";
cerr<<endl;
/*
cout<<"--------------------------------\n";
seg.print();
cout<<"--------------------------------\n";
seg.seg[3].val.print();
cout<<endl;
FOR(i,n){
FOR(j,n) a[i][j] = seg.query(i,i,j,j);
}
FORi(i,3,7){
FOR(j,seg.seg[i].val.seg.size()) cout<<seg.seg[i].val.seg[j].val<<" ";
cout<<endl;
}
FOR(i,n){
FOR(j,n) cout<<a[i][j]<<" ";
cout<<endl;
}
FOA(v,mapper) cout<<v.F.F<<" {"<<v.F.S.F<<" "<<v.F.S.S<<"} -> "<<v.S<<endl;
while(q--){
cin>>t;
if(t==1){
int x, y;
cin>>x>>y;
changed.clear();
seg.update(x-1,y-1, 1);
}
else{
int x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
cout<<seg.query(x1-1,x2-1, y1-1, y2-1)<<"\n";
}
}
}
*/
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;
}
void init(int R, int C) {
M = C;
seg.N = R;
}
void update(int P, int Q, long long K) {
seg.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return seg.query(P,U,Q,V);
}
Compilation message
game.cpp:220:2: warning: "/*" within comment [-Wcomment]
220 | /*
|
game.cpp:115:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
115 | static inline int N;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
6324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4980 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
6260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
6232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
6348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
