oj.uz

Submission #163266

# Submission time Handle Problem Language Result Execution time Memory
163266 2019-11-12T03:09:53 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6444 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(15200000);
int pt = 0;
const int sentinel = 15199999;
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 199 ms 238328 KB Output is correct
2 Correct 203 ms 238348 KB Output is correct
3 Correct 200 ms 238396 KB Output is correct
4 Correct 208 ms 238324 KB Output is correct
5 Correct 199 ms 238456 KB Output is correct
6 Correct 201 ms 238356 KB Output is correct
7 Correct 200 ms 238520 KB Output is correct
8 Correct 202 ms 238424 KB Output is correct
9 Correct 199 ms 238556 KB Output is correct
10 Correct 199 ms 238328 KB Output is correct
11 Correct 223 ms 238328 KB Output is correct
12 Correct 224 ms 238300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 238376 KB Output is correct
2 Correct 221 ms 238296 KB Output is correct
3 Correct 225 ms 238216 KB Output is correct
4 Correct 1040 ms 242680 KB Output is correct
5 Correct 817 ms 242808 KB Output is correct
6 Correct 899 ms 239596 KB Output is correct
7 Correct 959 ms 239320 KB Output is correct
8 Correct 748 ms 240168 KB Output is correct
9 Correct 980 ms 239516 KB Output is correct
10 Correct 874 ms 239004 KB Output is correct
11 Correct 199 ms 238456 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 238284 KB Output is correct
2 Correct 200 ms 238328 KB Output is correct
3 Correct 207 ms 238364 KB Output is correct
4 Correct 202 ms 238268 KB Output is correct
5 Correct 256 ms 238364 KB Output is correct
6 Correct 205 ms 238436 KB Output is correct
7 Correct 212 ms 238328 KB Output is correct
8 Correct 227 ms 238432 KB Output is correct
9 Correct 209 ms 238336 KB Output is correct
10 Correct 205 ms 238364 KB Output is correct
11 Correct 201 ms 238328 KB Output is correct
12 Correct 1671 ms 243424 KB Output is correct
13 Correct 2881 ms 240020 KB Output is correct
14 Correct 553 ms 239848 KB Output is correct
15 Correct 3306 ms 240252 KB Output is correct
16 Correct 454 ms 240224 KB Output is correct
17 Correct 1378 ms 240992 KB Output is correct
18 Correct 2261 ms 240636 KB Output is correct
19 Correct 1904 ms 240732 KB Output is correct
20 Correct 1807 ms 240180 KB Output is correct
21 Correct 200 ms 238328 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 238336 KB Output is correct
2 Correct 200 ms 238480 KB Output is correct
3 Correct 202 ms 238328 KB Output is correct
4 Correct 200 ms 238328 KB Output is correct
5 Correct 218 ms 238368 KB Output is correct
6 Correct 200 ms 238328 KB Output is correct
7 Correct 201 ms 238240 KB Output is correct
8 Correct 200 ms 238220 KB Output is correct
9 Correct 275 ms 238360 KB Output is correct
10 Correct 442 ms 238328 KB Output is correct
11 Correct 201 ms 238328 KB Output is correct
12 Correct 1050 ms 243172 KB Output is correct
13 Correct 823 ms 243632 KB Output is correct
14 Correct 893 ms 240348 KB Output is correct
15 Correct 957 ms 240120 KB Output is correct
16 Correct 699 ms 240760 KB Output is correct
17 Correct 941 ms 240016 KB Output is correct
18 Correct 873 ms 239856 KB Output is correct
19 Correct 1662 ms 243480 KB Output is correct
20 Correct 3047 ms 240096 KB Output is correct
21 Correct 549 ms 239780 KB Output is correct
22 Correct 3367 ms 240244 KB Output is correct
23 Correct 467 ms 240376 KB Output is correct
24 Correct 1401 ms 240880 KB Output is correct
25 Correct 2215 ms 240728 KB Output is correct
26 Correct 1924 ms 240696 KB Output is correct
27 Correct 1821 ms 240020 KB Output is correct
28 Correct 997 ms 251116 KB Output is correct
29 Correct 2445 ms 254064 KB Output is correct
30 Correct 6149 ms 246000 KB Output is correct
31 Correct 5709 ms 244820 KB Output is correct
32 Correct 746 ms 239936 KB Output is correct
33 Correct 1048 ms 239908 KB Output is correct
34 Correct 626 ms 251244 KB Output is correct
35 Correct 1929 ms 246468 KB Output is correct
36 Correct 3284 ms 251484 KB Output is correct
37 Correct 2705 ms 250972 KB Output is correct
38 Correct 2727 ms 250380 KB Output is correct
39 Correct 2419 ms 248588 KB Output is correct
40 Correct 222 ms 238328 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 238328 KB Output is correct
2 Correct 224 ms 238460 KB Output is correct
3 Correct 224 ms 238328 KB Output is correct
4 Correct 223 ms 238424 KB Output is correct
5 Correct 223 ms 238456 KB Output is correct
6 Correct 223 ms 238296 KB Output is correct
7 Correct 224 ms 238448 KB Output is correct
8 Correct 223 ms 238328 KB Output is correct
9 Correct 225 ms 238328 KB Output is correct
10 Correct 222 ms 238312 KB Output is correct
11 Correct 224 ms 238328 KB Output is correct
12 Correct 1029 ms 242580 KB Output is correct
13 Correct 829 ms 242960 KB Output is correct
14 Correct 889 ms 239668 KB Output is correct
15 Correct 963 ms 239308 KB Output is correct
16 Correct 692 ms 240176 KB Output is correct
17 Correct 940 ms 239416 KB Output is correct
18 Correct 865 ms 239124 KB Output is correct
19 Correct 1647 ms 242824 KB Output is correct
20 Correct 2892 ms 239604 KB Output is correct
21 Correct 543 ms 239140 KB Output is correct
22 Correct 3241 ms 239620 KB Output is correct
23 Correct 473 ms 239516 KB Output is correct
24 Correct 1365 ms 240176 KB Output is correct
25 Correct 2179 ms 240032 KB Output is correct
26 Correct 2155 ms 240220 KB Output is correct
27 Correct 1873 ms 239600 KB Output is correct
28 Correct 986 ms 250328 KB Output is correct
29 Correct 2475 ms 253364 KB Output is correct
30 Correct 6444 ms 245504 KB Output is correct
31 Correct 5663 ms 244220 KB Output is correct
32 Correct 760 ms 239228 KB Output is correct
33 Correct 1014 ms 239372 KB Output is correct
34 Correct 638 ms 250488 KB Output is correct
35 Correct 1875 ms 245772 KB Output is correct
36 Correct 3285 ms 250880 KB Output is correct
37 Correct 2763 ms 250976 KB Output is correct
38 Correct 2738 ms 250392 KB Output is correct
39 Runtime error 926 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -