oj.uz

Submission #110289

# Submission time Handle Problem Language Result Execution time Memory
110289 2019-05-10T13:37:11 Z ksmzzang2003 Game (IOI13_game) C++17
0 / 100
 4 ms 384 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int R, C, Q;

ll GCD(ll A, ll B){
    if (!B) return A;
    return GCD(B, A%B);
}

struct Node1D{
   ll val=0;
   int pos=-1;
   Node1D* lc=NULL, *rc=NULL;

   void update(int s, int e, int t, ll v){ //s,e 는 이 노드의 구간이다 .
      if (e < t || t < s) return;
      if (s == e){
         val = v;
         return;
      }
      int mid = (s+e)/2;
      if (pos>=0){ // pos>=0 이라는 소리는 이 노드는 이미 계산됬다는 것
         if (pos <= mid){
            lc = new Node1D;
            lc->pos = pos, lc->val = val;
         }
         else{
            rc = new Node1D;
            rc->pos = pos, rc->val = val;
         }
         pos=-1;
      }

      if (t <= mid){ // 타겟이 왼쪽에 있으면 일단 타겟만 만든다.
         if (lc == NULL){
            lc = new Node1D;
            lc->pos = t, lc->val = v;
         }
         else lc->update(s, mid, t, v);
      }
      else{
         if (rc == NULL){
            rc = new Node1D;
            rc->pos = t, rc->val = v;
         }
         else rc->update(mid+1, e, t, v);
      }
      val = 0;
      if (lc != NULL) val = GCD(val, lc->val);
      if (rc != NULL) val = GCD(val, rc->val);
   }

   ll query(int s, int e, int ts, int te){
      if (te < s || e < ts) return 0;
      if (ts <= s && e <= te) return val;
      
      int mid = (s+e)/2;
      ll ret = 0;
      if (lc != NULL) ret = GCD(ret, lc->query(s, mid, ts, te));
      if (rc != NULL) ret = GCD(ret, rc->query(mid+1, e, ts, te));
      return ret;
   }
};

struct Node2D{
   Node1D *T = new Node1D;
   Node2D *lc=NULL, *rc=NULL;

   void update(int s, int e, int tx, int ty, ll v){
      if (e < tx || tx < s) return;
      if (s == e){
         T->update(0, C-1, ty, v);
         return;
      }
      int mid = (s+e)/2;
      if (tx <= mid){
         if (lc == NULL) lc = new Node2D;
         lc->update(s, mid, tx, ty, v);
      }
      else{
         if (rc == NULL) rc = new Node2D;
         rc->update(mid+1, e, tx, ty, v);
      }
      ll ret = 0;
      
      if (lc != NULL) ret = GCD(ret, lc->T->query(0, C-1, ty, ty));
      if (rc != NULL) ret = GCD(ret, rc->T->query(0, C-1, ty, ty));
      T->update(0, C-1, ty, ret);
   }

   ll query(int s, int e, int txs, int txe, int tys, int tye){
      if (txe < s || e < txs) return 0;
      if (txs <= s && e <= txe) return T->query(0, C-1, tys, tye);
      int mid = (s+e)/2;
      ll ret = 0;
      if (lc != NULL) ret = GCD(ret, lc->query(s, mid, txs, txe, tys, tye));
      if (rc != NULL) ret = GCD(ret, rc->query(mid+1, e, txs, txe, tys, tye));
      return ret;
   }
} *Seg = new Node2D;

void init(int r, int c){
   R=r, C=c;
}

void update(int x, int y, ll v){
   Seg->update(0, R-1, x, y, v);
}

ll calculate(int x1, int y1, int x2, int y2){
   return Seg->query(0, R-1, x1, x2, y1, y2);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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