oj.uz

Submission #163256

# Submission time Handle Problem Language Result Execution time Memory
163256 2019-11-12T02:28:35 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6280 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(1e7 + 3e6);
int pt = 0;
struct implicit_segtree {
  bitset<60> v;
  int child[2];

  implicit_segtree() {
    v = 0;
    child[0] = -1;
    child[1] = -1;
  }

  int ch(int x) {
    if (child[x] == -1) {
      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] != -1) b = vec[ch(1)].v.to_ulong();
    } else {
      if (child[0] != -1) 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] != -1) a = vec[ch(0)].query(ql, qr, tl, m);
    if (child[1] != -1) 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 178 ms 203896 KB Output is correct
2 Correct 191 ms 203900 KB Output is correct
3 Correct 190 ms 203896 KB Output is correct
4 Correct 189 ms 203868 KB Output is correct
5 Correct 175 ms 203916 KB Output is correct
6 Correct 174 ms 203896 KB Output is correct
7 Correct 182 ms 203848 KB Output is correct
8 Correct 188 ms 203848 KB Output is correct
9 Correct 173 ms 203872 KB Output is correct
10 Correct 186 ms 203868 KB Output is correct
11 Correct 189 ms 203896 KB Output is correct
12 Correct 187 ms 203888 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 203868 KB Output is correct
2 Correct 188 ms 203852 KB Output is correct
3 Correct 188 ms 203844 KB Output is correct
4 Correct 1234 ms 208624 KB Output is correct
5 Correct 793 ms 208808 KB Output is correct
6 Correct 868 ms 205684 KB Output is correct
7 Correct 913 ms 205276 KB Output is correct
8 Correct 666 ms 206180 KB Output is correct
9 Correct 908 ms 205580 KB Output is correct
10 Correct 932 ms 205268 KB Output is correct
11 Correct 172 ms 203776 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 203972 KB Output is correct
2 Correct 172 ms 203868 KB Output is correct
3 Correct 186 ms 203860 KB Output is correct
4 Correct 176 ms 203880 KB Output is correct
5 Correct 182 ms 203900 KB Output is correct
6 Correct 178 ms 203896 KB Output is correct
7 Correct 216 ms 203912 KB Output is correct
8 Correct 198 ms 203880 KB Output is correct
9 Correct 171 ms 203896 KB Output is correct
10 Correct 174 ms 203896 KB Output is correct
11 Correct 174 ms 203964 KB Output is correct
12 Correct 1629 ms 208692 KB Output is correct
13 Correct 2878 ms 205320 KB Output is correct
14 Correct 529 ms 205176 KB Output is correct
15 Correct 3300 ms 205496 KB Output is correct
16 Correct 443 ms 205308 KB Output is correct
17 Correct 1368 ms 206184 KB Output is correct
18 Correct 2119 ms 206028 KB Output is correct
19 Correct 1904 ms 206200 KB Output is correct
20 Correct 1810 ms 205472 KB Output is correct
21 Correct 190 ms 203788 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 203768 KB Output is correct
2 Correct 189 ms 203844 KB Output is correct
3 Correct 192 ms 203788 KB Output is correct
4 Correct 190 ms 203896 KB Output is correct
5 Correct 184 ms 203996 KB Output is correct
6 Correct 175 ms 203880 KB Output is correct
7 Correct 172 ms 203936 KB Output is correct
8 Correct 326 ms 203896 KB Output is correct
9 Correct 180 ms 203896 KB Output is correct
10 Correct 170 ms 203896 KB Output is correct
11 Correct 171 ms 203896 KB Output is correct
12 Correct 1134 ms 208428 KB Output is correct
13 Correct 779 ms 208892 KB Output is correct
14 Correct 872 ms 205688 KB Output is correct
15 Correct 906 ms 205308 KB Output is correct
16 Correct 671 ms 206216 KB Output is correct
17 Correct 997 ms 205432 KB Output is correct
18 Correct 839 ms 205176 KB Output is correct
19 Correct 1638 ms 208756 KB Output is correct
20 Correct 2870 ms 205392 KB Output is correct
21 Correct 521 ms 205236 KB Output is correct
22 Correct 3417 ms 205756 KB Output is correct
23 Correct 437 ms 205048 KB Output is correct
24 Correct 1406 ms 206348 KB Output is correct
25 Correct 2130 ms 205856 KB Output is correct
26 Correct 1912 ms 206168 KB Output is correct
27 Correct 1737 ms 205564 KB Output is correct
28 Correct 912 ms 216308 KB Output is correct
29 Correct 2381 ms 228808 KB Output is correct
30 Correct 6209 ms 217572 KB Output is correct
31 Correct 5938 ms 216408 KB Output is correct
32 Correct 721 ms 213764 KB Output is correct
33 Correct 1152 ms 213880 KB Output is correct
34 Correct 615 ms 222584 KB Output is correct
35 Correct 1906 ms 221000 KB Output is correct
36 Correct 3294 ms 226764 KB Output is correct
37 Correct 2693 ms 226840 KB Output is correct
38 Correct 2665 ms 226324 KB Output is correct
39 Correct 2299 ms 224272 KB Output is correct
40 Correct 368 ms 203852 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 203880 KB Output is correct
2 Correct 174 ms 203848 KB Output is correct
3 Correct 180 ms 203896 KB Output is correct
4 Correct 170 ms 203896 KB Output is correct
5 Correct 172 ms 203896 KB Output is correct
6 Correct 175 ms 203948 KB Output is correct
7 Correct 178 ms 203928 KB Output is correct
8 Correct 173 ms 203996 KB Output is correct
9 Correct 174 ms 203824 KB Output is correct
10 Correct 182 ms 203984 KB Output is correct
11 Correct 291 ms 203804 KB Output is correct
12 Correct 1010 ms 209700 KB Output is correct
13 Correct 786 ms 209932 KB Output is correct
14 Correct 845 ms 207220 KB Output is correct
15 Correct 936 ms 206864 KB Output is correct
16 Correct 662 ms 207604 KB Output is correct
17 Correct 933 ms 206944 KB Output is correct
18 Correct 848 ms 206472 KB Output is correct
19 Correct 1627 ms 210304 KB Output is correct
20 Correct 2826 ms 206856 KB Output is correct
21 Correct 558 ms 206568 KB Output is correct
22 Correct 3243 ms 207040 KB Output is correct
23 Correct 420 ms 207344 KB Output is correct
24 Correct 1345 ms 207568 KB Output is correct
25 Correct 2161 ms 208580 KB Output is correct
26 Correct 1898 ms 208724 KB Output is correct
27 Correct 1725 ms 208128 KB Output is correct
28 Correct 939 ms 219348 KB Output is correct
29 Correct 2351 ms 228944 KB Output is correct
30 Correct 6280 ms 217828 KB Output is correct
31 Correct 5835 ms 216368 KB Output is correct
32 Correct 732 ms 213752 KB Output is correct
33 Correct 1000 ms 213856 KB Output is correct
34 Correct 599 ms 222480 KB Output is correct
35 Correct 1823 ms 220956 KB Output is correct
36 Correct 3030 ms 226708 KB Output is correct
37 Correct 2626 ms 227100 KB Output is correct
38 Correct 2681 ms 226292 KB Output is correct
39 Runtime error 1277 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -