oj.uz

Submission #1014562

# Submission time Handle Problem Language Result Execution time Memory
1014562 2024-07-05T07:02:28 Z huutuan Game (IOI13_game) C++14
10 / 100
 709 ms 226904 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;

struct Node{
   long long val;
   Node *l;
   Node *r;
   Node (){
      val=0;
      l=nullptr;
      r=nullptr;
   }
};

struct SegmentTree{
   Node *root;
   SegmentTree(){
      root=new Node();
   }
   void update(Node *t, int l, int r, int pos, long long val){
      if (l==r){
         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, l, mid, pos, val);
      else update(t->r, mid+1, r, pos, val);
      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));
   }
};

int sz;
SegmentTree st[2000000];
map<int, int> mp;
long long t[2010][2010];
int R, C;

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;
   if (R<=2000 && C<=2000){
      update_x(1, 1, R, P, Q, K);
      return;
   }
   if (!mp.count(P)){
      mp[P]=sz++;
   }
   int id=mp[P];
   st[id].update(st[id].root, 1, 1e9, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
   ++P; ++Q; ++U; ++V;
   if (R<=2000 && Q<=2000) return sum_x(1, 1, R, P, U, Q, V);
   long long ans=0;
   for (auto it=mp.lower_bound(P); it!=mp.end(); ++it){
      if (it->first>U) continue;
      ans=gcd2(ans, st[it->second].get(st[it->second].root, 1, 1e9, Q, V));
   }
   return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 78672 KB Output is correct
2 Correct 58 ms 79428 KB Output is correct
3 Correct 57 ms 79440 KB Output is correct
4 Correct 57 ms 78676 KB Output is correct
5 Correct 56 ms 78676 KB Output is correct
6 Correct 56 ms 79452 KB Output is correct
7 Correct 56 ms 78676 KB Output is correct
8 Correct 58 ms 78676 KB Output is correct
9 Correct 73 ms 79384 KB Output is correct
10 Correct 58 ms 79048 KB Output is correct
11 Correct 57 ms 78676 KB Output is correct
12 Correct 57 ms 78592 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 78676 KB Output is correct
2 Correct 60 ms 78676 KB Output is correct
3 Correct 56 ms 78676 KB Output is correct
4 Incorrect 511 ms 90448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 78672 KB Output is correct
2 Correct 59 ms 79444 KB Output is correct
3 Correct 57 ms 79340 KB Output is correct
4 Correct 55 ms 78696 KB Output is correct
5 Correct 51 ms 78676 KB Output is correct
6 Correct 53 ms 79444 KB Output is correct
7 Correct 56 ms 78676 KB Output is correct
8 Correct 52 ms 78676 KB Output is correct
9 Correct 48 ms 79440 KB Output is correct
10 Correct 49 ms 79164 KB Output is correct
11 Correct 53 ms 78768 KB Output is correct
12 Runtime error 709 ms 226904 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 78672 KB Output is correct
2 Correct 57 ms 79444 KB Output is correct
3 Correct 61 ms 79340 KB Output is correct
4 Correct 56 ms 78672 KB Output is correct
5 Correct 55 ms 78672 KB Output is correct
6 Correct 56 ms 79440 KB Output is correct
7 Correct 65 ms 78560 KB Output is correct
8 Correct 58 ms 78676 KB Output is correct
9 Correct 56 ms 79368 KB Output is correct
10 Correct 57 ms 78988 KB Output is correct
11 Correct 54 ms 78676 KB Output is correct
12 Incorrect 562 ms 90448 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 78560 KB Output is correct
2 Correct 54 ms 79444 KB Output is correct
3 Correct 60 ms 79424 KB Output is correct
4 Correct 65 ms 78660 KB Output is correct
5 Correct 56 ms 78676 KB Output is correct
6 Correct 55 ms 79440 KB Output is correct
7 Correct 56 ms 78668 KB Output is correct
8 Correct 57 ms 78672 KB Output is correct
9 Correct 58 ms 79440 KB Output is correct
10 Correct 57 ms 79188 KB Output is correct
11 Correct 58 ms 78676 KB Output is correct
12 Incorrect 543 ms 90328 KB Output isn't correct
13 Halted 0 ms 0 KB -