oj.uz

Submission #1014609

# Submission time Handle Problem Language Result Execution time Memory
1014609 2024-07-05T07:55:11 Z huutuan Game (IOI13_game) C++14
63 / 100
 1304 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 344 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 424 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 344 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 764 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 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 546 ms 50388 KB Output is correct
5 Correct 459 ms 50520 KB Output is correct
6 Correct 497 ms 47556 KB Output is correct
7 Correct 633 ms 47188 KB Output is correct
8 Correct 445 ms 28904 KB Output is correct
9 Correct 599 ms 47636 KB Output is correct
10 Correct 541 ms 47076 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 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 1 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 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 810 ms 18612 KB Output is correct
13 Correct 981 ms 9028 KB Output is correct
14 Correct 321 ms 1104 KB Output is correct
15 Correct 1304 ms 13492 KB Output is correct
16 Correct 406 ms 23380 KB Output is correct
17 Correct 726 ms 16208 KB Output is correct
18 Correct 1119 ms 23620 KB Output is correct
19 Correct 1060 ms 23800 KB Output is correct
20 Correct 1014 ms 23100 KB Output is correct
21 Correct 0 ms 348 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 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 360 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 2 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 535 ms 50260 KB Output is correct
13 Correct 408 ms 50496 KB Output is correct
14 Correct 585 ms 47604 KB Output is correct
15 Correct 591 ms 47448 KB Output is correct
16 Correct 435 ms 28904 KB Output is correct
17 Correct 533 ms 47440 KB Output is correct
18 Correct 532 ms 46980 KB Output is correct
19 Correct 815 ms 18944 KB Output is correct
20 Correct 1072 ms 8972 KB Output is correct
21 Correct 343 ms 1108 KB Output is correct
22 Correct 1174 ms 13396 KB Output is correct
23 Correct 365 ms 23380 KB Output is correct
24 Correct 759 ms 16212 KB Output is correct
25 Correct 1150 ms 23576 KB Output is correct
26 Correct 1055 ms 23896 KB Output is correct
27 Correct 1044 ms 23076 KB Output is correct
28 Correct 518 ms 256000 KB Output is correct
29 Runtime error 988 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 744 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 50304 KB Output is correct
13 Correct 397 ms 50516 KB Output is correct
14 Correct 478 ms 47444 KB Output is correct
15 Correct 536 ms 47284 KB Output is correct
16 Correct 348 ms 28880 KB Output is correct
17 Correct 570 ms 47444 KB Output is correct
18 Correct 614 ms 46892 KB Output is correct
19 Correct 853 ms 18512 KB Output is correct
20 Correct 1102 ms 8848 KB Output is correct
21 Correct 362 ms 1264 KB Output is correct
22 Correct 1226 ms 13608 KB Output is correct
23 Correct 362 ms 23324 KB Output is correct
24 Correct 839 ms 16280 KB Output is correct
25 Correct 1225 ms 23636 KB Output is correct
26 Correct 1217 ms 24324 KB Output is correct
27 Correct 1068 ms 27572 KB Output is correct
28 Correct 581 ms 256000 KB Output is correct
29 Runtime error 1169 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -