oj.uz

Submission #1090918

# Submission time Handle Problem Language Result Execution time Memory
1090918 2024-09-19T07:18:01 Z modwwe Game (IOI13_game) C++14
63 / 100
 1088 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);
        }
    }
    void upddd(int l,int r,int l1,Node* u,Node* v)
    {
 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();
            upddd(l,mid,l1,u->c[0],v->c[0]);
        }
        else
        {
            if(u->c[1]==NULL) u->c[1]=new Node();
             upddd(mid+1,r,l1,u->c[1],v->c[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;
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 604 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 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 309 ms 17144 KB Output is correct
5 Correct 209 ms 16960 KB Output is correct
6 Correct 304 ms 14608 KB Output is correct
7 Correct 327 ms 14248 KB Output is correct
8 Correct 225 ms 10832 KB Output is correct
9 Correct 306 ms 14676 KB Output is correct
10 Correct 276 ms 13904 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 1 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 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 1 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 472 ms 19996 KB Output is correct
13 Correct 669 ms 9980 KB Output is correct
14 Correct 176 ms 5716 KB Output is correct
15 Correct 732 ms 13236 KB Output is correct
16 Correct 121 ms 22600 KB Output is correct
17 Correct 494 ms 16464 KB Output is correct
18 Correct 772 ms 23888 KB Output is correct
19 Correct 698 ms 24148 KB Output is correct
20 Correct 647 ms 23376 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 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 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 1 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 330 ms 16964 KB Output is correct
13 Correct 211 ms 16912 KB Output is correct
14 Correct 286 ms 14584 KB Output is correct
15 Correct 299 ms 14160 KB Output is correct
16 Correct 210 ms 10852 KB Output is correct
17 Correct 282 ms 14404 KB Output is correct
18 Correct 275 ms 13908 KB Output is correct
19 Correct 425 ms 20048 KB Output is correct
20 Correct 657 ms 10168 KB Output is correct
21 Correct 156 ms 5968 KB Output is correct
22 Correct 719 ms 13136 KB Output is correct
23 Correct 119 ms 22612 KB Output is correct
24 Correct 491 ms 16464 KB Output is correct
25 Correct 735 ms 23888 KB Output is correct
26 Correct 642 ms 24060 KB Output is correct
27 Correct 597 ms 23460 KB Output is correct
28 Correct 511 ms 256000 KB Output is correct
29 Runtime error 989 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 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 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 440 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 301 ms 17084 KB Output is correct
13 Correct 196 ms 16860 KB Output is correct
14 Correct 273 ms 14420 KB Output is correct
15 Correct 291 ms 14164 KB Output is correct
16 Correct 229 ms 11012 KB Output is correct
17 Correct 312 ms 14416 KB Output is correct
18 Correct 281 ms 13904 KB Output is correct
19 Correct 458 ms 20056 KB Output is correct
20 Correct 631 ms 10224 KB Output is correct
21 Correct 155 ms 5540 KB Output is correct
22 Correct 755 ms 13240 KB Output is correct
23 Correct 128 ms 22612 KB Output is correct
24 Correct 521 ms 16468 KB Output is correct
25 Correct 749 ms 23892 KB Output is correct
26 Correct 674 ms 24144 KB Output is correct
27 Correct 624 ms 23520 KB Output is correct
28 Correct 543 ms 256000 KB Output is correct
29 Runtime error 1088 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -