oj.uz

Submission #1090932

# Submission time Handle Problem Language Result Execution time Memory
1090932 2024-09-19T08:02:10 Z modwwe Game (IOI13_game) C++17
63 / 100
 1064 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(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

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.0 / 10.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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 293 ms 16928 KB Output is correct
5 Correct 213 ms 16948 KB Output is correct
6 Correct 284 ms 14600 KB Output is correct
7 Correct 309 ms 14164 KB Output is correct
8 Correct 215 ms 10952 KB Output is correct
9 Correct 303 ms 14416 KB Output is correct
10 Correct 196 ms 13952 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 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 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 459 ms 20052 KB Output is correct
13 Correct 664 ms 10064 KB Output is correct
14 Correct 136 ms 5536 KB Output is correct
15 Correct 777 ms 13136 KB Output is correct
16 Correct 109 ms 22608 KB Output is correct
17 Correct 473 ms 16528 KB Output is correct
18 Correct 745 ms 23892 KB Output is correct
19 Correct 653 ms 24104 KB Output is correct
20 Correct 479 ms 23460 KB Output is correct
21 Correct 0 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 285 ms 16968 KB Output is correct
13 Correct 198 ms 16980 KB Output is correct
14 Correct 267 ms 14596 KB Output is correct
15 Correct 292 ms 14240 KB Output is correct
16 Correct 222 ms 10864 KB Output is correct
17 Correct 304 ms 14364 KB Output is correct
18 Correct 195 ms 13840 KB Output is correct
19 Correct 437 ms 20004 KB Output is correct
20 Correct 666 ms 10216 KB Output is correct
21 Correct 160 ms 5716 KB Output is correct
22 Correct 787 ms 13496 KB Output is correct
23 Correct 112 ms 22608 KB Output is correct
24 Correct 467 ms 16456 KB Output is correct
25 Correct 727 ms 23888 KB Output is correct
26 Correct 676 ms 24028 KB Output is correct
27 Correct 511 ms 23368 KB Output is correct
28 Correct 551 ms 256000 KB Output is correct
29 Runtime error 1006 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 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 296 ms 17032 KB Output is correct
13 Correct 187 ms 17060 KB Output is correct
14 Correct 272 ms 14596 KB Output is correct
15 Correct 284 ms 14164 KB Output is correct
16 Correct 208 ms 10836 KB Output is correct
17 Correct 301 ms 14420 KB Output is correct
18 Correct 197 ms 13904 KB Output is correct
19 Correct 476 ms 20048 KB Output is correct
20 Correct 690 ms 10148 KB Output is correct
21 Correct 146 ms 5712 KB Output is correct
22 Correct 779 ms 13088 KB Output is correct
23 Correct 121 ms 22548 KB Output is correct
24 Correct 471 ms 16468 KB Output is correct
25 Correct 752 ms 23932 KB Output is correct
26 Correct 658 ms 24144 KB Output is correct
27 Correct 473 ms 23444 KB Output is correct
28 Correct 518 ms 256000 KB Output is correct
29 Runtime error 1064 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -