oj.uz

Submission #163249

# Submission time Handle Problem Language Result Execution time Memory
163249 2019-11-12T01:26:03 Z galen_colin Game (IOI13_game) C++14
63 / 100
 3589 ms 256004 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;
struct implicit_segtree {
  bitset<60> v;
  int child[2];

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

  int ch(int x) {
    if (child[x] == -1) {
      child[x] = vec.size();
      vec.pb(new 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;
    bitset<60> 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;
    } else {
      if (child[0] != -1) a = vec[ch(0)]->v;
      b = vec[ch(1)]->add(loc, val, m + 1, r);
    }
    
    // cout << "inner " << l << " " << r << " " << a << " " << b << " " << gcd(a, b) << endl;
    return (v = gcd(a.to_ulong(), b.to_ulong())).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 << endl;
    if (ql <= tl && tr <= qr) return v.to_ulong();
    bitset<60> 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.to_ulong(), b.to_ulong());
  }
};

using implicit_segtree_lv2 = struct implicit_segtree_lv2;
struct implicit_segtree_lv2 {
  implicit_segtree v;
  implicit_segtree_lv2* child[2];

  implicit_segtree_lv2() {
    v = 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;
//     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 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 966 ms 18300 KB Output is correct
5 Correct 722 ms 18676 KB Output is correct
6 Correct 863 ms 15624 KB Output is correct
7 Correct 994 ms 13396 KB Output is correct
8 Correct 645 ms 9428 KB Output is correct
9 Correct 1020 ms 14180 KB Output is correct
10 Correct 911 ms 13612 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 1726 ms 20444 KB Output is correct
13 Correct 3078 ms 9168 KB Output is correct
14 Correct 356 ms 2532 KB Output is correct
15 Correct 3589 ms 12512 KB Output is correct
16 Correct 348 ms 25692 KB Output is correct
17 Correct 1619 ms 16296 KB Output is correct
18 Correct 2934 ms 26976 KB Output is correct
19 Correct 2483 ms 28648 KB Output is correct
20 Correct 2345 ms 28036 KB Output is correct
21 Correct 2 ms 356 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 982 ms 18744 KB Output is correct
13 Correct 678 ms 18508 KB Output is correct
14 Correct 860 ms 16144 KB Output is correct
15 Correct 986 ms 14300 KB Output is correct
16 Correct 637 ms 9948 KB Output is correct
17 Correct 932 ms 14468 KB Output is correct
18 Correct 862 ms 14400 KB Output is correct
19 Correct 1716 ms 20696 KB Output is correct
20 Correct 2930 ms 9056 KB Output is correct
21 Correct 367 ms 2736 KB Output is correct
22 Correct 3495 ms 12916 KB Output is correct
23 Correct 371 ms 26692 KB Output is correct
24 Correct 1532 ms 16848 KB Output is correct
25 Correct 2782 ms 27744 KB Output is correct
26 Correct 2378 ms 29020 KB Output is correct
27 Correct 2261 ms 28652 KB Output is correct
28 Runtime error 1141 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 979 ms 16992 KB Output is correct
13 Correct 666 ms 17116 KB Output is correct
14 Correct 833 ms 13956 KB Output is correct
15 Correct 957 ms 12772 KB Output is correct
16 Correct 579 ms 8416 KB Output is correct
17 Correct 972 ms 13280 KB Output is correct
18 Correct 880 ms 12900 KB Output is correct
19 Correct 1688 ms 18896 KB Output is correct
20 Correct 2933 ms 7812 KB Output is correct
21 Correct 352 ms 1272 KB Output is correct
22 Correct 3418 ms 10768 KB Output is correct
23 Correct 354 ms 25308 KB Output is correct
24 Correct 1601 ms 14276 KB Output is correct
25 Correct 2838 ms 25836 KB Output is correct
26 Correct 2556 ms 27284 KB Output is correct
27 Correct 2469 ms 26816 KB Output is correct
28 Runtime error 1160 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -