oj.uz

Submission #1014564

# Submission time Handle Problem Language Result Execution time Memory
1014564 2024-07-05T07:04:39 Z huutuan Game (IOI13_game) C++14
63 / 100
 13000 ms 212052 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[8010][8010];
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 && C<=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 55 ms 78592 KB Output is correct
2 Correct 56 ms 79408 KB Output is correct
3 Correct 56 ms 79440 KB Output is correct
4 Correct 55 ms 78672 KB Output is correct
5 Correct 61 ms 78692 KB Output is correct
6 Correct 61 ms 79576 KB Output is correct
7 Correct 55 ms 78672 KB Output is correct
8 Correct 55 ms 78608 KB Output is correct
9 Correct 58 ms 79436 KB Output is correct
10 Correct 64 ms 79184 KB Output is correct
11 Correct 66 ms 78800 KB Output is correct
12 Correct 56 ms 78688 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 78676 KB Output is correct
2 Correct 52 ms 78684 KB Output is correct
3 Correct 63 ms 78564 KB Output is correct
4 Correct 562 ms 89344 KB Output is correct
5 Correct 359 ms 90960 KB Output is correct
6 Correct 419 ms 88656 KB Output is correct
7 Correct 462 ms 88400 KB Output is correct
8 Correct 381 ms 86864 KB Output is correct
9 Correct 468 ms 88400 KB Output is correct
10 Correct 421 ms 87932 KB Output is correct
11 Correct 52 ms 78672 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 78676 KB Output is correct
2 Correct 58 ms 79696 KB Output is correct
3 Correct 52 ms 79440 KB Output is correct
4 Correct 53 ms 78592 KB Output is correct
5 Correct 51 ms 78672 KB Output is correct
6 Correct 50 ms 79440 KB Output is correct
7 Correct 59 ms 78672 KB Output is correct
8 Correct 52 ms 78672 KB Output is correct
9 Correct 56 ms 79444 KB Output is correct
10 Correct 51 ms 79188 KB Output is correct
11 Correct 51 ms 78672 KB Output is correct
12 Correct 666 ms 123972 KB Output is correct
13 Correct 832 ms 116048 KB Output is correct
14 Correct 531 ms 84820 KB Output is correct
15 Correct 1043 ms 164608 KB Output is correct
16 Correct 212 ms 208840 KB Output is correct
17 Correct 867 ms 190328 KB Output is correct
18 Correct 1055 ms 209752 KB Output is correct
19 Correct 952 ms 209588 KB Output is correct
20 Correct 904 ms 208808 KB Output is correct
21 Correct 51 ms 78672 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78680 KB Output is correct
2 Correct 54 ms 79368 KB Output is correct
3 Correct 57 ms 79572 KB Output is correct
4 Correct 60 ms 78676 KB Output is correct
5 Correct 55 ms 78672 KB Output is correct
6 Correct 56 ms 79596 KB Output is correct
7 Correct 56 ms 78700 KB Output is correct
8 Correct 56 ms 78632 KB Output is correct
9 Correct 57 ms 79440 KB Output is correct
10 Correct 64 ms 79168 KB Output is correct
11 Correct 60 ms 78848 KB Output is correct
12 Correct 573 ms 89168 KB Output is correct
13 Correct 306 ms 90964 KB Output is correct
14 Correct 417 ms 88472 KB Output is correct
15 Correct 442 ms 88224 KB Output is correct
16 Correct 381 ms 86720 KB Output is correct
17 Correct 440 ms 88400 KB Output is correct
18 Correct 406 ms 87912 KB Output is correct
19 Correct 690 ms 125776 KB Output is correct
20 Correct 828 ms 117584 KB Output is correct
21 Correct 458 ms 86876 KB Output is correct
22 Correct 1070 ms 166480 KB Output is correct
23 Correct 208 ms 210588 KB Output is correct
24 Correct 811 ms 192656 KB Output is correct
25 Correct 964 ms 211888 KB Output is correct
26 Correct 949 ms 211832 KB Output is correct
27 Correct 884 ms 211436 KB Output is correct
28 Execution timed out 13035 ms 108660 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 78672 KB Output is correct
2 Correct 54 ms 79444 KB Output is correct
3 Correct 53 ms 79524 KB Output is correct
4 Correct 55 ms 78676 KB Output is correct
5 Correct 59 ms 78544 KB Output is correct
6 Correct 53 ms 79592 KB Output is correct
7 Correct 53 ms 78676 KB Output is correct
8 Correct 53 ms 78736 KB Output is correct
9 Correct 53 ms 79440 KB Output is correct
10 Correct 53 ms 79184 KB Output is correct
11 Correct 60 ms 78672 KB Output is correct
12 Correct 566 ms 90444 KB Output is correct
13 Correct 346 ms 90888 KB Output is correct
14 Correct 453 ms 88692 KB Output is correct
15 Correct 495 ms 88400 KB Output is correct
16 Correct 372 ms 86868 KB Output is correct
17 Correct 488 ms 88400 KB Output is correct
18 Correct 441 ms 87892 KB Output is correct
19 Correct 682 ms 125856 KB Output is correct
20 Correct 873 ms 117588 KB Output is correct
21 Correct 493 ms 86596 KB Output is correct
22 Correct 1054 ms 167036 KB Output is correct
23 Correct 201 ms 210512 KB Output is correct
24 Correct 866 ms 192480 KB Output is correct
25 Correct 971 ms 212016 KB Output is correct
26 Correct 963 ms 212052 KB Output is correct
27 Correct 895 ms 211280 KB Output is correct
28 Execution timed out 13030 ms 108708 KB Time limit exceeded
29 Halted 0 ms 0 KB -