Submission #898949

#	Time	Username	Problem	Language	Result	Execution time	Memory
898949		Faisal_Saqib	Game (IOI13_game)	C++17	100 / 100	1595 ms	73188 KiB

game

#include "game.h"
#include <iostream>
#include <numeric>
using namespace std;
// const int N=1e9;
int R,C;
class AVL{
    public:
        class node{
            public:
                long long subtree_gcd=0,own_value=0;
                int height,key,mx=-1e9,mi=1e9;
                node * left;
                node * right;
                node(int k,long long tp){
                    height = 1;
                    mx=mi=k;
                    key = k;
                    subtree_gcd=tp;
                    own_value=tp;
                    left = NULL;
                    right = NULL;
                }
        };
        node * root = NULL;
        int n;
        void Update(int& x,long long& val){
            root=insertUtil(root, x,val);
        }
        long long get(int& l,int& r)
        {
          // cout<<"GCd for "<<l<<' '<<r<<" is "<<get(root,l,r)<<endl;
          return get(root,l,r);
        }
        void print()
        {
          print(root);
        }
    private:
        void Rectify(node * head)
        {
          if(head==NULL)
            return;
            head->subtree_gcd=head->own_value;
            head->mx=head->key;
            head->mi=head->key;
            if(head->left!=NULL)
            {
              head->mx=max(head->mx,head->left->mx);
              head->mi=min(head->mi,head->left->mi);
              head->subtree_gcd=gcd(head->subtree_gcd,head->left->subtree_gcd);
            }
            if(head->right!=NULL)
            {
              head->mx=max(head->mx,head->right->mx);
              head->mi=min(head->mi,head->right->mi);
              head->subtree_gcd=gcd(head->subtree_gcd,head->right->subtree_gcd);
            }
        }
      void print(node* h)
      {
        if(h==NULL)
          return;
        print(h->left);
        cout<<h->key<<' '<<h->mi<<' '<<h->mx<<' '<<h->own_value<<' '<<h->subtree_gcd<<endl;
        print(h->right);
      }
        int height(node * head){
            if(head==NULL) return 0;
            return head->height;
        }
        node * rightRotation(node * head){
            node * newhead = head->left;
            head->left = newhead->right;
            newhead->right = head;
            head->height = 1+max(height(head->left), height(head->right));
            newhead->height = 1+max(height(newhead->left), height(newhead->right));
            Rectify(head);
            Rectify(newhead);
            return newhead;
        }

        node * leftRotation(node * head){
            node * newhead = head->right;
            head->right = newhead->left;
            newhead->left = head;
            head->height = 1+max(height(head->left), height(head->right));
            newhead->height = 1+max(height(newhead->left), height(newhead->right));
            Rectify(head);
            Rectify(newhead);
            return newhead;
        }
        long long get(node* head,int& l,int& r)
        {
            if(head==NULL)
              return 0;
            if(head->mx<l or r<head->mi)
              return 0;
            if(l<=head->mi and head->mx<=r)
              return head->subtree_gcd;
            long long ans=gcd(get(head->left,l,r),get(head->right,l,r));
            if(l<=head->key and head->key<=r)
            {
                ans=gcd(ans,head->own_value);
            }
            return ans;
        }
        node * insertUtil(node * head, int& x,long long& tp){
            if(head==NULL){
                n+=1;
                node * temp = new node(x,tp);
                return temp;
            }
            if(head->key==x)
            {
              head->own_value=tp;
              Rectify(head);
              return head;
            }
            if(x < head->key) head->left = insertUtil(head->left, x,tp);
            else if(x > head->key) head->right = insertUtil(head->right, x,tp);
            Rectify(head);
            head->height = 1 + max(height(head->left), height(head->right));
            int bal = height(head->left) - height(head->right);
            if(bal>1){
                if(x < head->left->key){
                    return rightRotation(head);
                }else{
                    head->left = leftRotation(head->left);
                    return rightRotation(head);
                }
            }else if(bal<-1){
                if(x > head->right->key){
                    return leftRotation(head);
                }else{
                    head->right = rightRotation(head->right);
                    return leftRotation(head);
                }
            }
            return head;
        }

};
struct SegmentTree2D
{
  AVL heavy;
  SegmentTree2D* next[2];
  SegmentTree2D(int l,int r)
  {
    next[0]=next[1]=NULL;
  }
  long long get(int& sx,int& ex,int& sy,int& ey,int s=0,int e=R-1)
  {
    if(ex<s or e<sx)
      return 0;
    if(sx<=s and e<=ex)
      return heavy.get(sy,ey);
    long long ans=0;
    if(next[0]!=NULL)
      ans=gcd(ans,next[0]->get(sx,ex,sy,ey,s,(s+e)/2));
    if(next[1]!=NULL)
      ans=gcd(ans,next[1]->get(sx,ex,sy,ey,1+((s+e)/2),e));
    return ans;
  }
  void Update(int& l,int& r,long long& val,int s=0,int e=R-1)
  {
    if(s==e)
    {
      heavy.Update(r,val);
      return;
    }
    long long gdc=0;
    if(l<=((s+e)/2))
    {
      if(next[0]==NULL)
        next[0]=new SegmentTree2D(s,(s+e)/2);
      next[0]->Update(l,r,val,s,(s+e)/2);
    }
    else
    {
      if(next[1]==NULL)
        next[1]=new SegmentTree2D(1+((s+e)/2),e);
      next[1]->Update(l,r,val,1+((s+e)/2),e);
    }
    if(next[0]!=NULL)
      gdc=gcd(gdc,next[0]->heavy.get(r,r));
    if(next[1]!=NULL)
      gdc=gcd(gdc,next[1]->heavy.get(r,r));
    heavy.Update(r,gdc);
  }
};
SegmentTree2D* st;
void init(int r, int c)
{
  C=c;
  R=r;
  st=new SegmentTree2D(0,R-1);
}
void update(int p, int q, long long k)
{
  st->Update(p,q,k);
}
long long calculate(int P, int Q, int U, int V)
{
  return st->get(P,U,Q,V);
}

Compilation message (stderr)

game.cpp: In member function 'void AVL::Rectify(AVL::node*)':
game.cpp:42:11: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |           if(head==NULL)
      |           ^~
game.cpp:44:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |             head->subtree_gcd=head->own_value;
      |             ^~~~

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