| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1090756 |
2024-09-18T16:52:29 Z |
modwwe |
Game (IOI13_game) |
C++14 |
|
0 ms |
0 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while(c<'0'||c>'9')
{
c=getchar_unlocked();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf=1e9;
const int mod2=1e9+9;
const int mod1=998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c,d,e;
};
long long n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int i,s10,s12;
int kk;
int el=19;
struct Node
{
Node* c[2];
long long gcd;
Node()
{
gcd=0;
c[0]=c[1]=NULL;
}
};
struct segtree
{
void upd(int l,int r,int l1,long long x,Node* u)
{
if(l==r)
{
u->gcd=x;
return;
}
int mid=l+r>>1;
if(l1<=mid)
{
if(u->c[0]==NULL) u->c[0]=new Node();
upd(l,mid,l1,x,u->c[0]);
}
else
{
if(u->c[1]==NULL) u->c[1]=new Node();
upd(mid+1,r,l1,x,u->c[1]);
}
u->gcd=0;
if(u->c[0]!=NULL)
u->gcd=__gcd(u->gcd,u->c[0]->gcd);
if(u->c[1]!=NULL)
u->gcd=__gcd(u->gcd,u->c[1]->gcd);
}
void updd(int l,int r,int l1,Node* u,Node* v,Node* uv,bool d,bool d1)
{
u->gcd=0;
if(!d) u->gcd=__gcd(v->gcd,u->gcd);
if(!d1)u->gcd=__gcd(uv->gcd,u->gcd);
if(l==r)
{
return;
}
int mid=l+r>>1;
if(l1<=mid)
{
if(u->c[0]==NULL) u->c[0]=new Node();
if(v->c[0]==NULL) updd(l,mid,l1,u->c[0],v,uv->c[0],1,d1);
else if(uv->c[0]==NULL) updd(l,mid,l1,u->c[0],v->c[0],uv,d,1);
else updd(l,mid,l1,u->c[0],v->c[0],uv->c[0],d,d1);
}
else
{
if(u->c[1]==NULL) u->c[1]=new Node();
if(v->c[1]==NULL) updd(mid+1,r,l1,u->c[1],v,uv->c[1],1,d1);
else if(uv->c[1]==NULL) updd(mid+1,r,l1,u->c[1],v->c[1],uv,d,1);
else updd(mid+1,r,l1,u->c[1],v->c[1],uv->c[1],d,d1);
}
}
long long get(int l,int r,int l1,int r1, Node* u)
{
if(l>r1||r<l1) return 0;
if(l>=l1&&r<=r1)
{
return u->gcd;
}
int mid=l+r>>1;
long long s=0;
if(u->c[0]!=NULL) s=__gcd(s,get(l,mid,l1,r1,u->c[0]));
if(u->c[1]!=NULL)s=__gcd(s,get(mid+1,r,l1,r1,u->c[1]));
return s;
}
};
struct treap
{
treap* c[2];
segtree st;
Node* rot;
treap()
{
rot=new Node();
c[0]=c[1]=NULL;
}
};
treap *root=new treap();
void upd3(int l,treap* x,treap*y,treap*xy)
{
x->st.updd(1,k,l,x->rot,y->rot,xy->rot,0,0);
}
void upd(int l,int r,int l1,long long x,int r1,treap* u)
{
if(l==r)
{
u->st.upd(1,k,r1,x,u->rot);
}
if(l==r) return;
int mid=l+r>>1;
if(l1<=mid)
{
if(u->c[0]==NULL)u->c[0]=new treap();
upd(l,mid,l1,x,r1,u->c[0]);
}
else
{
if(u->c[1]==NULL) u->c[1]=new treap();
upd(mid+1,r,l1,x,r1,u->c[1]);
}
if(u->c[1]==NULL) upd3(r1,u,u->c[0],u->c[0]);
else if(u->c[0]==NULL) upd3(r1,u,u->c[1],u->c[1]);
else upd3(r1,u,u->c[1],u->c[0]);
}
void get(int l,int r,int l1,int r1,int l2,int r2,treap* u)
{
if(l>r1||r<l1) return;
if(l>=l1&&r<=r1)
{
s4=__gcd(s4,u->st.get(1,k,l2,r2,u->rot));
return;
}
int mid=l+r>>1;
if(u->c[0]!=NULL)
get(l,mid,l1,r1,l2,r2,u->c[0]);
if(u->c[1]!=NULL)
get(mid+1,r,l1,r1,l2,r2,u->c[1]);
}
void init(int R,int C)
{
m=R;
k=C;
}
void update(int a1,int a2,long long a3)
{
a1++;
a2++;
upd(1,m,a1,a3,a2,root);
}
long long calculate(int a1,int a2,int a3,int a4)
{
a1++;
a2++;
a3++;
a4++;s4=0;
get(1,m,a1,a3,a2,a4,root);
return s4;
}
Compilation message
game.cpp: In member function 'void segtree::upd(int, int, int, long long int, Node*)':
game.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid=l+r>>1;
| ~^~
game.cpp: In member function 'void segtree::updd(int, int, int, Node*, Node*, Node*, bool, bool)':
game.cpp:114:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid=l+r>>1;
| ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:138:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
138 | int mid=l+r>>1;
| ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:169:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
169 | int mid=l+r>>1;
| ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:193:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
193 | int mid=l+r>>1;
| ~^~
/usr/bin/ld: /tmp/ccFZKm2G.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status
