oj.uz

Submission #163265

# Submission time Handle Problem Language Result Execution time Memory
163265 2019-11-12T03:06:40 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6308 ms 256000 KB 
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
 
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < n; i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const ll mod = 998244353;
 
ll madd(ll a, ll b) {
  return (a + b) % mod;
}
ll msub(ll a, ll b) {
  return (((a - b) % mod) + mod) % mod;
}
ll mmul(ll a, ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
ll mpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp % 2 == 1){
        res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}
ll minv(ll base) {
  return mpow(base, mod - 2);
}
ll mdiv(ll a, ll b) {
  return mmul(a, minv(b));
}
ll gcd(ll x, ll y) {
  if (x == 0) return y;
  if (y == 0) return x;
  return gcd(y, x % y);
}
 
// bool prime[1000006]; 
// void sieve(int n) { 
//   f0r(i, n + 1) prime[i] = 1;
//   for (int p = 2; p * p <= n; p++) { 
//     if (prime[p] == true) { 
//       for (int i = p * p; i <= n; i += p) 
//         prime[i] = false; 
//     } 
//   } 
//   prime[1] = prime[0] = 0;
// } 
 
ll n, m, k, q, Q, T, l, r, x, y, z;
// ll a[500005];
// ll b[500005];
string s, t;
ll ans = 0;

using implicit_segtree = struct implicit_segtree;
vector<implicit_segtree> vec(14000000);
int pt = 0;
const int sentinel = 13999999;
struct implicit_segtree {
  bitset<60> v;
  int child[2];

  implicit_segtree() {
    v = 0;
    child[0] = sentinel;
    child[1] = sentinel;
  }

  int ch(int x) {
    if (child[x] == sentinel) {
      child[x] = pt++;
    }
    return child[x];
  }

  void add(int loc, ll val) {
    add(loc, val, 0, m - 1);
  }

  ll add(int loc, ll val, int l, int r) {
    if (l > loc || r < loc) return v.to_ulong();
    if (l == r) return (v = val).to_ulong();
    ll m = (l + r) / 2;
    ll a = 0, b = 0;
    if (loc <= m) {
      a = vec[ch(0)].add(loc, val, l, m);
      if (child[1] != sentinel) b = vec[ch(1)].v.to_ulong();
    } else {
      if (child[0] != sentinel) a = vec[ch(0)].v.to_ulong();
      b = vec[ch(1)].add(loc, val, m + 1, r);
    }
    
    // cout << "add inner " << l << " " << r << " " << a << " " << b << " " << gcd(a, b) << endl;
    return (v = gcd(a, b)).to_ulong();
  }

  ll query(int ql, int qr) {
    return query(ql, qr, 0, m - 1);
  }

  ll query(int ql, int qr, int tl, int tr) {
    if (qr < tl || ql > tr || tl > tr) return 0;
    // cout << "inner " << ql << " " << qr << " " << tl << " " << tr << " " << v.to_ulong() << endl;
    if (ql <= tl && tr <= qr) return v.to_ulong();
    ll a = 0, b = 0;
    ll m = (tl + tr) / 2;
    if (child[0] != sentinel) a = vec[ch(0)].query(ql, qr, tl, m);
    if (child[1] != sentinel) b = vec[ch(1)].query(ql, qr, m + 1, tr);
    // cout << tl << " " << tr << " " << a << " " << b << endl;
    return gcd(a, b);
  }
};

using implicit_segtree_lv2 = struct implicit_segtree_lv2;
struct implicit_segtree_lv2 {
  implicit_segtree* v;
  implicit_segtree_lv2* child[2];

  implicit_segtree_lv2() {
    v = new implicit_segtree();
    child[0] = nullptr;
    child[1] = nullptr;
  }

  implicit_segtree_lv2* ch(int x) {
    if (!child[x]) child[x] = new implicit_segtree_lv2();
    return child[x];
  }

  void add(int loc, int loc2, ll val) {
    add(loc, loc2, val, 0, n - 1);
  }

  ll add(int loc, int loc2, ll val, int l, int r) {
    // cout << "add outer " << l << " " << r << " " << loc2 << " " << val << endl;
    if (l > loc || r < loc) return v->query(loc2, loc2);
    if (l == r) {
      v->add(loc2, val);
      return val;
    }
    ll m = (l + r) / 2;
    ll a = 0, b = 0;
    if (loc <= m) {
      a = ch(0)->add(loc, loc2, val, l, m);
      if (child[1]) b = ch(1)->v->query(loc2, loc2);
    } else {
      if (child[0]) a = ch(0)->v->query(loc2, loc2);
      b = ch(1)->add(loc, loc2, val, m + 1, r);
    }
    
    ll x = gcd(a, b);
    v->add(loc2, x);
    return x;
  }

  ll query(int ql1, int qr1, int ql2, int qr2) {
    return query(ql1, qr1, ql2, qr2, 0, n - 1);
  }

  ll query(int ql1, int qr1, int ql2, int qr2, int tl, int tr) {
    // cout << "outer " << ql1 << " " << qr1 << " " << tl << " " << tr << endl;
    if (qr1 < tl || ql1 > tr || tl > tr) return 0;
    if (ql1 <= tl && tr <= qr1) return v->query(ql2, qr2);
    ll a = 0, b = 0, m = (tl + tr) / 2;
    if (child[0]) a = ch(0)->query(ql1, qr1, ql2, qr2, tl, m);
    if (child[1]) b = ch(1)->query(ql1, qr1, ql2, qr2, m + 1, tr);
    return gcd(a, b);
  }
};

#include "game.h"

implicit_segtree_lv2 st;

void init(int r, int c) {
  n = r;
  m = c;
}

void update(int r, int c, ll v) {
  st.add(r, c, v);
}

ll calculate(int r1, int c1, int r2, int c2) {
  return st.query(r1, r2, c1, c2);
}

// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   usaco("file");

//   cin >> n >> m >> Q;
//   init(n, m);
//   f0r(i, Q) {
//     cin >> q;
//     // cout << "QUERY   __ " << i << " __" << endl;
//     if (q == 1) {
//       ll a, b, c; cin >> a >> b >> c;
//       update(a, b, c);
//     } else {
//       ll a, b, c, d; cin >> a >> b >> c >> d;
//       // cout << "Q " << a << " " << b << " " << c << " " << d << endl;
//       cout << calculate(a, b, c, d) << endl;
//     }
//   }
// }

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'void usaco(std::__cxx11::string)':
game.cpp:54:53: note: #pragma message: be careful, freopen may be wrong
   #pragma message("be careful, freopen may be wrong")
                                                     ^
game.cpp:55:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:56:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 219512 KB Output is correct
2 Correct 186 ms 219540 KB Output is correct
3 Correct 184 ms 219516 KB Output is correct
4 Correct 185 ms 219640 KB Output is correct
5 Correct 183 ms 219544 KB Output is correct
6 Correct 184 ms 219628 KB Output is correct
7 Correct 187 ms 219464 KB Output is correct
8 Correct 186 ms 219460 KB Output is correct
9 Correct 184 ms 219512 KB Output is correct
10 Correct 199 ms 219640 KB Output is correct
11 Correct 184 ms 219508 KB Output is correct
12 Correct 184 ms 219512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 219640 KB Output is correct
2 Correct 186 ms 219512 KB Output is correct
3 Correct 187 ms 219660 KB Output is correct
4 Correct 1022 ms 223792 KB Output is correct
5 Correct 822 ms 224224 KB Output is correct
6 Correct 880 ms 221008 KB Output is correct
7 Correct 939 ms 220548 KB Output is correct
8 Correct 692 ms 221596 KB Output is correct
9 Correct 929 ms 220768 KB Output is correct
10 Correct 897 ms 220372 KB Output is correct
11 Correct 204 ms 219492 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 219684 KB Output is correct
2 Correct 184 ms 219512 KB Output is correct
3 Correct 189 ms 219468 KB Output is correct
4 Correct 190 ms 219640 KB Output is correct
5 Correct 209 ms 219484 KB Output is correct
6 Correct 204 ms 219624 KB Output is correct
7 Correct 186 ms 219540 KB Output is correct
8 Correct 185 ms 219512 KB Output is correct
9 Correct 185 ms 219512 KB Output is correct
10 Correct 206 ms 219572 KB Output is correct
11 Correct 190 ms 219536 KB Output is correct
12 Correct 1639 ms 224212 KB Output is correct
13 Correct 2845 ms 220908 KB Output is correct
14 Correct 544 ms 220284 KB Output is correct
15 Correct 3354 ms 220904 KB Output is correct
16 Correct 456 ms 220888 KB Output is correct
17 Correct 1397 ms 221344 KB Output is correct
18 Correct 2244 ms 221340 KB Output is correct
19 Correct 1885 ms 221420 KB Output is correct
20 Correct 1781 ms 220852 KB Output is correct
21 Correct 193 ms 219616 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 219452 KB Output is correct
2 Correct 207 ms 219640 KB Output is correct
3 Correct 205 ms 219540 KB Output is correct
4 Correct 207 ms 219512 KB Output is correct
5 Correct 206 ms 219648 KB Output is correct
6 Correct 203 ms 219640 KB Output is correct
7 Correct 185 ms 219512 KB Output is correct
8 Correct 188 ms 219648 KB Output is correct
9 Correct 185 ms 219644 KB Output is correct
10 Correct 202 ms 219628 KB Output is correct
11 Correct 189 ms 219516 KB Output is correct
12 Correct 1018 ms 223960 KB Output is correct
13 Correct 813 ms 224224 KB Output is correct
14 Correct 865 ms 220908 KB Output is correct
15 Correct 941 ms 220772 KB Output is correct
16 Correct 676 ms 221424 KB Output is correct
17 Correct 910 ms 220880 KB Output is correct
18 Correct 954 ms 220412 KB Output is correct
19 Correct 1621 ms 224140 KB Output is correct
20 Correct 2947 ms 220736 KB Output is correct
21 Correct 526 ms 220664 KB Output is correct
22 Correct 3248 ms 220880 KB Output is correct
23 Correct 433 ms 220856 KB Output is correct
24 Correct 1426 ms 221560 KB Output is correct
25 Correct 2263 ms 221208 KB Output is correct
26 Correct 1922 ms 221428 KB Output is correct
27 Correct 1789 ms 220888 KB Output is correct
28 Correct 981 ms 231372 KB Output is correct
29 Correct 2413 ms 234716 KB Output is correct
30 Correct 6244 ms 226572 KB Output is correct
31 Correct 5842 ms 225484 KB Output is correct
32 Correct 732 ms 220432 KB Output is correct
33 Correct 995 ms 220512 KB Output is correct
34 Correct 628 ms 231724 KB Output is correct
35 Correct 1880 ms 226996 KB Output is correct
36 Correct 3501 ms 232000 KB Output is correct
37 Correct 2835 ms 232708 KB Output is correct
38 Correct 2670 ms 232100 KB Output is correct
39 Correct 2381 ms 230116 KB Output is correct
40 Correct 185 ms 219512 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 219512 KB Output is correct
2 Correct 185 ms 219532 KB Output is correct
3 Correct 208 ms 219772 KB Output is correct
4 Correct 187 ms 219508 KB Output is correct
5 Correct 191 ms 219656 KB Output is correct
6 Correct 184 ms 219568 KB Output is correct
7 Correct 185 ms 219520 KB Output is correct
8 Correct 187 ms 219540 KB Output is correct
9 Correct 201 ms 219624 KB Output is correct
10 Correct 184 ms 219484 KB Output is correct
11 Correct 187 ms 219520 KB Output is correct
12 Correct 1012 ms 224564 KB Output is correct
13 Correct 790 ms 224776 KB Output is correct
14 Correct 958 ms 221672 KB Output is correct
15 Correct 943 ms 221252 KB Output is correct
16 Correct 682 ms 222096 KB Output is correct
17 Correct 983 ms 221408 KB Output is correct
18 Correct 854 ms 221156 KB Output is correct
19 Correct 1621 ms 224832 KB Output is correct
20 Correct 2933 ms 221512 KB Output is correct
21 Correct 549 ms 221216 KB Output is correct
22 Correct 3264 ms 221576 KB Output is correct
23 Correct 443 ms 221696 KB Output is correct
24 Correct 1399 ms 222188 KB Output is correct
25 Correct 2148 ms 221876 KB Output is correct
26 Correct 1930 ms 222196 KB Output is correct
27 Correct 2029 ms 221372 KB Output is correct
28 Correct 949 ms 232156 KB Output is correct
29 Correct 2396 ms 235056 KB Output is correct
30 Correct 6308 ms 226984 KB Output is correct
31 Correct 5941 ms 225760 KB Output is correct
32 Correct 736 ms 220792 KB Output is correct
33 Correct 1040 ms 221060 KB Output is correct
34 Correct 653 ms 232048 KB Output is correct
35 Correct 2041 ms 227552 KB Output is correct
36 Correct 3290 ms 232568 KB Output is correct
37 Correct 2886 ms 232732 KB Output is correct
38 Correct 2768 ms 232204 KB Output is correct
39 Runtime error 1422 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -