oj.uz

Submission #1016006

# Submission time Handle Problem Language Result Execution time Memory
1016006 2024-07-07T09:38:51 Z huutuan Game (IOI13_game) C++14
63 / 100
 1239 ms 256000 KB 
#pragma GCC optimize("Os")
#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;
      }
      int mid=(l+r)>>1;
      if (pos<=mid){
         if (!t->l) t->l=new Node();
         update(t->l, tl?tl->l:nullptr, tr?tr->l:nullptr, l, mid, pos, val, sussy);
      }else{
         if (!t->r) t->r=new Node();
         update(t->r, tl?tl->r:nullptr, tr?tr->r:nullptr, mid+1, r, pos, val, sussy);
      }
      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);
         }
      }
      t->update(t->root, t->l?t->l->root:nullptr, t->r?t->r->root:nullptr, 1, 1e9, 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, 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 716 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 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 1 ms 604 KB Output is correct
11 Correct 1 ms 360 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 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 470 ms 54812 KB Output is correct
5 Correct 424 ms 54352 KB Output is correct
6 Correct 518 ms 52156 KB Output is correct
7 Correct 513 ms 52048 KB Output is correct
8 Correct 350 ms 33092 KB Output is correct
9 Correct 519 ms 52304 KB Output is correct
10 Correct 465 ms 51536 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 1 ms 436 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 436 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 711 ms 22676 KB Output is correct
13 Correct 946 ms 12848 KB Output is correct
14 Correct 341 ms 5716 KB Output is correct
15 Correct 1230 ms 18024 KB Output is correct
16 Correct 359 ms 27636 KB Output is correct
17 Correct 747 ms 21100 KB Output is correct
18 Correct 1179 ms 29008 KB Output is correct
19 Correct 1006 ms 29036 KB Output is correct
20 Correct 1024 ms 28524 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 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 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 436 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 473 ms 54744 KB Output is correct
13 Correct 413 ms 54212 KB Output is correct
14 Correct 504 ms 52176 KB Output is correct
15 Correct 492 ms 51928 KB Output is correct
16 Correct 352 ms 33108 KB Output is correct
17 Correct 559 ms 52308 KB Output is correct
18 Correct 524 ms 51584 KB Output is correct
19 Correct 816 ms 22688 KB Output is correct
20 Correct 978 ms 12772 KB Output is correct
21 Correct 359 ms 5968 KB Output is correct
22 Correct 1239 ms 17840 KB Output is correct
23 Correct 351 ms 27580 KB Output is correct
24 Correct 771 ms 21076 KB Output is correct
25 Correct 1125 ms 28988 KB Output is correct
26 Correct 946 ms 29024 KB Output is correct
27 Correct 868 ms 28448 KB Output is correct
28 Correct 484 ms 256000 KB Output is correct
29 Runtime error 943 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 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 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 487 ms 54676 KB Output is correct
13 Correct 372 ms 54352 KB Output is correct
14 Correct 494 ms 52148 KB Output is correct
15 Correct 487 ms 51964 KB Output is correct
16 Correct 350 ms 33112 KB Output is correct
17 Correct 495 ms 52192 KB Output is correct
18 Correct 467 ms 51792 KB Output is correct
19 Correct 688 ms 22608 KB Output is correct
20 Correct 948 ms 13168 KB Output is correct
21 Correct 319 ms 5832 KB Output is correct
22 Correct 1087 ms 17996 KB Output is correct
23 Correct 336 ms 27472 KB Output is correct
24 Correct 720 ms 21024 KB Output is correct
25 Correct 1068 ms 29128 KB Output is correct
26 Correct 1004 ms 29008 KB Output is correct
27 Correct 1008 ms 28608 KB Output is correct
28 Correct 530 ms 256000 KB Output is correct
29 Runtime error 1008 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -