oj.uz

Submission #797504

# Submission time Handle Problem Language Result Execution time Memory
797504 2023-07-29T13:35:20 Z erray Game (IOI13_game) C++17
100 / 100
 2632 ms 114288 KB 
#include "game.h"

#include<bits/stdc++.h>

using namespace std;

template<typename A, typename B> 
string to_string(pair<A, B>);

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return "'"s + c + "'";
}
string to_string(const char* c) {
  return to_string(string(c));
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template<size_t T> 
string to_string(bitset<T> bs) {
  return bs.to_string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < int(v.size()); ++i) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<typename T>
string to_string(T v) {
  string res = "{";
  for (auto x : v) {
    if (int(res.size()) > 1) {
      res += ", ";
    }
    res += to_string(x);
  }
  res += "}";
  return res;  
}
template<typename A, typename B> 
string to_string(pair<A, B> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename H, typename... T> 
void debug_out(H head, T... tail) {
  cerr << "  " << to_string(head);
  debug_out(tail...);
}

#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]", debug_out(__VA_ARGS__)
#else 
  #define debug(...) void(37)
#endif

const int MAX = int(1e9); //temp
//#define debug(...) void(37)
struct GcdSegTree {
  struct node {
    long long g = 0;
    node* l = NULL;
    node* r = NULL;
    int jump = -1;
  };
  void pull(node* v) {
    v->g = 0;
    if (v->l != NULL) {
      v->g = gcd(v->g, v->l->g);
    }
    if (v->r != NULL) {
      v->g = gcd(v->g, v->r->g);
    }
  }
  bool J(node* v) const {
    return (v->l == NULL && v->r == NULL && v->jump != -1);
  }  
  node* root;
  GcdSegTree() {
    root = new node();
  }
  node* modify(node* v, int l, int r, int p, long long g) {
    debug(l, r, p, g);
    if (v == NULL || (J(v) && p == v->jump)) {
      v = new node();
      v->g = g;
      v->jump = p;
      debug("created");
      return v;
    } 
    if (l == r) {
      v->g = g;
      return v;
    }
    bool branch = J(v);       
    int mid = (l + r) >> 1;
    if (p <= mid) {
      v->l = modify(v->l, l, mid, p, g);
    } else {
      v->r = modify(v->r, mid + 1, r, p, g);
    }
    //assert(!J(v));
    if (branch) {
      debug("branch");
      modify(v, l, r, v->jump, v->g);
    } else {
      pull(v);
    }
    debug(l, r, v->g);
    return v;
  }
  long long get(node* v, int l, int r, int ll, int rr) const {
    if (J(v)) {
      l = r = v->jump;
    }
    debug(l, r, ll, rr, v->g);
    if (l >= ll && rr >= r) {
      return v->g;
    }
    int mid = (l + r) >> 1;
    long long res = 0;
    if (mid >= ll && v->l != NULL) {
      res = gcd(res, get(v->l, l, mid, ll, rr));
    }
    if (mid < rr && v->r != NULL) {
      res = gcd(res, get(v->r, mid + 1, r, ll, rr));
    }
    return res;
  }
  long long get(int l, int r) const {
    return get(root, 0, MAX - 1, l, r);
  }
  void modify(int p, long long x) {
    //debug(p, x);
    modify(root, 0, MAX - 1, p, x);
  }
};
#ifdef DEBUG 
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]", debug_out(__VA_ARGS__)
#else 
  #define debug(...) void(37)
#endif

struct TwoDSegTree {
  struct node {
    GcdSegTree st;
    node* l = NULL;
    node* r = NULL;
  };
  //add jump to this too if it gets tle or some shit 
  node* root;
  map<int, GcdSegTree> cols;  
  TwoDSegTree() {
    root = new node();
  }
  long long get(node* v, int l, int r, int rl, int rr, int cl, int cr) {
    debug(l, r, rl, rr, cl, cr);
    if (l >= rl && rr >= r) {
      return v->st.get(cl, cr);
    }
    int mid = (l + r) >> 1;
    long long res = 0;
    if (mid >= rl && v->l != NULL) {
      res = gcd(res, get(v->l, l, mid, rl, rr, cl, cr));
    }
    if (mid < rr && v->r != NULL) {
      res = gcd(res, get(v->r, mid + 1, r, rl, rr, cl, cr));
    }
    return res;
  }  
  node* modify(node* v, int l, int r, int row, int col, const GcdSegTree& carry) {
    if (v == NULL) {
      v = new node();
    }
    long long upd = carry.get(l, r);
    debug("2D", l, r, upd);    
    v->st.modify(col, upd);
    if (l < r) {
      int mid = (l + r) >> 1;
      if (row <= mid) {
        v->l = modify(v->l, l, mid, row, col, carry);
      } else {
        v->r = modify(v->r, mid + 1, r, row, col, carry);
      }
    }
    return v;
  }
  long long get(int rl, int rr, int cl, int cr) {
    return get(root, 0, MAX - 1, rl, rr, cl, cr);
  } 
  void modify(int row, int col, long long x) {
    cols[col].modify(row, x);
    modify(root, 0, MAX - 1, row, col, cols[col]);
  }
};

TwoDSegTree st;
void init(int R, int C) {
  
}

void update(int P, int Q, long long K) {
  debug("asdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasd", P, Q, K);
  st.modify(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st.get(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 473 ms 43716 KB Output is correct
5 Correct 349 ms 43468 KB Output is correct
6 Correct 506 ms 41008 KB Output is correct
7 Correct 527 ms 40744 KB Output is correct
8 Correct 357 ms 23300 KB Output is correct
9 Correct 526 ms 40308 KB Output is correct
10 Correct 488 ms 40340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 735 ms 32424 KB Output is correct
13 Correct 1069 ms 27112 KB Output is correct
14 Correct 349 ms 20952 KB Output is correct
15 Correct 1157 ms 30604 KB Output is correct
16 Correct 319 ms 33708 KB Output is correct
17 Correct 749 ms 22956 KB Output is correct
18 Correct 1309 ms 35264 KB Output is correct
19 Correct 1130 ms 35300 KB Output is correct
20 Correct 1039 ms 34784 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 463 ms 43524 KB Output is correct
13 Correct 355 ms 43468 KB Output is correct
14 Correct 513 ms 40988 KB Output is correct
15 Correct 544 ms 40716 KB Output is correct
16 Correct 342 ms 23356 KB Output is correct
17 Correct 540 ms 40348 KB Output is correct
18 Correct 484 ms 40336 KB Output is correct
19 Correct 736 ms 32496 KB Output is correct
20 Correct 1031 ms 27056 KB Output is correct
21 Correct 335 ms 20872 KB Output is correct
22 Correct 1161 ms 30640 KB Output is correct
23 Correct 330 ms 33772 KB Output is correct
24 Correct 706 ms 22840 KB Output is correct
25 Correct 1275 ms 35172 KB Output is correct
26 Correct 1108 ms 35240 KB Output is correct
27 Correct 1037 ms 34744 KB Output is correct
28 Correct 332 ms 57460 KB Output is correct
29 Correct 861 ms 52796 KB Output is correct
30 Correct 2095 ms 50516 KB Output is correct
31 Correct 1897 ms 43704 KB Output is correct
32 Correct 394 ms 25540 KB Output is correct
33 Correct 455 ms 28980 KB Output is correct
34 Correct 177 ms 46272 KB Output is correct
35 Correct 574 ms 30444 KB Output is correct
36 Correct 1102 ms 50464 KB Output is correct
37 Correct 856 ms 50708 KB Output is correct
38 Correct 846 ms 50140 KB Output is correct
39 Correct 774 ms 41092 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 478 ms 43544 KB Output is correct
13 Correct 354 ms 43592 KB Output is correct
14 Correct 490 ms 41028 KB Output is correct
15 Correct 551 ms 40664 KB Output is correct
16 Correct 351 ms 23328 KB Output is correct
17 Correct 512 ms 40396 KB Output is correct
18 Correct 498 ms 40344 KB Output is correct
19 Correct 748 ms 32508 KB Output is correct
20 Correct 1038 ms 27128 KB Output is correct
21 Correct 342 ms 20876 KB Output is correct
22 Correct 1170 ms 30708 KB Output is correct
23 Correct 362 ms 33768 KB Output is correct
24 Correct 816 ms 22936 KB Output is correct
25 Correct 1283 ms 35080 KB Output is correct
26 Correct 1153 ms 35296 KB Output is correct
27 Correct 1261 ms 34764 KB Output is correct
28 Correct 422 ms 57448 KB Output is correct
29 Correct 977 ms 52616 KB Output is correct
30 Correct 2237 ms 50476 KB Output is correct
31 Correct 2037 ms 43760 KB Output is correct
32 Correct 349 ms 25604 KB Output is correct
33 Correct 495 ms 28932 KB Output is correct
34 Correct 195 ms 46264 KB Output is correct
35 Correct 677 ms 30404 KB Output is correct
36 Correct 1536 ms 50444 KB Output is correct
37 Correct 1085 ms 50712 KB Output is correct
38 Correct 1092 ms 50228 KB Output is correct
39 Correct 565 ms 114288 KB Output is correct
40 Correct 1417 ms 97892 KB Output is correct
41 Correct 2632 ms 101488 KB Output is correct
42 Correct 2465 ms 86420 KB Output is correct
43 Correct 324 ms 92700 KB Output is correct
44 Correct 476 ms 43972 KB Output is correct
45 Correct 815 ms 41188 KB Output is correct
46 Correct 1713 ms 96892 KB Output is correct
47 Correct 1668 ms 97000 KB Output is correct
48 Correct 1604 ms 96404 KB Output is correct
49 Correct 1 ms 340 KB Output is correct