oj.uz

Submission #1016112

# Submission time Handle Problem Language Result Execution time Memory
1016112 2024-07-07T11:55:43 Z huutuan Game (IOI13_game) C++14
63 / 100
 1171 ms 256000 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;
   Node (){
      val=0;
      l=nullptr;
      r=nullptr;
   }
};

struct SegmentTree{
   Node *root;
   SegmentTree *l;
   SegmentTree *r;
   SegmentTree(){
      root=new Node();
      l=nullptr;
      r=nullptr;
   }
   void update(Node *t, int l, int r, int pos, long long val){
      if (l==r){
         t->val=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid){
         if (!t->l) t->l=new Node();
         update(t->l, l, mid, pos, val);
      }else{
         if (!t->r) t->r=new Node();
         update(t->r, mid+1, r, 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, int R){
      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, mid, L, R):0, t->r?get(t->r, mid+1, 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, 1, 1e9, y, y):0, t->r?t->r->get(t->r->root, 1, 1e9, y, y):0);
      }
      t->update(t->root, 1, 1e9, 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, 1, 1e9, 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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 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 2 ms 684 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 445 ms 54776 KB Output is correct
5 Correct 377 ms 54412 KB Output is correct
6 Correct 551 ms 52308 KB Output is correct
7 Correct 569 ms 51856 KB Output is correct
8 Correct 388 ms 33152 KB Output is correct
9 Correct 514 ms 52268 KB Output is correct
10 Correct 484 ms 51540 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 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 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 616 KB Output is correct
11 Correct 2 ms 416 KB Output is correct
12 Correct 730 ms 22840 KB Output is correct
13 Correct 922 ms 12964 KB Output is correct
14 Correct 324 ms 5824 KB Output is correct
15 Correct 1096 ms 18000 KB Output is correct
16 Correct 333 ms 27580 KB Output is correct
17 Correct 794 ms 21116 KB Output is correct
18 Correct 1171 ms 29064 KB Output is correct
19 Correct 995 ms 29032 KB Output is correct
20 Correct 946 ms 28752 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 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 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 424 KB Output is correct
12 Correct 460 ms 54612 KB Output is correct
13 Correct 370 ms 54352 KB Output is correct
14 Correct 477 ms 52048 KB Output is correct
15 Correct 512 ms 51728 KB Output is correct
16 Correct 378 ms 33112 KB Output is correct
17 Correct 525 ms 52308 KB Output is correct
18 Correct 505 ms 51536 KB Output is correct
19 Correct 726 ms 22692 KB Output is correct
20 Correct 952 ms 12860 KB Output is correct
21 Correct 286 ms 5952 KB Output is correct
22 Correct 1030 ms 18020 KB Output is correct
23 Correct 355 ms 27636 KB Output is correct
24 Correct 750 ms 21072 KB Output is correct
25 Correct 1118 ms 28960 KB Output is correct
26 Correct 1002 ms 29072 KB Output is correct
27 Correct 933 ms 28488 KB Output is correct
28 Correct 553 ms 256000 KB Output is correct
29 Runtime error 980 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 2 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 2 ms 676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 420 KB Output is correct
12 Correct 454 ms 54668 KB Output is correct
13 Correct 364 ms 54320 KB Output is correct
14 Correct 547 ms 52036 KB Output is correct
15 Correct 541 ms 51944 KB Output is correct
16 Correct 336 ms 33108 KB Output is correct
17 Correct 600 ms 52296 KB Output is correct
18 Correct 477 ms 51776 KB Output is correct
19 Correct 714 ms 22616 KB Output is correct
20 Correct 959 ms 12952 KB Output is correct
21 Correct 308 ms 5716 KB Output is correct
22 Correct 1059 ms 18020 KB Output is correct
23 Correct 345 ms 27476 KB Output is correct
24 Correct 710 ms 21072 KB Output is correct
25 Correct 1071 ms 29024 KB Output is correct
26 Correct 1006 ms 29008 KB Output is correct
27 Correct 1006 ms 28500 KB Output is correct
28 Correct 578 ms 256000 KB Output is correct
29 Runtime error 916 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -