Submission #1090932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090932		modwwe	Game (IOI13_game)	C++17	63 / 100	1064 ms	256000 KiB

game

#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;
    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)
    {
        while(1)
        {
                    u->gcd=0;

            if(!d) u->gcd=__gcd(v->gcd,u->gcd);
                                   if(!d1)u->gcd=__gcd(uv->gcd,u->gcd);
            if(l==r)
            {
                break;
            }
            int mid=l+r>>1;
            if(l1<=mid)
            {
                r=mid;
                if(u->c[0]==NULL) u->c[0]=new Node();
                u=u->c[0];
                if(v->c[0]==NULL||d) d=1;
                else v=v->c[0];
                if(uv->c[0]==NULL||d1) d1=1;
                else uv=uv->c[0];
            }
            else
            {
                l=mid+1;
                if(u->c[1]==NULL) u->c[1]=new Node();
                u=u->c[1];
                if(v->c[1]==NULL||d) d=1;
                else v=v->c[1];
                if(uv->c[1]==NULL||d1) d1=1;
                else uv=uv->c[1];
            }
        }
    }
    void upddd(int l,int r,int l1,Node* u,Node* v)
    {
        while(1){
        u->gcd=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]);
    }
    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)    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 (stderr)

game.cpp: In member function 'void segtree::upd(int, int, int, long long int, Node*)':
game.cpp:101:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'void segtree::updd(int, int, int, Node*, Node*, Node*, bool, bool)':
game.cpp:131:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |             int mid=l+r>>1;
      |                     ~^~
game.cpp: In member function 'void segtree::upddd(int, int, int, Node*, Node*)':
game.cpp:163:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:187:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:215:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  215 |     int mid=l+r>>1;
      |             ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:239:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  239 |     int mid=l+r>>1;
      |             ~^~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20