oj.uz

Submission #1090973

# Submission time Handle Problem Language Result Execution time Memory
1090973 2024-09-19T09:22:57 Z modwwe Game (IOI13_game) C++17
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()
    {
        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);

    }
    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;
    }
    long long get2(int l,int r,int l1,Node* u)
    {
        while(1)
        {
            if(l==r)
            {
                return u->gcd;
            }
            int mid=l+r>>1;
            if(l1<=mid)
            {
                if(u->c[0]==NULL) return 0;
                u=u->c[0];
                r=mid;
            }
            else
            {
                if(u->c[1]==NULL) return 0;
                u=u->c[1];
                l=mid+1;
            }
        }
    }
};
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]);
    }
    long long s=0;
    if(u->c[0]!=NULL) s=u->c[0]->st.get2(1,k,r1,u->c[0]->rot);
    if(u->c[1]!=NULL) s=__gcd(s,u->c[1]->st.get2(1,k,r1,u->c[1]->rot));
    u->st.upd(1,k,r1,s,u->rot);
}
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:100:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:125:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'long long int segtree::get2(int, int, int, Node*)':
game.cpp:140:22: 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:176:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |     int mid=l+r>>1;
      |             ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:200:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  200 |     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 344 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 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 1 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 337 ms 17024 KB Output is correct
5 Correct 204 ms 16900 KB Output is correct
6 Correct 291 ms 14484 KB Output is correct
7 Correct 291 ms 14268 KB Output is correct
8 Correct 204 ms 10856 KB Output is correct
9 Correct 285 ms 14420 KB Output is correct
10 Correct 181 ms 13888 KB Output is correct
11 Correct 0 ms 344 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 432 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 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 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 426 ms 19876 KB Output is correct
13 Correct 666 ms 10064 KB Output is correct
14 Correct 154 ms 5572 KB Output is correct
15 Correct 772 ms 13404 KB Output is correct
16 Correct 126 ms 22608 KB Output is correct
17 Correct 555 ms 16464 KB Output is correct
18 Correct 809 ms 24144 KB Output is correct
19 Correct 697 ms 24096 KB Output is correct
20 Correct 513 ms 23380 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 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 388 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 436 KB Output is correct
12 Correct 294 ms 16980 KB Output is correct
13 Correct 198 ms 16952 KB Output is correct
14 Correct 266 ms 14420 KB Output is correct
15 Correct 300 ms 14164 KB Output is correct
16 Correct 238 ms 10944 KB Output is correct
17 Correct 298 ms 14240 KB Output is correct
18 Correct 183 ms 13908 KB Output is correct
19 Correct 433 ms 20068 KB Output is correct
20 Correct 635 ms 10236 KB Output is correct
21 Correct 138 ms 5716 KB Output is correct
22 Correct 751 ms 13400 KB Output is correct
23 Correct 127 ms 22612 KB Output is correct
24 Correct 459 ms 16536 KB Output is correct
25 Correct 688 ms 23892 KB Output is correct
26 Correct 634 ms 24092 KB Output is correct
27 Correct 481 ms 23376 KB Output is correct
28 Correct 512 ms 256000 KB Output is correct
29 Runtime error 963 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 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 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 315 ms 17172 KB Output is correct
13 Correct 183 ms 16844 KB Output is correct
14 Correct 273 ms 14464 KB Output is correct
15 Correct 286 ms 14276 KB Output is correct
16 Correct 207 ms 10780 KB Output is correct
17 Correct 278 ms 14416 KB Output is correct
18 Correct 181 ms 14160 KB Output is correct
19 Correct 426 ms 19868 KB Output is correct
20 Correct 651 ms 10060 KB Output is correct
21 Correct 148 ms 5712 KB Output is correct
22 Correct 787 ms 13316 KB Output is correct
23 Correct 118 ms 22636 KB Output is correct
24 Correct 471 ms 16468 KB Output is correct
25 Correct 736 ms 24060 KB Output is correct
26 Correct 663 ms 24124 KB Output is correct
27 Correct 483 ms 23380 KB Output is correct
28 Correct 638 ms 256000 KB Output is correct
29 Runtime error 986 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -