oj.uz

Submission #163270

# Submission time Handle Problem Language Result Execution time Memory
163270 2019-11-12T04:14:42 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6277 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[15000000];
}

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 208 ms 235128 KB Output is correct
2 Correct 209 ms 235256 KB Output is correct
3 Correct 202 ms 235248 KB Output is correct
4 Correct 203 ms 235100 KB Output is correct
5 Correct 204 ms 235192 KB Output is correct
6 Correct 203 ms 235128 KB Output is correct
7 Correct 205 ms 235280 KB Output is correct
8 Correct 210 ms 235128 KB Output is correct
9 Correct 210 ms 235256 KB Output is correct
10 Correct 201 ms 235128 KB Output is correct
11 Correct 201 ms 235256 KB Output is correct
12 Correct 210 ms 235128 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 235160 KB Output is correct
2 Correct 211 ms 235128 KB Output is correct
3 Correct 204 ms 235132 KB Output is correct
4 Correct 1016 ms 239588 KB Output is correct
5 Correct 906 ms 240068 KB Output is correct
6 Correct 870 ms 236424 KB Output is correct
7 Correct 964 ms 236104 KB Output is correct
8 Correct 704 ms 237028 KB Output is correct
9 Correct 937 ms 236272 KB Output is correct
10 Correct 862 ms 235796 KB Output is correct
11 Correct 206 ms 235256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 235200 KB Output is correct
2 Correct 202 ms 235152 KB Output is correct
3 Correct 202 ms 235188 KB Output is correct
4 Correct 203 ms 235256 KB Output is correct
5 Correct 199 ms 235128 KB Output is correct
6 Correct 201 ms 235192 KB Output is correct
7 Correct 199 ms 235256 KB Output is correct
8 Correct 209 ms 235236 KB Output is correct
9 Correct 203 ms 235256 KB Output is correct
10 Correct 201 ms 235256 KB Output is correct
11 Correct 203 ms 235148 KB Output is correct
12 Correct 1639 ms 239984 KB Output is correct
13 Correct 2866 ms 236064 KB Output is correct
14 Correct 601 ms 235872 KB Output is correct
15 Correct 3256 ms 236404 KB Output is correct
16 Correct 455 ms 236152 KB Output is correct
17 Correct 1394 ms 236776 KB Output is correct
18 Correct 2244 ms 236740 KB Output is correct
19 Correct 1904 ms 236756 KB Output is correct
20 Correct 1806 ms 236180 KB Output is correct
21 Correct 202 ms 235256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 235152 KB Output is correct
2 Correct 206 ms 235180 KB Output is correct
3 Correct 201 ms 235256 KB Output is correct
4 Correct 202 ms 235156 KB Output is correct
5 Correct 201 ms 235128 KB Output is correct
6 Correct 202 ms 235128 KB Output is correct
7 Correct 208 ms 235172 KB Output is correct
8 Correct 200 ms 235192 KB Output is correct
9 Correct 215 ms 235232 KB Output is correct
10 Correct 212 ms 235228 KB Output is correct
11 Correct 199 ms 235104 KB Output is correct
12 Correct 1022 ms 239844 KB Output is correct
13 Correct 807 ms 240152 KB Output is correct
14 Correct 878 ms 236288 KB Output is correct
15 Correct 964 ms 236200 KB Output is correct
16 Correct 697 ms 236856 KB Output is correct
17 Correct 930 ms 236272 KB Output is correct
18 Correct 869 ms 235748 KB Output is correct
19 Correct 1657 ms 239884 KB Output is correct
20 Correct 2852 ms 236108 KB Output is correct
21 Correct 553 ms 235868 KB Output is correct
22 Correct 3270 ms 236300 KB Output is correct
23 Correct 466 ms 236300 KB Output is correct
24 Correct 1386 ms 236900 KB Output is correct
25 Correct 2211 ms 236608 KB Output is correct
26 Correct 1873 ms 236704 KB Output is correct
27 Correct 1755 ms 236176 KB Output is correct
28 Correct 1193 ms 248696 KB Output is correct
29 Correct 2402 ms 251764 KB Output is correct
30 Correct 6261 ms 242872 KB Output is correct
31 Correct 5799 ms 241616 KB Output is correct
32 Correct 757 ms 236944 KB Output is correct
33 Correct 1006 ms 236980 KB Output is correct
34 Correct 634 ms 248712 KB Output is correct
35 Correct 1979 ms 243816 KB Output is correct
36 Correct 3367 ms 248708 KB Output is correct
37 Correct 2722 ms 248896 KB Output is correct
38 Correct 2777 ms 248264 KB Output is correct
39 Correct 2367 ms 246376 KB Output is correct
40 Correct 202 ms 235364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 235128 KB Output is correct
2 Correct 200 ms 235412 KB Output is correct
3 Correct 201 ms 235172 KB Output is correct
4 Correct 201 ms 235252 KB Output is correct
5 Correct 201 ms 235128 KB Output is correct
6 Correct 201 ms 235176 KB Output is correct
7 Correct 202 ms 235136 KB Output is correct
8 Correct 208 ms 235220 KB Output is correct
9 Correct 203 ms 235128 KB Output is correct
10 Correct 201 ms 235256 KB Output is correct
11 Correct 202 ms 235208 KB Output is correct
12 Correct 1089 ms 239804 KB Output is correct
13 Correct 812 ms 240072 KB Output is correct
14 Correct 1006 ms 236612 KB Output is correct
15 Correct 977 ms 236204 KB Output is correct
16 Correct 806 ms 237196 KB Output is correct
17 Correct 980 ms 236340 KB Output is correct
18 Correct 864 ms 235940 KB Output is correct
19 Correct 1661 ms 239872 KB Output is correct
20 Correct 2844 ms 236196 KB Output is correct
21 Correct 538 ms 236024 KB Output is correct
22 Correct 3261 ms 236440 KB Output is correct
23 Correct 460 ms 236408 KB Output is correct
24 Correct 1379 ms 237140 KB Output is correct
25 Correct 2175 ms 236672 KB Output is correct
26 Correct 1904 ms 236856 KB Output is correct
27 Correct 1764 ms 236228 KB Output is correct
28 Correct 937 ms 248396 KB Output is correct
29 Correct 2410 ms 251384 KB Output is correct
30 Correct 6277 ms 242800 KB Output is correct
31 Correct 5885 ms 241584 KB Output is correct
32 Correct 748 ms 237048 KB Output is correct
33 Correct 1012 ms 236952 KB Output is correct
34 Correct 625 ms 248568 KB Output is correct
35 Correct 1864 ms 243736 KB Output is correct
36 Correct 3321 ms 248704 KB Output is correct
37 Correct 2793 ms 249116 KB Output is correct
38 Correct 2926 ms 248424 KB Output is correct
39 Runtime error 1169 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -