oj.uz

Submission #163258

# Submission time Handle Problem Language Result Execution time Memory
163258 2019-11-12T02:40:30 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6410 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(10000000);
int pt = 0;
const int sentinel = 9999999;
struct implicit_segtree {
  bitset<60> v;
  bitset<24> 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].to_ulong();
  }

  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 191 ms 235128 KB Output is correct
2 Correct 191 ms 235120 KB Output is correct
3 Correct 193 ms 235152 KB Output is correct
4 Correct 193 ms 235128 KB Output is correct
5 Correct 194 ms 235236 KB Output is correct
6 Correct 192 ms 235128 KB Output is correct
7 Correct 191 ms 235220 KB Output is correct
8 Correct 191 ms 235128 KB Output is correct
9 Correct 190 ms 235160 KB Output is correct
10 Correct 189 ms 235148 KB Output is correct
11 Correct 190 ms 235288 KB Output is correct
12 Correct 226 ms 235264 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 235360 KB Output is correct
2 Correct 191 ms 235228 KB Output is correct
3 Correct 191 ms 235128 KB Output is correct
4 Correct 1056 ms 241080 KB Output is correct
5 Correct 826 ms 241388 KB Output is correct
6 Correct 929 ms 238112 KB Output is correct
7 Correct 1069 ms 238236 KB Output is correct
8 Correct 708 ms 238680 KB Output is correct
9 Correct 971 ms 237896 KB Output is correct
10 Correct 883 ms 237944 KB Output is correct
11 Correct 190 ms 235132 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 235192 KB Output is correct
2 Correct 191 ms 235220 KB Output is correct
3 Correct 207 ms 235128 KB Output is correct
4 Correct 192 ms 235128 KB Output is correct
5 Correct 192 ms 235260 KB Output is correct
6 Correct 190 ms 235256 KB Output is correct
7 Correct 192 ms 235148 KB Output is correct
8 Correct 191 ms 235220 KB Output is correct
9 Correct 190 ms 235256 KB Output is correct
10 Correct 261 ms 235100 KB Output is correct
11 Correct 191 ms 235216 KB Output is correct
12 Correct 1787 ms 241292 KB Output is correct
13 Correct 2980 ms 237796 KB Output is correct
14 Correct 559 ms 237812 KB Output is correct
15 Correct 3364 ms 237980 KB Output is correct
16 Correct 461 ms 237944 KB Output is correct
17 Correct 1602 ms 238544 KB Output is correct
18 Correct 2348 ms 238412 KB Output is correct
19 Correct 1967 ms 238600 KB Output is correct
20 Correct 1824 ms 237872 KB Output is correct
21 Correct 205 ms 235256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 235128 KB Output is correct
2 Correct 191 ms 235212 KB Output is correct
3 Correct 190 ms 235212 KB Output is correct
4 Correct 191 ms 235220 KB Output is correct
5 Correct 205 ms 235384 KB Output is correct
6 Correct 199 ms 235176 KB Output is correct
7 Correct 190 ms 235156 KB Output is correct
8 Correct 188 ms 235128 KB Output is correct
9 Correct 207 ms 235100 KB Output is correct
10 Correct 189 ms 235180 KB Output is correct
11 Correct 188 ms 235132 KB Output is correct
12 Correct 1045 ms 241352 KB Output is correct
13 Correct 849 ms 241876 KB Output is correct
14 Correct 916 ms 238448 KB Output is correct
15 Correct 968 ms 238236 KB Output is correct
16 Correct 718 ms 239108 KB Output is correct
17 Correct 966 ms 238036 KB Output is correct
18 Correct 902 ms 237732 KB Output is correct
19 Correct 1690 ms 240924 KB Output is correct
20 Correct 2944 ms 238132 KB Output is correct
21 Correct 539 ms 237880 KB Output is correct
22 Correct 3343 ms 238276 KB Output is correct
23 Correct 469 ms 237560 KB Output is correct
24 Correct 1450 ms 238636 KB Output is correct
25 Correct 2319 ms 238072 KB Output is correct
26 Correct 2029 ms 239020 KB Output is correct
27 Correct 1895 ms 237936 KB Output is correct
28 Correct 991 ms 250232 KB Output is correct
29 Correct 2565 ms 251664 KB Output is correct
30 Correct 6280 ms 243412 KB Output is correct
31 Correct 5819 ms 242300 KB Output is correct
32 Correct 741 ms 237280 KB Output is correct
33 Correct 1008 ms 237572 KB Output is correct
34 Correct 627 ms 248708 KB Output is correct
35 Correct 1967 ms 243912 KB Output is correct
36 Correct 3406 ms 249056 KB Output is correct
37 Correct 2779 ms 249132 KB Output is correct
38 Correct 2772 ms 248480 KB Output is correct
39 Correct 2460 ms 246276 KB Output is correct
40 Correct 197 ms 235356 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 235108 KB Output is correct
2 Correct 213 ms 235144 KB Output is correct
3 Correct 204 ms 235264 KB Output is correct
4 Correct 205 ms 235100 KB Output is correct
5 Correct 214 ms 235172 KB Output is correct
6 Correct 214 ms 235168 KB Output is correct
7 Correct 200 ms 235308 KB Output is correct
8 Correct 218 ms 235124 KB Output is correct
9 Correct 216 ms 235128 KB Output is correct
10 Correct 213 ms 235128 KB Output is correct
11 Correct 214 ms 235128 KB Output is correct
12 Correct 1059 ms 241660 KB Output is correct
13 Correct 831 ms 242040 KB Output is correct
14 Correct 896 ms 238720 KB Output is correct
15 Correct 966 ms 238584 KB Output is correct
16 Correct 764 ms 239480 KB Output is correct
17 Correct 924 ms 238712 KB Output is correct
18 Correct 899 ms 238200 KB Output is correct
19 Correct 1678 ms 241820 KB Output is correct
20 Correct 2967 ms 238620 KB Output is correct
21 Correct 541 ms 238192 KB Output is correct
22 Correct 3317 ms 238596 KB Output is correct
23 Correct 461 ms 238672 KB Output is correct
24 Correct 1446 ms 239308 KB Output is correct
25 Correct 2317 ms 239000 KB Output is correct
26 Correct 1970 ms 239112 KB Output is correct
27 Correct 1830 ms 238536 KB Output is correct
28 Correct 1159 ms 251256 KB Output is correct
29 Correct 2522 ms 251668 KB Output is correct
30 Correct 6410 ms 243428 KB Output is correct
31 Correct 5909 ms 242160 KB Output is correct
32 Correct 737 ms 237448 KB Output is correct
33 Correct 1008 ms 237468 KB Output is correct
34 Correct 638 ms 248376 KB Output is correct
35 Correct 1945 ms 243680 KB Output is correct
36 Correct 3799 ms 248716 KB Output is correct
37 Correct 2872 ms 248800 KB Output is correct
38 Correct 2855 ms 248108 KB Output is correct
39 Runtime error 1158 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -