Submission #593059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593059	2022-07-10T10:14:44 Z	MilosMilutinovic	Game (IOI13_game)	C++14	100 / 100	2630 ms	73184 KB

game

/**
 *    author:  wxhtzdy
 *    created: 10.07.2022 09:47:45
**/

// learning 2d segment tree of treaps from USACO Guide

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(time(0));

struct TreapNode {
  TreapNode *l, *r;
  int pos, key, mn, mx;
  long long val, g;

  TreapNode(int position, long long value) {
    l = r = nullptr;
    mn = mx = pos = position;
    key = rng();
    val = g = value;
  }

  void update() {
    g = val;
    if (l) g = __gcd(g, l->g);
    if (r) g = __gcd(g, r->g);
    mn = (l ? l->mn : pos);
    mx = (r ? r->mx : pos);
  }
};

struct Treap {
  TreapNode *root;

  Treap() {
    root = nullptr;
  }
  
  void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
    if (t == nullptr) {
      l = r = nullptr;
      return;
    }       
    if (t->pos < pos) {
      split(t->r, pos, l, r);
      t->r = l;
      l = t;
    } else {
      split(t->l, pos, l, r);
      t->l = r;
      r = t;
    }
    t->update();
  }

  TreapNode* merge(TreapNode *l, TreapNode *r) {
    if (!l) return r;
    if (!r) return l;
    if (l->key < r->key) {
      l->r = merge(l->r, r);
      l->update();
      return l;
    } else {
      r->l = merge(l, r->l);
      r->update();
      return r;
    }
  }

  bool find(int pos) {
    TreapNode *t = root;
    while (t) {
      if (t->pos == pos) return true;
      if (t->pos > pos) t = t->l;
      else t = t->r;
    }
    return false;
  }

  void update(TreapNode *t, int pos, long long value) {
    if (t->pos == pos) {
      t->val = value;
      t->update();
      return;
    }

    if (t->pos > pos) {
      update(t->l, pos, value);
    } else {
      update(t->r, pos, value);
    }
    t->update();
  }

  void insert(int pos, long long value) {
    if (find(pos)) {
      update(root, pos, value);
      return;
    }
    TreapNode *l, *r;
    split(root, pos, l, r);
    root = merge(merge(l, new TreapNode(pos, value)), r);
  }
  
  long long query(TreapNode *t, int l, int r) {
    if (t->mx < l || t->mn > r) return 0LL;
    if (l <= t->mn && t->mx <= r) return t->g;
    long long res = 0;
    if (l <= t->pos && t->pos <= r) {
      res = t->val;
    }
    if (t->l) res = __gcd(res, query(t->l, l, r));
    if (t->r) res = __gcd(res, query(t->r, l, r));
    return res;
  }   

  long long query(int l, int r) {
    if (!root) return 0LL;
    return query(root, l, r);
  }
};

struct Segtree {
  Segtree *l, *r;
  Treap treap;
  int lo, hi;

  Segtree () { l = r = nullptr; }
  Segtree(int st, int en) {
    l = r = nullptr;
    lo = st;
    hi = en;
  }

  void new_left() {
    if (!l) {
      l = new Segtree(lo, (lo + hi) / 2);
    }
  }
  void new_right() {
    if (!r) {
      r = new Segtree((lo + hi) / 2 + 1, hi);
    }
  }

  void fix(int pos) {
    long long val = 0;
    if (l) val = __gcd(val, l->treap.query(pos, pos));
    if (r) val = __gcd(val, r->treap.query(pos, pos)); 
    treap.insert(pos, val);
  }

  void update(int x, int y, long long val) {
    if (hi < x || lo > x) return;
    if (lo == hi) {
      treap.insert(y, val);
      return;
    }
    int mid = (lo + hi) / 2;
    if (x <= mid) {
      new_left();
      l->update(x, y, val);
    } else {
      new_right();
      r->update(x, y, val);
    }
    fix(y);
  }
   
  long long query(int t, int b, int st, int en) {
    if (hi < t || lo > b) return 0LL;
    if (t <= lo && hi <= b) return treap.query(st, en);
    long long ans = 0;
    if (l) ans = __gcd(ans, l->query(t, b, st, en));
    if (r) ans = __gcd(ans, r->query(t, b, st, en));
    return ans;
  }
};

Segtree segtree;

void init(int R, int C) {
  segtree = Segtree(0, R - 1);
}

void update(int P, int Q, long long K) {
  segtree.update(P, Q, K);
}

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

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	312 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	316 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	464 ms	7128 KB	Output is correct
5	Correct	227 ms	11212 KB	Output is correct
6	Correct	481 ms	8696 KB	Output is correct
7	Correct	550 ms	8380 KB	Output is correct
8	Correct	328 ms	7344 KB	Output is correct
9	Correct	513 ms	8484 KB	Output is correct
10	Correct	481 ms	8140 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	296 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	606 ms	9376 KB	Output is correct
13	Correct	1058 ms	7796 KB	Output is correct
14	Correct	203 ms	5608 KB	Output is correct
15	Correct	1104 ms	9204 KB	Output is correct
16	Correct	231 ms	11388 KB	Output is correct
17	Correct	674 ms	9648 KB	Output is correct
18	Correct	1145 ms	12944 KB	Output is correct
19	Correct	1016 ms	12896 KB	Output is correct
20	Correct	946 ms	12576 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	304 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	431 ms	11324 KB	Output is correct
13	Correct	235 ms	11340 KB	Output is correct
14	Correct	480 ms	8672 KB	Output is correct
15	Correct	562 ms	8348 KB	Output is correct
16	Correct	340 ms	7432 KB	Output is correct
17	Correct	518 ms	8596 KB	Output is correct
18	Correct	472 ms	8068 KB	Output is correct
19	Correct	635 ms	13400 KB	Output is correct
20	Correct	1044 ms	7656 KB	Output is correct
21	Correct	232 ms	5588 KB	Output is correct
22	Correct	1064 ms	9152 KB	Output is correct
23	Correct	243 ms	11392 KB	Output is correct
24	Correct	705 ms	9768 KB	Output is correct
25	Correct	1185 ms	12864 KB	Output is correct
26	Correct	1020 ms	13180 KB	Output is correct
27	Correct	955 ms	12424 KB	Output is correct
28	Correct	389 ms	39096 KB	Output is correct
29	Correct	1083 ms	41692 KB	Output is correct
30	Correct	1275 ms	29844 KB	Output is correct
31	Correct	1143 ms	24656 KB	Output is correct
32	Correct	276 ms	10188 KB	Output is correct
33	Correct	406 ms	10476 KB	Output is correct
34	Correct	334 ms	35432 KB	Output is correct
35	Correct	893 ms	25272 KB	Output is correct
36	Correct	1784 ms	39844 KB	Output is correct
37	Correct	1382 ms	39820 KB	Output is correct
38	Correct	1387 ms	39316 KB	Output is correct
39	Correct	1142 ms	32952 KB	Output is correct
40	Correct	0 ms	304 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	300 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	276 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	304 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	457 ms	11352 KB	Output is correct
13	Correct	225 ms	11160 KB	Output is correct
14	Correct	482 ms	8636 KB	Output is correct
15	Correct	534 ms	8440 KB	Output is correct
16	Correct	330 ms	7444 KB	Output is correct
17	Correct	520 ms	8568 KB	Output is correct
18	Correct	484 ms	8096 KB	Output is correct
19	Correct	614 ms	13364 KB	Output is correct
20	Correct	1061 ms	7860 KB	Output is correct
21	Correct	200 ms	5484 KB	Output is correct
22	Correct	1069 ms	8980 KB	Output is correct
23	Correct	231 ms	11344 KB	Output is correct
24	Correct	677 ms	9724 KB	Output is correct
25	Correct	1194 ms	12900 KB	Output is correct
26	Correct	1035 ms	13080 KB	Output is correct
27	Correct	956 ms	12460 KB	Output is correct
28	Correct	396 ms	38988 KB	Output is correct
29	Correct	1101 ms	41696 KB	Output is correct
30	Correct	1309 ms	29804 KB	Output is correct
31	Correct	1161 ms	24520 KB	Output is correct
32	Correct	273 ms	10136 KB	Output is correct
33	Correct	398 ms	10640 KB	Output is correct
34	Correct	314 ms	35400 KB	Output is correct
35	Correct	866 ms	25188 KB	Output is correct
36	Correct	1768 ms	39708 KB	Output is correct
37	Correct	1389 ms	39792 KB	Output is correct
38	Correct	1398 ms	39272 KB	Output is correct
39	Correct	581 ms	71312 KB	Output is correct
40	Correct	1994 ms	73184 KB	Output is correct
41	Correct	2081 ms	55220 KB	Output is correct
42	Correct	1901 ms	43480 KB	Output is correct
43	Correct	684 ms	68048 KB	Output is correct
44	Correct	388 ms	10700 KB	Output is correct
45	Correct	1182 ms	32988 KB	Output is correct
46	Correct	2585 ms	72164 KB	Output is correct
47	Correct	2630 ms	71984 KB	Output is correct
48	Correct	2565 ms	71696 KB	Output is correct
49	Correct	0 ms	212 KB	Output is correct