Submission #989512

#	Time	Username	Problem	Language	Result	Execution time	Memory
989512		User0069	Game (IOI13_game)	C++17	0 / 100	1 ms	348 KiB

game

#include<bits/stdc++.h>
#include"game.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int n,q,a[maxn],boundr,boundc;
long long gcd(long long a,long long b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
struct segtreetree
{
    struct segtree
    {
        struct node
        {
            long long val;
            node *l,*r;
            node(long long val): val(val),l(NULL),r(NULL){};
        }*root;
        long long vall(node* x) {return x?x->val:0;}
        void update(node* kk,int cl,int cr,int pos,long long val)
        {
            if(cl==cr)
            {
                kk->val=val;
                return;
            }
            int mid=(cl+cr)/2;
            if(pos<=mid)
            {
                if(kk->l==NULL) kk->l=new node(0);
                update(kk->l,cl,mid,pos,val);
            }
            else
            {
                if(kk->r==NULL) kk->r=new node(0);
                update(kk->r,mid+1,cr,pos,val);
            }
            kk->val=gcd(vall(kk->l),vall(kk->r));
        }
        long long get(node* kk,int cl,int cr,int l,int r)
        {
            if(kk==NULL||cl>r||cr<l) return 0;
            if(cl>=l&&cr<=r) return kk->val;
            int mid=(cl+cr)/2;
            return gcd(get(kk->l,cl,mid,l,r),get(kk->r,mid+1,cr,l,r));
        }
        segtree *l, *r;
        segtree(): root(new node(0)), l(NULL), r(NULL) {};
    }*root;
    void update(segtree* kk,int cl,int cr,int r,int c,long long val)
    {
        if(cl==cr)
        {
            kk->update(kk->root,0,boundc,c,val);
            return;
        }
        int mid=(cl+cr)/2;
        if(r<=mid)
        {
            if(kk->l==NULL) kk->l=new segtree();
            update(kk->l,cl,mid,r,c,val);
        }
        else
        {
            if(kk->r==NULL) kk->r=new segtree();
            update(kk->r,mid+1,cr,r,c,val);
        }
        int u=0;
        if(kk->l) u=kk->l->get(kk->l->root,0,boundc,c,c);
        int v=0;
        if(kk->r) v=kk->r->get(kk->r->root,0,boundc,c,c);
        kk->update(kk->root,0,boundc,c,gcd(u,v));
    }
    long long get(segtree *kk,int cl,int cr,int u,int l,int d,int r)
    {
        if(kk==NULL||cl>d||cr<u) return 0;
        if(cl>=u&&cr<=d) return kk->get(kk->root,0,boundc,l,r);
        int mid=(cl+cr)/2;
        return gcd(get(kk->l,cl,mid,u,l,d,r),get(kk->r,mid+1,cr,u,l,d,r));
    }
    segtreetree(): root(new segtree()){};
}*root=new segtreetree();
void init(int R,int C)
{
    boundr=R-1;
    boundc=C-1;
}
void update(int P,int Q, long long k)
{
    root->update(root->root,0,boundr,P,Q,k);
}
long long calculate(int P,int Q,int U,int V)
{
    return root->get(root->root,0,boundr,P,Q,U,V);
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int R,C,N;
//    cin>>R>>C>>N;
//    init(R,C);
//    while(N--)
//    {
//        int t;
//        cin>>t;
//        if(t==1)
//        {
//            int a,b,c;
//            cin>>a>>b>>c;
//            update(a,b,c);
//        }
//        else
//        {
//            int a,b,c,d;
//            cin>>a>>b>>c>>d;
//            cout<<calculate(a,b,c,d)<<"\n";
//        }
//    }
////    cout<<calculate(0,1,2,1);
//}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20