oj.uz

Submission #1016117

# Submission time Handle Problem Language Result Execution time Memory
1016117 2024-07-07T12:05:12 Z huutuan Game (IOI13_game) C++14
0 / 100
 372 ms 36768 KB 
#include "game.h"

long long gcd2(long long X, long long Y) {
   long long tmp;
   while (X != Y && Y != 0) {
      tmp = X;
      X = Y;
      Y = tmp % Y;
   }
   return X;
}

#include <assert.h>

int R, C;

struct Node{
   long long val;
   Node *l;
   Node *r;
   int lv, rv;
   Node (int _lv, int _rv){
      val=0;
      l=nullptr;
      r=nullptr;
      lv=_lv, rv=_rv;
   }
};

struct SegmentTree{
   Node *root;
   SegmentTree *l;
   SegmentTree *r;
   SegmentTree(){
      root=new Node(1, 1e9);
      l=nullptr;
      r=nullptr;
   }
   void update(Node *t, int pos, long long val){
      int l=t->lv, r=t->rv;
      if (l==r){
         t->val=val;
         return;
      }
      int mid=(l+r)>>1;
      Node *&tt=pos<=mid?t->l:t->r;
      if (!tt){
         tt=new Node(pos, pos);
         tt->val=val;
      }else if (tt->lv<=pos && pos<=tt->rv){
         update(tt, pos, val);
      }else{
         do{
            (pos<=mid?r:l)=mid;
            mid=(l+r)>>1;
         }while ((pos<=mid)==(tt->lv<=mid));
         Node *tmp=new Node(l, r);
         (tt->lv<=mid?tmp->l:tmp->r)=tt;
         tt=tmp;
         update(tmp, pos, val);
      }
      t->val=gcd2(t->l?t->l->val:0, t->r?t->r->val:0);
   }
   long long get(Node *t, int L, int R){
      int l=t->lv, r=t->rv;
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t->val;
      int mid=(l+r)>>1;
      return gcd2(t->l?get(t->l, L, R):0, t->r?get(t->r, L, R):0);
   }
};

struct SegmentTree2d{
   SegmentTree *root;
   SegmentTree2d(){
      root=new SegmentTree();
   }
   void update(SegmentTree *t, int l, int r, int x, int y, long long val){
      if (l!=r){
         int mid=(l+r)>>1;
         if (x<=mid){
            if (!t->l) t->l=new SegmentTree();
            update(t->l, l, mid, x, y, val);
         }else{
            if (!t->r) t->r=new SegmentTree();
            update(t->r, mid+1, r, x, y, val);
         }
         val=gcd2(t->l?t->l->get(t->l->root, y, y):0, t->r?t->r->get(t->r->root, y, y):0);
      }
      t->update(t->root, y, val);
   }
   long long get(SegmentTree *t, int l, int r, int lx, int rx, int ly, int ry){
      if (rx<l || r<lx) return 0;
      if (lx<=l && r<=rx) return t->get(t->root, ly, ry);
      int mid=(l+r)>>1;
      return gcd2(t->l?get(t->l, l, mid, lx, rx, ly, ry):0, t->r?get(t->r, mid+1, r, lx, rx, ly, ry):0);
   }
} st;

void init(int _R, int _C) {
   R=_R; C=_C;
}

void update(int P, int Q, long long K) {
   ++P; ++Q;
   st.update(st.root, 1, 1e9, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
   ++P; ++Q; ++U; ++V;
   return st.get(st.root, 1, 1e9, P, U, Q, V);
}

Compilation message

game.cpp: In member function 'long long int SegmentTree::get(Node*, int, int)':
game.cpp:68:11: warning: unused variable 'mid' [-Wunused-variable]
   68 |       int mid=(l+r)>>1;
      |           ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 428 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 372 ms 36768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 424 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -