oj.uz

Submission #163267

# Submission time Handle Problem Language Result Execution time Memory
163267 2019-11-12T03:30:50 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6479 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(14700000);
int pt = 0;
const int sentinel = 14700000;
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 196 ms 230456 KB Output is correct
2 Correct 203 ms 230612 KB Output is correct
3 Correct 196 ms 230648 KB Output is correct
4 Correct 194 ms 230440 KB Output is correct
5 Correct 195 ms 230540 KB Output is correct
6 Correct 197 ms 230520 KB Output is correct
7 Correct 207 ms 230404 KB Output is correct
8 Correct 216 ms 230432 KB Output is correct
9 Correct 207 ms 230520 KB Output is correct
10 Correct 198 ms 230580 KB Output is correct
11 Correct 206 ms 230488 KB Output is correct
12 Correct 209 ms 230492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 230444 KB Output is correct
2 Correct 206 ms 230448 KB Output is correct
3 Correct 195 ms 230520 KB Output is correct
4 Correct 1024 ms 235656 KB Output is correct
5 Correct 828 ms 235780 KB Output is correct
6 Correct 891 ms 232628 KB Output is correct
7 Correct 1002 ms 232172 KB Output is correct
8 Correct 687 ms 233140 KB Output is correct
9 Correct 943 ms 232564 KB Output is correct
10 Correct 909 ms 231936 KB Output is correct
11 Correct 197 ms 230520 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 230548 KB Output is correct
2 Correct 205 ms 230492 KB Output is correct
3 Correct 217 ms 230524 KB Output is correct
4 Correct 215 ms 230392 KB Output is correct
5 Correct 217 ms 230520 KB Output is correct
6 Correct 221 ms 230520 KB Output is correct
7 Correct 196 ms 230520 KB Output is correct
8 Correct 207 ms 230420 KB Output is correct
9 Correct 204 ms 230520 KB Output is correct
10 Correct 198 ms 230556 KB Output is correct
11 Correct 198 ms 230648 KB Output is correct
12 Correct 1650 ms 235100 KB Output is correct
13 Correct 2881 ms 231688 KB Output is correct
14 Correct 553 ms 231516 KB Output is correct
15 Correct 3358 ms 231948 KB Output is correct
16 Correct 455 ms 231812 KB Output is correct
17 Correct 1350 ms 232612 KB Output is correct
18 Correct 2236 ms 232224 KB Output is correct
19 Correct 1938 ms 232276 KB Output is correct
20 Correct 1845 ms 231808 KB Output is correct
21 Correct 198 ms 230496 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 230464 KB Output is correct
2 Correct 214 ms 230564 KB Output is correct
3 Correct 211 ms 230492 KB Output is correct
4 Correct 201 ms 230392 KB Output is correct
5 Correct 202 ms 230480 KB Output is correct
6 Correct 210 ms 230560 KB Output is correct
7 Correct 212 ms 230484 KB Output is correct
8 Correct 211 ms 230424 KB Output is correct
9 Correct 213 ms 230520 KB Output is correct
10 Correct 212 ms 230396 KB Output is correct
11 Correct 201 ms 230568 KB Output is correct
12 Correct 1035 ms 235092 KB Output is correct
13 Correct 806 ms 235308 KB Output is correct
14 Correct 879 ms 231832 KB Output is correct
15 Correct 969 ms 231544 KB Output is correct
16 Correct 693 ms 232580 KB Output is correct
17 Correct 939 ms 231816 KB Output is correct
18 Correct 852 ms 231396 KB Output is correct
19 Correct 1633 ms 235132 KB Output is correct
20 Correct 2895 ms 231812 KB Output is correct
21 Correct 543 ms 231544 KB Output is correct
22 Correct 3366 ms 231852 KB Output is correct
23 Correct 524 ms 231800 KB Output is correct
24 Correct 1385 ms 232356 KB Output is correct
25 Correct 2180 ms 232148 KB Output is correct
26 Correct 1965 ms 232328 KB Output is correct
27 Correct 1775 ms 232168 KB Output is correct
28 Correct 973 ms 242528 KB Output is correct
29 Correct 2461 ms 245772 KB Output is correct
30 Correct 6292 ms 238176 KB Output is correct
31 Correct 6019 ms 236956 KB Output is correct
32 Correct 816 ms 232068 KB Output is correct
33 Correct 1008 ms 232220 KB Output is correct
34 Correct 713 ms 243308 KB Output is correct
35 Correct 1890 ms 238636 KB Output is correct
36 Correct 3345 ms 243604 KB Output is correct
37 Correct 2788 ms 243868 KB Output is correct
38 Correct 2772 ms 243200 KB Output is correct
39 Correct 2316 ms 241468 KB Output is correct
40 Correct 213 ms 230640 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 230496 KB Output is correct
2 Correct 197 ms 230520 KB Output is correct
3 Correct 207 ms 230540 KB Output is correct
4 Correct 201 ms 230504 KB Output is correct
5 Correct 197 ms 230424 KB Output is correct
6 Correct 200 ms 230528 KB Output is correct
7 Correct 202 ms 230396 KB Output is correct
8 Correct 203 ms 230648 KB Output is correct
9 Correct 212 ms 230564 KB Output is correct
10 Correct 207 ms 230480 KB Output is correct
11 Correct 208 ms 230532 KB Output is correct
12 Correct 1197 ms 235612 KB Output is correct
13 Correct 811 ms 235784 KB Output is correct
14 Correct 902 ms 232656 KB Output is correct
15 Correct 968 ms 232376 KB Output is correct
16 Correct 724 ms 233336 KB Output is correct
17 Correct 920 ms 232364 KB Output is correct
18 Correct 850 ms 232040 KB Output is correct
19 Correct 1650 ms 235804 KB Output is correct
20 Correct 2894 ms 232476 KB Output is correct
21 Correct 543 ms 232044 KB Output is correct
22 Correct 3301 ms 232672 KB Output is correct
23 Correct 461 ms 232312 KB Output is correct
24 Correct 1396 ms 233364 KB Output is correct
25 Correct 2224 ms 232936 KB Output is correct
26 Correct 1944 ms 233060 KB Output is correct
27 Correct 1785 ms 232560 KB Output is correct
28 Correct 966 ms 243204 KB Output is correct
29 Correct 2477 ms 246496 KB Output is correct
30 Correct 6479 ms 238244 KB Output is correct
31 Correct 5829 ms 237028 KB Output is correct
32 Correct 745 ms 231872 KB Output is correct
33 Correct 1010 ms 232152 KB Output is correct
34 Correct 635 ms 243332 KB Output is correct
35 Correct 1881 ms 238564 KB Output is correct
36 Correct 3339 ms 243716 KB Output is correct
37 Correct 2776 ms 243748 KB Output is correct
38 Correct 2934 ms 243200 KB Output is correct
39 Runtime error 1536 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -