oj.uz

답안 #1090959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090959 2024-09-19T08:54:55 Z modwwe 게임 (IOI13_game) C++11
63 / 100
 853 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;
    long long gcd_left;
    long long gcd_right;
    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 upddd(int l,int r,int l1,Node* u,Node* v,bool x)
    {
        while(1)
        {
            if(x)
                u->gcd=__gcd(u->gcd_left,v->gcd),
                   u->gcd_right=v->gcd;
            else
                u->gcd=__gcd(u->gcd_right,v->gcd),
                   u->gcd_left=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]);
          u->st.upddd(1,k,r1,u->rot,u->c[0]->rot,0);
    }
    else
    {
        if(u->c[1]==NULL) u->c[1]=new treap();
        upd(mid+1,r,l1,x,r1,u->c[1]);
  u->st.upddd(1,k,r1,u->rot,u->c[1]->rot,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:103:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In member function 'void segtree::upddd(int, int, int, Node*, Node*, bool)':
game.cpp:135:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |             int mid=l+r>>1;
      |                     ~^~
game.cpp: In member function 'long long int segtree::get(int, int, int, int, Node*)':
game.cpp:159:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |         int mid=l+r>>1;
      |                 ~^~
game.cpp: In function 'void upd(int, int, int, long long int, int, treap*)':
game.cpp:187:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |     int mid=l+r>>1;
      |             ~^~
game.cpp: In function 'void get(int, int, int, int, int, int, treap*)':
game.cpp:212:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  212 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 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 528 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 436 KB Output is correct
10 Correct 0 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

# 결과 실행 시간 메모리 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 319 ms 16872 KB Output is correct
5 Correct 225 ms 17232 KB Output is correct
6 Correct 290 ms 14088 KB Output is correct
7 Correct 370 ms 13904 KB Output is correct
8 Correct 248 ms 9040 KB Output is correct
9 Correct 317 ms 13992 KB Output is correct
10 Correct 185 ms 13480 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 498 ms 25568 KB Output is correct
13 Correct 676 ms 12628 KB Output is correct
14 Correct 156 ms 5700 KB Output is correct
15 Correct 783 ms 16976 KB Output is correct
16 Correct 122 ms 31060 KB Output is correct
17 Correct 532 ms 21252 KB Output is correct
18 Correct 828 ms 32460 KB Output is correct
19 Correct 734 ms 32732 KB Output is correct
20 Correct 541 ms 32084 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 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 337 ms 21120 KB Output is correct
13 Correct 224 ms 21080 KB Output is correct
14 Correct 314 ms 18620 KB Output is correct
15 Correct 341 ms 18416 KB Output is correct
16 Correct 242 ms 13304 KB Output is correct
17 Correct 349 ms 18516 KB Output is correct
18 Correct 208 ms 18304 KB Output is correct
19 Correct 473 ms 25684 KB Output is correct
20 Correct 642 ms 12600 KB Output is correct
21 Correct 135 ms 5712 KB Output is correct
22 Correct 737 ms 16980 KB Output is correct
23 Correct 113 ms 31056 KB Output is correct
24 Correct 506 ms 21328 KB Output is correct
25 Correct 853 ms 32592 KB Output is correct
26 Correct 730 ms 32712 KB Output is correct
27 Correct 530 ms 32080 KB Output is correct
28 Runtime error 366 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 604 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 324 ms 21108 KB Output is correct
13 Correct 212 ms 21072 KB Output is correct
14 Correct 293 ms 18824 KB Output is correct
15 Correct 342 ms 18544 KB Output is correct
16 Correct 224 ms 13260 KB Output is correct
17 Correct 329 ms 18896 KB Output is correct
18 Correct 214 ms 18168 KB Output is correct
19 Correct 464 ms 26004 KB Output is correct
20 Correct 669 ms 12628 KB Output is correct
21 Correct 144 ms 5792 KB Output is correct
22 Correct 776 ms 16964 KB Output is correct
23 Correct 120 ms 31060 KB Output is correct
24 Correct 522 ms 21332 KB Output is correct
25 Correct 839 ms 32592 KB Output is correct
26 Correct 728 ms 32540 KB Output is correct
27 Correct 527 ms 31928 KB Output is correct
28 Runtime error 359 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -