oj.uz

Submission #1090926

# Submission time Handle Problem Language Result Execution time Memory
1090926 2024-09-19T07:49:19 Z modwwe Game (IOI13_game) C++14
63 / 100
 986 ms 256000 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;
    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(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

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:162:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:186:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:213:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  213 |     int mid=l+r>>1;
      |             ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:237:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  237 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 0 ms 356 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 1 ms 356 KB Output is correct
12 Correct 0 ms 356 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 313 ms 17112 KB Output is correct
5 Correct 183 ms 16984 KB Output is correct
6 Correct 278 ms 14608 KB Output is correct
7 Correct 302 ms 14172 KB Output is correct
8 Correct 214 ms 10860 KB Output is correct
9 Correct 290 ms 14260 KB Output is correct
10 Correct 262 ms 13904 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 431 ms 19924 KB Output is correct
13 Correct 646 ms 10064 KB Output is correct
14 Correct 146 ms 5712 KB Output is correct
15 Correct 736 ms 13136 KB Output is correct
16 Correct 112 ms 22608 KB Output is correct
17 Correct 476 ms 16472 KB Output is correct
18 Correct 769 ms 24004 KB Output is correct
19 Correct 665 ms 24160 KB Output is correct
20 Correct 592 ms 23524 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 315 ms 16960 KB Output is correct
13 Correct 185 ms 16980 KB Output is correct
14 Correct 284 ms 14444 KB Output is correct
15 Correct 295 ms 14160 KB Output is correct
16 Correct 213 ms 11016 KB Output is correct
17 Correct 288 ms 14372 KB Output is correct
18 Correct 261 ms 13992 KB Output is correct
19 Correct 415 ms 20048 KB Output is correct
20 Correct 646 ms 10064 KB Output is correct
21 Correct 141 ms 5716 KB Output is correct
22 Correct 725 ms 13288 KB Output is correct
23 Correct 132 ms 22608 KB Output is correct
24 Correct 467 ms 16452 KB Output is correct
25 Correct 718 ms 24048 KB Output is correct
26 Correct 634 ms 23992 KB Output is correct
27 Correct 580 ms 23532 KB Output is correct
28 Correct 465 ms 256000 KB Output is correct
29 Runtime error 906 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 352 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 0 ms 352 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 306 ms 17132 KB Output is correct
13 Correct 210 ms 16984 KB Output is correct
14 Correct 285 ms 14420 KB Output is correct
15 Correct 301 ms 14404 KB Output is correct
16 Correct 205 ms 10836 KB Output is correct
17 Correct 284 ms 14388 KB Output is correct
18 Correct 288 ms 13824 KB Output is correct
19 Correct 427 ms 20052 KB Output is correct
20 Correct 618 ms 10072 KB Output is correct
21 Correct 163 ms 5680 KB Output is correct
22 Correct 783 ms 13152 KB Output is correct
23 Correct 117 ms 22656 KB Output is correct
24 Correct 476 ms 16464 KB Output is correct
25 Correct 713 ms 23892 KB Output is correct
26 Correct 623 ms 24068 KB Output is correct
27 Correct 570 ms 23380 KB Output is correct
28 Correct 526 ms 256000 KB Output is correct
29 Runtime error 986 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -