oj.uz

Submission #1014568

# Submission time Handle Problem Language Result Execution time Memory
1014568 2024-07-05T07:30:55 Z huutuan Game (IOI13_game) C++14
63 / 100
 791 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;

int sz;
long long t[8010][8010];

long long sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
   if (ly > ry) 
      return 0;
   if (ly == tly && try_ == ry)
      return t[vx][vy];
   int tmy = (tly + try_) >> 1;
   return gcd2(sum_y(vx, vy<<1, tly, tmy, ly, min(ry, tmy)),
      sum_y(vx, vy<<1|1, tmy+1, try_, max(ly, tmy+1), ry));
}

long long sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
   if (lx > rx)
      return 0;
   if (lx == tlx && trx == rx)
      return sum_y(vx, 1, 1, C, ly, ry);
   int tmx = (tlx + trx) >> 1;
   return gcd2(sum_x(vx<<1, tlx, tmx, lx, min(rx, tmx), ly, ry),
      sum_x(vx<<1|1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, long long new_val) {
   if (ly == ry) {
      if (lx == rx)
         t[vx][vy] = new_val;
      else
         t[vx][vy] = gcd2(t[vx<<1][vy], t[vx<<1|1][vy]);
   } else {
      int my = (ly + ry) >> 1;
      if (y <= my)
         update_y(vx, lx, rx, vy<<1, ly, my, x, y, new_val);
      else
         update_y(vx, lx, rx, vy<<1|1, my+1, ry, x, y, new_val);
      t[vx][vy] = gcd2(t[vx][vy<<1], t[vx][vy<<1|1]);
   }
}

void update_x(int vx, int lx, int rx, int x, int y, long long new_val) {
   if (lx != rx) {
      int mx = (lx + rx) >> 1;
      if (x <= mx)
         update_x(vx<<1, lx, mx, x, y, new_val);
      else
         update_x(vx<<1|1, mx+1, rx, x, y, new_val);
   }
   update_y(vx, lx, rx, 1, 1, C, x, y, new_val);
}

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 1 ms 600 KB Output is correct
2 Correct 1 ms 600 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 360 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 444 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 1 ms 604 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 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 288 ms 22700 KB Output is correct
5 Correct 180 ms 22480 KB Output is correct
6 Correct 265 ms 20232 KB Output is correct
7 Correct 296 ms 20052 KB Output is correct
8 Correct 196 ms 14164 KB Output is correct
9 Correct 269 ms 20044 KB Output is correct
10 Correct 263 ms 19648 KB Output is correct
11 Correct 0 ms 600 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 344 KB Output is correct
5 Correct 0 ms 440 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 436 ms 26604 KB Output is correct
13 Correct 675 ms 12696 KB Output is correct
14 Correct 154 ms 5712 KB Output is correct
15 Correct 776 ms 17488 KB Output is correct
16 Correct 123 ms 33616 KB Output is correct
17 Correct 486 ms 23108 KB Output is correct
18 Correct 746 ms 35156 KB Output is correct
19 Correct 650 ms 35416 KB Output is correct
20 Correct 624 ms 34704 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 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 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 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 280 ms 22704 KB Output is correct
13 Correct 187 ms 22352 KB Output is correct
14 Correct 256 ms 20304 KB Output is correct
15 Correct 317 ms 19972 KB Output is correct
16 Correct 239 ms 14196 KB Output is correct
17 Correct 273 ms 20196 KB Output is correct
18 Correct 262 ms 19940 KB Output is correct
19 Correct 466 ms 26456 KB Output is correct
20 Correct 701 ms 12624 KB Output is correct
21 Correct 145 ms 5712 KB Output is correct
22 Correct 770 ms 17264 KB Output is correct
23 Correct 113 ms 33620 KB Output is correct
24 Correct 504 ms 22868 KB Output is correct
25 Correct 763 ms 34132 KB Output is correct
26 Correct 660 ms 34220 KB Output is correct
27 Correct 635 ms 33616 KB Output is correct
28 Runtime error 317 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 448 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 316 ms 21940 KB Output is correct
13 Correct 212 ms 21944 KB Output is correct
14 Correct 286 ms 19500 KB Output is correct
15 Correct 292 ms 19244 KB Output is correct
16 Correct 199 ms 13616 KB Output is correct
17 Correct 282 ms 19460 KB Output is correct
18 Correct 261 ms 19028 KB Output is correct
19 Correct 473 ms 25852 KB Output is correct
20 Correct 655 ms 11864 KB Output is correct
21 Correct 157 ms 4944 KB Output is correct
22 Correct 791 ms 16976 KB Output is correct
23 Correct 119 ms 33104 KB Output is correct
24 Correct 482 ms 22072 KB Output is correct
25 Correct 768 ms 34128 KB Output is correct
26 Correct 689 ms 34384 KB Output is correct
27 Correct 626 ms 33620 KB Output is correct
28 Runtime error 315 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -