oj.uz

Submission #163269

# Submission time Handle Problem Language Result Execution time Memory
163269 2019-11-12T04:12:50 Z galen_colin Game (IOI13_game) C++14
63 / 100
 3300 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;
implicit_segtree* vec;
int pt = 0;
const int sentinel = 20000000;
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++;
      // vec[pt++] = implicit_segtree();
    }
    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;
  vec = new implicit_segtree[16000000];
}

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 226 ms 250788 KB Output is correct
2 Correct 227 ms 250828 KB Output is correct
3 Correct 222 ms 250888 KB Output is correct
4 Correct 214 ms 250872 KB Output is correct
5 Correct 220 ms 250848 KB Output is correct
6 Correct 217 ms 250872 KB Output is correct
7 Correct 215 ms 250776 KB Output is correct
8 Correct 214 ms 250916 KB Output is correct
9 Correct 216 ms 250880 KB Output is correct
10 Correct 217 ms 250876 KB Output is correct
11 Correct 226 ms 250928 KB Output is correct
12 Correct 213 ms 250772 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 250868 KB Output is correct
2 Correct 226 ms 250912 KB Output is correct
3 Correct 226 ms 250872 KB Output is correct
4 Correct 1047 ms 256000 KB Output is correct
5 Correct 833 ms 256000 KB Output is correct
6 Correct 910 ms 253660 KB Output is correct
7 Correct 966 ms 253208 KB Output is correct
8 Correct 697 ms 254088 KB Output is correct
9 Correct 977 ms 253432 KB Output is correct
10 Correct 867 ms 253036 KB Output is correct
11 Correct 212 ms 250872 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 250852 KB Output is correct
2 Correct 221 ms 250884 KB Output is correct
3 Correct 214 ms 250872 KB Output is correct
4 Correct 224 ms 250832 KB Output is correct
5 Correct 215 ms 250768 KB Output is correct
6 Correct 221 ms 250940 KB Output is correct
7 Correct 215 ms 250872 KB Output is correct
8 Correct 222 ms 250872 KB Output is correct
9 Correct 214 ms 250872 KB Output is correct
10 Correct 217 ms 250872 KB Output is correct
11 Correct 217 ms 250844 KB Output is correct
12 Correct 1724 ms 256000 KB Output is correct
13 Correct 2866 ms 253228 KB Output is correct
14 Correct 560 ms 252996 KB Output is correct
15 Correct 3296 ms 253816 KB Output is correct
16 Correct 463 ms 253516 KB Output is correct
17 Correct 1611 ms 254316 KB Output is correct
18 Correct 2211 ms 254288 KB Output is correct
19 Correct 1900 ms 253928 KB Output is correct
20 Correct 1807 ms 253372 KB Output is correct
21 Correct 396 ms 250872 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 250800 KB Output is correct
2 Correct 226 ms 250844 KB Output is correct
3 Correct 229 ms 250872 KB Output is correct
4 Correct 233 ms 250872 KB Output is correct
5 Correct 213 ms 250840 KB Output is correct
6 Correct 215 ms 250872 KB Output is correct
7 Correct 224 ms 250988 KB Output is correct
8 Correct 221 ms 250872 KB Output is correct
9 Correct 221 ms 250848 KB Output is correct
10 Correct 216 ms 250908 KB Output is correct
11 Correct 217 ms 250812 KB Output is correct
12 Correct 1049 ms 256000 KB Output is correct
13 Correct 820 ms 256000 KB Output is correct
14 Correct 927 ms 253632 KB Output is correct
15 Correct 987 ms 253332 KB Output is correct
16 Correct 793 ms 254104 KB Output is correct
17 Correct 949 ms 253380 KB Output is correct
18 Correct 900 ms 253048 KB Output is correct
19 Correct 1641 ms 256000 KB Output is correct
20 Correct 2871 ms 253420 KB Output is correct
21 Correct 559 ms 253028 KB Output is correct
22 Correct 3300 ms 253740 KB Output is correct
23 Correct 464 ms 253944 KB Output is correct
24 Correct 1470 ms 254172 KB Output is correct
25 Correct 2165 ms 254332 KB Output is correct
26 Correct 1920 ms 254056 KB Output is correct
27 Correct 1759 ms 253108 KB Output is correct
28 Runtime error 468 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 250804 KB Output is correct
2 Correct 216 ms 250972 KB Output is correct
3 Correct 216 ms 250880 KB Output is correct
4 Correct 217 ms 250844 KB Output is correct
5 Correct 214 ms 250844 KB Output is correct
6 Correct 213 ms 250872 KB Output is correct
7 Correct 224 ms 250872 KB Output is correct
8 Correct 215 ms 250876 KB Output is correct
9 Correct 213 ms 250872 KB Output is correct
10 Correct 215 ms 250848 KB Output is correct
11 Correct 217 ms 250872 KB Output is correct
12 Correct 1046 ms 256000 KB Output is correct
13 Correct 832 ms 256000 KB Output is correct
14 Correct 897 ms 253060 KB Output is correct
15 Correct 978 ms 252788 KB Output is correct
16 Correct 824 ms 253676 KB Output is correct
17 Correct 948 ms 252828 KB Output is correct
18 Correct 918 ms 252488 KB Output is correct
19 Correct 1635 ms 256000 KB Output is correct
20 Correct 2882 ms 252688 KB Output is correct
21 Correct 555 ms 252516 KB Output is correct
22 Correct 3290 ms 252776 KB Output is correct
23 Correct 469 ms 252776 KB Output is correct
24 Correct 1402 ms 253580 KB Output is correct
25 Correct 2199 ms 253484 KB Output is correct
26 Correct 1847 ms 253488 KB Output is correct
27 Correct 1790 ms 252844 KB Output is correct
28 Runtime error 460 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -