| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1090957 |
2024-09-19T08:53:17 Z |
modwwe |
Game (IOI13_game) |
C++17 |
|
0 ms |
0 KB |
//#include "game.h"
//#pragma GCC optimize("conserve-stack")
//#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;
/*
main()
{
#ifndef ONLINE_JUDGE
fin(task);
fou(task);
#endif
NHP
/// cin>>s1;
///modwwe
phongbeo(),down
// checktime
}*/
struct Node
{
Node* c[2];
long long gcd;
long long gcd_left;
long long gcd_right;
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 upddd(int l,int r,int l1,Node* u,Node* v,bool x)
{
while(1)
{
if(x)
u->gcd=__gcd(u->gcd_left,v->gcd),
u->gcd_right=v->gcd;
else
u->gcd=__gcd(u->gcd_right,v->gcd),
u->gcd_left=v->gcd;
if(l==r)
{
return;
}
int mid=l+r>>1;
if(l1<=mid)
{
if(u->c[0]==NULL) u->c[0]=new Node();
u=u->c[0];
v=v->c[0];
r=mid;
}
else
{
if(u->c[1]==NULL) u->c[1]=new Node();
u=u->c[1];
v=v->c[1];
l=mid+1;
}
}
}
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(s==1) return s;
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 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]);
u->st.upddd(1,k,r1,u->rot,u->c[0]->rot,0);
}
else
{
if(u->c[1]==NULL) u->c[1]=new treap();
upd(mid+1,r,l1,x,r1,u->c[1]);
u->st.upddd(1,k,r1,u->rot,u->c[1]->rot,1);
}
/// if(u->c[1]==NULL) u->st.upddd(1,k,r1,u->rot,u->c[0]->rot);
/// else if(u->c[0]==NULL) u->st.upddd(1,k,r1,u->rot,u->c[1]->rot);
///else u->st.updd(1,k,r1,u->rot,u->c[1]->rot,u->c[0]->rot,0,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;
}
void phongbeo()
{
cin>>m>>k>>n;
init(m,k);
for(int i=1; i<=n; i++)
{
/// cout<<i,down
cin>>l;
if(l==1)
{
cin>>l>>r>>s3;
update(l,r,s3);
}
else
{
///s4=0;
cin>>l>>r>>s2>>s3;
cout<<calculate(l,r,s2,s3),down
}
}
}
Compilation message
game.cpp: In member function 'void segtree::upd(int, int, int, long long int, Node*)':
game.cpp:103:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid=l+r>>1;
| ~^~
game.cpp: In member function 'void segtree::upddd(int, int, int, Node*, Node*, bool)':
game.cpp:135:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | int mid=l+r>>1;
| ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:159:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
159 | int mid=l+r>>1;
| ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:187:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
187 | int mid=l+r>>1;
| ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:212:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
212 | int mid=l+r>>1;
| ~^~
/usr/bin/ld: /tmp/ccNOmtnU.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
