oj.uz

Submission #163245

# Submission time Handle Problem Language Result Execution time Memory
163245 2019-11-12T01:07:55 Z galen_colin Game (IOI13_game) C++14
63 / 100
 3076 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;
struct implicit_segtree {
  bitset<60> v;
  implicit_segtree* child[2];

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

  implicit_segtree* ch(int x) {
    if (!child[x]) child[x] = 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 = ch(0)->add(loc, val, l, m);
      if (child[1]) b = ch(1)->v;
    } else {
      if (child[0]) a = ch(0)->v;
      b = 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]) a = ch(0)->query(ql, qr, tl, m);
    if (child[1]) b = 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 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 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 256 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 2 ms 256 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 866 ms 13656 KB Output is correct
5 Correct 650 ms 13788 KB Output is correct
6 Correct 744 ms 10616 KB Output is correct
7 Correct 827 ms 10492 KB Output is correct
8 Correct 518 ms 7416 KB Output is correct
9 Correct 804 ms 10488 KB Output is correct
10 Correct 697 ms 10072 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 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 15 ms 256 KB Output is correct
8 Correct 2 ms 256 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 1409 ms 16720 KB Output is correct
13 Correct 2621 ms 6904 KB Output is correct
14 Correct 349 ms 1784 KB Output is correct
15 Correct 3049 ms 9624 KB Output is correct
16 Correct 298 ms 18992 KB Output is correct
17 Correct 1226 ms 12404 KB Output is correct
18 Correct 2087 ms 19568 KB Output is correct
19 Correct 1873 ms 19516 KB Output is correct
20 Correct 1862 ms 18868 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.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 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 480 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 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 860 ms 13600 KB Output is correct
13 Correct 631 ms 13780 KB Output is correct
14 Correct 722 ms 10616 KB Output is correct
15 Correct 796 ms 10336 KB Output is correct
16 Correct 525 ms 7544 KB Output is correct
17 Correct 781 ms 10596 KB Output is correct
18 Correct 710 ms 10104 KB Output is correct
19 Correct 1431 ms 16828 KB Output is correct
20 Correct 2622 ms 7048 KB Output is correct
21 Correct 351 ms 1792 KB Output is correct
22 Correct 3076 ms 9580 KB Output is correct
23 Correct 304 ms 18968 KB Output is correct
24 Correct 1233 ms 12312 KB Output is correct
25 Correct 2117 ms 19296 KB Output is correct
26 Correct 1975 ms 19524 KB Output is correct
27 Correct 1785 ms 18888 KB Output is correct
28 Correct 1221 ms 251112 KB Output is correct
29 Runtime error 2557 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 11 ms 408 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 900 ms 13500 KB Output is correct
13 Correct 634 ms 13800 KB Output is correct
14 Correct 743 ms 10736 KB Output is correct
15 Correct 799 ms 10488 KB Output is correct
16 Correct 525 ms 7672 KB Output is correct
17 Correct 785 ms 10568 KB Output is correct
18 Correct 713 ms 10232 KB Output is correct
19 Correct 1463 ms 16800 KB Output is correct
20 Correct 2594 ms 7000 KB Output is correct
21 Correct 351 ms 1656 KB Output is correct
22 Correct 3036 ms 9676 KB Output is correct
23 Correct 291 ms 19064 KB Output is correct
24 Correct 1246 ms 12280 KB Output is correct
25 Correct 2073 ms 19412 KB Output is correct
26 Correct 1779 ms 19576 KB Output is correct
27 Correct 1683 ms 18928 KB Output is correct
28 Correct 1207 ms 251372 KB Output is correct
29 Runtime error 2645 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -