oj.uz

Submission #163263

# Submission time Handle Problem Language Result Execution time Memory
163263 2019-11-12T03:00:29 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6283 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(11000000);
int pt = 0;
const int sentinel = 10999999;
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 166 ms 172536 KB Output is correct
2 Correct 166 ms 172536 KB Output is correct
3 Correct 152 ms 172536 KB Output is correct
4 Correct 164 ms 172536 KB Output is correct
5 Correct 147 ms 172540 KB Output is correct
6 Correct 156 ms 172536 KB Output is correct
7 Correct 144 ms 172536 KB Output is correct
8 Correct 160 ms 172480 KB Output is correct
9 Correct 149 ms 172508 KB Output is correct
10 Correct 191 ms 172536 KB Output is correct
11 Correct 145 ms 172524 KB Output is correct
12 Correct 151 ms 172620 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 172504 KB Output is correct
2 Correct 147 ms 172508 KB Output is correct
3 Correct 149 ms 172584 KB Output is correct
4 Correct 1111 ms 176968 KB Output is correct
5 Correct 765 ms 177108 KB Output is correct
6 Correct 842 ms 174008 KB Output is correct
7 Correct 908 ms 173712 KB Output is correct
8 Correct 639 ms 174500 KB Output is correct
9 Correct 890 ms 173748 KB Output is correct
10 Correct 826 ms 173432 KB Output is correct
11 Correct 149 ms 172536 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 172524 KB Output is correct
2 Correct 148 ms 172548 KB Output is correct
3 Correct 146 ms 172664 KB Output is correct
4 Correct 147 ms 172664 KB Output is correct
5 Correct 149 ms 172508 KB Output is correct
6 Correct 148 ms 172560 KB Output is correct
7 Correct 147 ms 172568 KB Output is correct
8 Correct 150 ms 172536 KB Output is correct
9 Correct 146 ms 172708 KB Output is correct
10 Correct 160 ms 172528 KB Output is correct
11 Correct 147 ms 172508 KB Output is correct
12 Correct 1582 ms 177184 KB Output is correct
13 Correct 2869 ms 173752 KB Output is correct
14 Correct 502 ms 173332 KB Output is correct
15 Correct 3343 ms 174140 KB Output is correct
16 Correct 399 ms 173816 KB Output is correct
17 Correct 1387 ms 174376 KB Output is correct
18 Correct 2246 ms 174188 KB Output is correct
19 Correct 1939 ms 174440 KB Output is correct
20 Correct 1941 ms 173804 KB Output is correct
21 Correct 164 ms 172588 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 172540 KB Output is correct
2 Correct 165 ms 172536 KB Output is correct
3 Correct 150 ms 172496 KB Output is correct
4 Correct 158 ms 172572 KB Output is correct
5 Correct 158 ms 172536 KB Output is correct
6 Correct 164 ms 172536 KB Output is correct
7 Correct 157 ms 172624 KB Output is correct
8 Correct 146 ms 172536 KB Output is correct
9 Correct 150 ms 172536 KB Output is correct
10 Correct 146 ms 172536 KB Output is correct
11 Correct 151 ms 172664 KB Output is correct
12 Correct 977 ms 177128 KB Output is correct
13 Correct 767 ms 177296 KB Output is correct
14 Correct 861 ms 174040 KB Output is correct
15 Correct 934 ms 173972 KB Output is correct
16 Correct 648 ms 174560 KB Output is correct
17 Correct 905 ms 173816 KB Output is correct
18 Correct 817 ms 173408 KB Output is correct
19 Correct 1572 ms 177068 KB Output is correct
20 Correct 2861 ms 173704 KB Output is correct
21 Correct 488 ms 173404 KB Output is correct
22 Correct 3162 ms 173904 KB Output is correct
23 Correct 426 ms 173824 KB Output is correct
24 Correct 1549 ms 174416 KB Output is correct
25 Correct 2231 ms 174204 KB Output is correct
26 Correct 1918 ms 174316 KB Output is correct
27 Correct 1773 ms 173716 KB Output is correct
28 Correct 909 ms 184660 KB Output is correct
29 Correct 2388 ms 188892 KB Output is correct
30 Correct 6283 ms 181256 KB Output is correct
31 Correct 5659 ms 180208 KB Output is correct
32 Correct 709 ms 175220 KB Output is correct
33 Correct 962 ms 175324 KB Output is correct
34 Correct 568 ms 186492 KB Output is correct
35 Correct 1819 ms 181964 KB Output is correct
36 Correct 3670 ms 186992 KB Output is correct
37 Correct 2741 ms 186896 KB Output is correct
38 Correct 2886 ms 186396 KB Output is correct
39 Correct 2369 ms 184528 KB Output is correct
40 Correct 157 ms 172664 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 172544 KB Output is correct
2 Correct 163 ms 172536 KB Output is correct
3 Correct 160 ms 172520 KB Output is correct
4 Correct 154 ms 172536 KB Output is correct
5 Correct 163 ms 172596 KB Output is correct
6 Correct 147 ms 172476 KB Output is correct
7 Correct 164 ms 172544 KB Output is correct
8 Correct 162 ms 172536 KB Output is correct
9 Correct 164 ms 172536 KB Output is correct
10 Correct 164 ms 172576 KB Output is correct
11 Correct 164 ms 172508 KB Output is correct
12 Correct 992 ms 176704 KB Output is correct
13 Correct 777 ms 176900 KB Output is correct
14 Correct 845 ms 173944 KB Output is correct
15 Correct 921 ms 173512 KB Output is correct
16 Correct 657 ms 174284 KB Output is correct
17 Correct 919 ms 173672 KB Output is correct
18 Correct 861 ms 173284 KB Output is correct
19 Correct 1596 ms 176856 KB Output is correct
20 Correct 2794 ms 173632 KB Output is correct
21 Correct 500 ms 173132 KB Output is correct
22 Correct 3173 ms 173808 KB Output is correct
23 Correct 412 ms 173660 KB Output is correct
24 Correct 1356 ms 174308 KB Output is correct
25 Correct 2140 ms 173880 KB Output is correct
26 Correct 1837 ms 174268 KB Output is correct
27 Correct 1724 ms 173580 KB Output is correct
28 Correct 932 ms 184408 KB Output is correct
29 Correct 2396 ms 188444 KB Output is correct
30 Correct 6144 ms 180352 KB Output is correct
31 Correct 5641 ms 179228 KB Output is correct
32 Correct 706 ms 174244 KB Output is correct
33 Correct 959 ms 174328 KB Output is correct
34 Correct 578 ms 185488 KB Output is correct
35 Correct 1858 ms 180856 KB Output is correct
36 Correct 3455 ms 185852 KB Output is correct
37 Correct 2613 ms 186000 KB Output is correct
38 Correct 3442 ms 185456 KB Output is correct
39 Runtime error 1032 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -