oj.uz

Submission #1014569

# Submission time Handle Problem Language Result Execution time Memory
1014569 2024-07-05T07:32:02 Z huutuan Game (IOI13_game) C++14
63 / 100
 858 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 <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) {
   ++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 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 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 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 298 ms 18408 KB Output is correct
5 Correct 198 ms 18608 KB Output is correct
6 Correct 274 ms 15696 KB Output is correct
7 Correct 321 ms 15440 KB Output is correct
8 Correct 214 ms 10064 KB Output is correct
9 Correct 315 ms 15456 KB Output is correct
10 Correct 313 ms 15096 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 0 ms 348 KB Output is correct
2 Correct 0 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 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 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 485 ms 22612 KB Output is correct
13 Correct 666 ms 8524 KB Output is correct
14 Correct 168 ms 932 KB Output is correct
15 Correct 858 ms 13020 KB Output is correct
16 Correct 119 ms 29524 KB Output is correct
17 Correct 539 ms 18260 KB Output is correct
18 Correct 761 ms 29880 KB Output is correct
19 Correct 749 ms 29904 KB Output is correct
20 Correct 656 ms 29268 KB Output is correct
21 Correct 1 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 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 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 322 ms 18308 KB Output is correct
13 Correct 202 ms 18884 KB Output is correct
14 Correct 276 ms 15696 KB Output is correct
15 Correct 318 ms 15440 KB Output is correct
16 Correct 207 ms 10064 KB Output is correct
17 Correct 311 ms 15448 KB Output is correct
18 Correct 285 ms 15184 KB Output is correct
19 Correct 458 ms 22612 KB Output is correct
20 Correct 705 ms 8592 KB Output is correct
21 Correct 168 ms 976 KB Output is correct
22 Correct 836 ms 13140 KB Output is correct
23 Correct 122 ms 29512 KB Output is correct
24 Correct 538 ms 18316 KB Output is correct
25 Correct 828 ms 30036 KB Output is correct
26 Correct 701 ms 30032 KB Output is correct
27 Correct 628 ms 29268 KB Output is correct
28 Runtime error 334 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 600 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 0 ms 348 KB Output is correct
12 Correct 288 ms 18260 KB Output is correct
13 Correct 177 ms 18704 KB Output is correct
14 Correct 273 ms 15696 KB Output is correct
15 Correct 287 ms 15448 KB Output is correct
16 Correct 230 ms 10052 KB Output is correct
17 Correct 297 ms 15440 KB Output is correct
18 Correct 277 ms 15188 KB Output is correct
19 Correct 495 ms 22492 KB Output is correct
20 Correct 743 ms 8580 KB Output is correct
21 Correct 162 ms 1284 KB Output is correct
22 Correct 783 ms 12880 KB Output is correct
23 Correct 119 ms 29520 KB Output is correct
24 Correct 475 ms 18260 KB Output is correct
25 Correct 755 ms 29676 KB Output is correct
26 Correct 695 ms 29932 KB Output is correct
27 Correct 653 ms 29268 KB Output is correct
28 Runtime error 311 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -