oj.uz

Submission #163264

# Submission time Handle Problem Language Result Execution time Memory
163264 2019-11-12T03:03:30 Z galen_colin Game (IOI13_game) C++14
80 / 100
 6233 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(12500000);
int pt = 0;
const int sentinel = 12499999;
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 183 ms 196088 KB Output is correct
2 Correct 166 ms 195980 KB Output is correct
3 Correct 183 ms 196088 KB Output is correct
4 Correct 184 ms 195960 KB Output is correct
5 Correct 168 ms 196060 KB Output is correct
6 Correct 183 ms 196060 KB Output is correct
7 Correct 186 ms 195960 KB Output is correct
8 Correct 175 ms 196080 KB Output is correct
9 Correct 166 ms 195960 KB Output is correct
10 Correct 166 ms 196088 KB Output is correct
11 Correct 165 ms 196088 KB Output is correct
12 Correct 164 ms 196048 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 196160 KB Output is correct
2 Correct 164 ms 196044 KB Output is correct
3 Correct 169 ms 196088 KB Output is correct
4 Correct 985 ms 201080 KB Output is correct
5 Correct 782 ms 201308 KB Output is correct
6 Correct 855 ms 197948 KB Output is correct
7 Correct 960 ms 197632 KB Output is correct
8 Correct 661 ms 198544 KB Output is correct
9 Correct 929 ms 197956 KB Output is correct
10 Correct 840 ms 197324 KB Output is correct
11 Correct 164 ms 196088 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 196196 KB Output is correct
2 Correct 164 ms 196040 KB Output is correct
3 Correct 165 ms 196048 KB Output is correct
4 Correct 167 ms 195968 KB Output is correct
5 Correct 165 ms 196088 KB Output is correct
6 Correct 166 ms 195960 KB Output is correct
7 Correct 187 ms 195960 KB Output is correct
8 Correct 179 ms 196184 KB Output is correct
9 Correct 174 ms 196056 KB Output is correct
10 Correct 169 ms 195960 KB Output is correct
11 Correct 179 ms 196088 KB Output is correct
12 Correct 1616 ms 201008 KB Output is correct
13 Correct 2837 ms 197796 KB Output is correct
14 Correct 527 ms 197464 KB Output is correct
15 Correct 3229 ms 197988 KB Output is correct
16 Correct 425 ms 197944 KB Output is correct
17 Correct 1356 ms 198568 KB Output is correct
18 Correct 2292 ms 198368 KB Output is correct
19 Correct 1974 ms 198324 KB Output is correct
20 Correct 1812 ms 197904 KB Output is correct
21 Correct 168 ms 195960 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 196088 KB Output is correct
2 Correct 186 ms 196088 KB Output is correct
3 Correct 167 ms 196088 KB Output is correct
4 Correct 170 ms 196176 KB Output is correct
5 Correct 185 ms 195960 KB Output is correct
6 Correct 247 ms 196028 KB Output is correct
7 Correct 365 ms 196060 KB Output is correct
8 Correct 187 ms 196196 KB Output is correct
9 Correct 186 ms 196016 KB Output is correct
10 Correct 186 ms 196088 KB Output is correct
11 Correct 185 ms 195960 KB Output is correct
12 Correct 998 ms 200944 KB Output is correct
13 Correct 790 ms 201100 KB Output is correct
14 Correct 861 ms 197944 KB Output is correct
15 Correct 940 ms 197864 KB Output is correct
16 Correct 667 ms 198380 KB Output is correct
17 Correct 951 ms 197868 KB Output is correct
18 Correct 846 ms 197340 KB Output is correct
19 Correct 1618 ms 201012 KB Output is correct
20 Correct 2839 ms 197800 KB Output is correct
21 Correct 530 ms 197320 KB Output is correct
22 Correct 3223 ms 197912 KB Output is correct
23 Correct 443 ms 198008 KB Output is correct
24 Correct 1372 ms 198460 KB Output is correct
25 Correct 2277 ms 198444 KB Output is correct
26 Correct 1933 ms 198276 KB Output is correct
27 Correct 1829 ms 197760 KB Output is correct
28 Correct 963 ms 208660 KB Output is correct
29 Correct 2379 ms 211428 KB Output is correct
30 Correct 6214 ms 203524 KB Output is correct
31 Correct 5773 ms 202404 KB Output is correct
32 Correct 709 ms 197500 KB Output is correct
33 Correct 981 ms 197596 KB Output is correct
34 Correct 595 ms 208712 KB Output is correct
35 Correct 1863 ms 204004 KB Output is correct
36 Correct 3311 ms 208884 KB Output is correct
37 Correct 2895 ms 208992 KB Output is correct
38 Correct 2724 ms 208412 KB Output is correct
39 Correct 2288 ms 206720 KB Output is correct
40 Correct 182 ms 195960 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 196064 KB Output is correct
2 Correct 167 ms 195960 KB Output is correct
3 Correct 171 ms 195984 KB Output is correct
4 Correct 165 ms 196080 KB Output is correct
5 Correct 171 ms 195976 KB Output is correct
6 Correct 165 ms 196088 KB Output is correct
7 Correct 179 ms 196000 KB Output is correct
8 Correct 165 ms 196084 KB Output is correct
9 Correct 165 ms 196092 KB Output is correct
10 Correct 164 ms 196024 KB Output is correct
11 Correct 165 ms 196060 KB Output is correct
12 Correct 992 ms 200616 KB Output is correct
13 Correct 773 ms 201080 KB Output is correct
14 Correct 977 ms 197868 KB Output is correct
15 Correct 927 ms 197516 KB Output is correct
16 Correct 666 ms 198336 KB Output is correct
17 Correct 979 ms 197544 KB Output is correct
18 Correct 862 ms 197128 KB Output is correct
19 Correct 1600 ms 200776 KB Output is correct
20 Correct 2836 ms 197604 KB Output is correct
21 Correct 722 ms 197136 KB Output is correct
22 Correct 3239 ms 197736 KB Output is correct
23 Correct 420 ms 197724 KB Output is correct
24 Correct 1422 ms 198360 KB Output is correct
25 Correct 2168 ms 197900 KB Output is correct
26 Correct 1861 ms 198036 KB Output is correct
27 Correct 1965 ms 197644 KB Output is correct
28 Correct 933 ms 208384 KB Output is correct
29 Correct 2415 ms 211396 KB Output is correct
30 Correct 6233 ms 203368 KB Output is correct
31 Correct 5671 ms 202084 KB Output is correct
32 Correct 731 ms 197172 KB Output is correct
33 Correct 973 ms 197372 KB Output is correct
34 Correct 610 ms 208380 KB Output is correct
35 Correct 1879 ms 203724 KB Output is correct
36 Correct 3472 ms 208872 KB Output is correct
37 Correct 2706 ms 209088 KB Output is correct
38 Correct 2707 ms 208312 KB Output is correct
39 Runtime error 1192 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -