oj.uz

Submission #1090759

# Submission time Handle Problem Language Result Execution time Memory
1090759 2024-09-18T17:01:17 Z modwwe Game (IOI13_game) C++17
63 / 100
 971 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;

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:90:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'void segtree::updd(int, int, int, Node*, Node*, Node*, bool, bool)':
game.cpp:116:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:140:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:171:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  171 |     int mid=l+r>>1;
      |             ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:195:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  195 |     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 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 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 306 ms 17096 KB Output is correct
5 Correct 184 ms 16976 KB Output is correct
6 Correct 279 ms 14632 KB Output is correct
7 Correct 292 ms 14164 KB Output is correct
8 Correct 212 ms 10812 KB Output is correct
9 Correct 308 ms 14316 KB Output is correct
10 Correct 281 ms 13916 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.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 344 KB Output is correct
6 Correct 1 ms 600 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 445 ms 19896 KB Output is correct
13 Correct 652 ms 10320 KB Output is correct
14 Correct 148 ms 5664 KB Output is correct
15 Correct 728 ms 13188 KB Output is correct
16 Correct 122 ms 22600 KB Output is correct
17 Correct 492 ms 16464 KB Output is correct
18 Correct 788 ms 23888 KB Output is correct
19 Correct 660 ms 24268 KB Output is correct
20 Correct 613 ms 23496 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 492 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 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 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 311 ms 17060 KB Output is correct
13 Correct 182 ms 16896 KB Output is correct
14 Correct 271 ms 14516 KB Output is correct
15 Correct 321 ms 14364 KB Output is correct
16 Correct 202 ms 10852 KB Output is correct
17 Correct 296 ms 14476 KB Output is correct
18 Correct 259 ms 13904 KB Output is correct
19 Correct 412 ms 20048 KB Output is correct
20 Correct 627 ms 10064 KB Output is correct
21 Correct 143 ms 5712 KB Output is correct
22 Correct 753 ms 13308 KB Output is correct
23 Correct 123 ms 22608 KB Output is correct
24 Correct 485 ms 16456 KB Output is correct
25 Correct 748 ms 23936 KB Output is correct
26 Correct 647 ms 24132 KB Output is correct
27 Correct 602 ms 23376 KB Output is correct
28 Correct 554 ms 256000 KB Output is correct
29 Runtime error 971 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 0 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 1 ms 344 KB Output is correct
7 Correct 0 ms 348 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 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 309 ms 17096 KB Output is correct
13 Correct 177 ms 16980 KB Output is correct
14 Correct 261 ms 14576 KB Output is correct
15 Correct 307 ms 14212 KB Output is correct
16 Correct 203 ms 10832 KB Output is correct
17 Correct 287 ms 14420 KB Output is correct
18 Correct 265 ms 13904 KB Output is correct
19 Correct 415 ms 19900 KB Output is correct
20 Correct 618 ms 10156 KB Output is correct
21 Correct 144 ms 5708 KB Output is correct
22 Correct 723 ms 13396 KB Output is correct
23 Correct 113 ms 22540 KB Output is correct
24 Correct 484 ms 16352 KB Output is correct
25 Correct 736 ms 23892 KB Output is correct
26 Correct 637 ms 24144 KB Output is correct
27 Correct 594 ms 23420 KB Output is correct
28 Correct 546 ms 256000 KB Output is correct
29 Runtime error 969 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -