oj.uz

Submission #437283

# Submission time Handle Problem Language Result Execution time Memory
437283 2021-06-26T06:43:07 Z Mackerel_Pike Game (IOI13_game) C++14
0 / 100
 2 ms 588 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

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;
}

class SegmentTree{
public:
  static const int maxv = 1e6 + 5;
  static const int maxv2 = 5e6 + 5;
  static const int siz = 1000000000;
  int tot, tot2, r;
  int ls[maxv], rs[maxv], rt[maxv];
  int ls2[maxv2], rs2[maxv2];
  ll dat[maxv2];
  inline void init(){ r = 0, tot = tot2 = 1; return; }
  inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot2++, dat[u] = 0;
    //printf("update2 u = %d l = %d r = %d\n", u, l, r);
    if(l == r){
      dat[u] = k;
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      update2(q, k, ls2[u], l, md);
    else
      update2(q, k, rs2[u], md + 1, r);
    dat[u] = gcd2(dat[ls2[u]], dat[rs2[u]]);
    return;
  }

  inline void pushUp(int q, int &v, int vl, int vr, int l = 0, int r = siz - 1){
    if(!vl && !vr)
      return;
    if(!v)
      v = tot++, dat[v] = 0;
    if(l == r){
      dat[v] = gcd2(dat[vl], dat[vr]);
      return;
    }
    int md = l + r >> 1;
    if(q <= md)
      pushUp(q, ls2[v], ls2[vl], ls2[vr], l, md);
    else
      pushUp(q, rs2[v], rs2[vl], rs2[vr], md + 1, r);
    dat[v] = gcd2(dat[ls2[v]], dat[rs2[v]]);
    return;
  }
  
  inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
    if(!u)
      u = tot++;
    //printf("update u = %d rt = %d\n", u, rt[u]);
    if(l == r){
      update2(q, k, rt[u]);
      return;
    }
    int md = l + r >> 1;
    if(p <= md)
      update(p, q, k, ls[u], l, md);
    else
      update(p, q, k, rs[u], md + 1, r);
    pushUp(q, rt[u], rt[ls[u]], rt[rs[u]]);
    return;
  }

  inline ll query2(int s, int t, int u, int l = 0, int r = siz - 1){
    //printf("query2 u = %d\n", u);
    if(!u){
      return 0;
    }
    if(l >= s && r <= t){
      return dat[u];
    }
    int md = l + r >> 1;
    if(s > md)
      return query2(s, t, rs2[u], md + 1, r);
    if(t <= md)
      return query2(s, t, ls2[u], l, md);
    return gcd2(query2(s, t, ls2[u], l, md), query2(s, t, rs2[u], md + 1, r));
  }

  inline ll query(int p, int q, int s, int t, int u, int l = 0, int r = siz - 1){
    if(!u)
      return 0;
    if(l >= p && r <= q)
      return query2(s, t, rt[u]);
    int md = l + r >> 1;
    if(p > md)
      return query(p, q, s, t, rs[u], md + 1, r);
    if(q <= md)
      return query(p, q, s, t, ls[u], l, md);
    return gcd2(query(p, q, s, t, rs[u], md + 1, r), query(p, q, s, t, ls[u], l, md));
  }
} seg;

void init(int R, int C) {
  seg.init();
}

void update(int P, int Q, long long K) {
  seg.update(P, Q, K, seg.r);
  return;
}

long long calculate(int P, int Q, int U, int V) {
  return seg.query(P, U, Q, V, seg.r);
}

Compilation message

game.cpp: In member function 'void SegmentTree::update2(int, ll, int&, int, int)':
game.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::pushUp(int, int&, int, int, int, int)':
game.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'void SegmentTree::update(int, int, ll, int&, int, int)':
game.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query2(int, int, int, int, int)':
game.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int md = l + r >> 1;
      |              ~~^~~
game.cpp: In member function 'll SegmentTree::query(int, int, int, int, int, int, int)':
game.cpp:99:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int md = l + r >> 1;
      |              ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -